Lagmental Vicfred

Cantor's Diagonal Argument Makes Binary Sequences Uncountable by Vicfred

Last updated: Fri 05 July 2019

tags: mathematics, set theory, cardinals, choice

Any proposed enumeration of infinite binary sequences misses the sequence obtained by flipping the diagonal. The point is to make the formal expression readable enough to audit line by line.

Notation

Cardinality compares sets through bijections rather than geometry. The notation \(|A|\le|B|\) means an injection \(A\hookrightarrow B\) exists, while equality requires a bijection.

$$ f:\mathbf N\to\{0,1\}^{\mathbf N} $$

A reliable calculation names domain and codomain. The notation \(\mathsf{data}\mapsto\mathsf{claim}\) is harmless only after both \(\operatorname{dom}\) and \(\operatorname{cod}\) have been fixed.

$$ d(n)=1-f(n)(n)\Longrightarrow d\notin\operatorname{im}f $$

Stress the formula

Now evaluate one representative case. The result should agree with the structural law above, but it is obtained without assuming the conclusion.

$$ \begin{array}{c|ccccc}f(0)&\boxed0&1&0&1&\cdots\\f(1)&1&\boxed1&0&0&\cdots\\f(2)&0&0&\boxed1&1&\cdots\\\vdots&&&&\ddots\end{array}\quad d=(1,0,0,\ldots) $$

Interpretation

The compact alignment is a local map of the argument: assumptions on the first row, consequence on the second. Any generalisation must preserve that dependency.

$$ \begin{aligned} \mathsf{D}\;&:\quad f:\mathbf N\to\{0,1\}^{\mathbf N},\\[5pt] \mathsf{C}\;&:\quad d(n)=1-f(n)(n)\Longrightarrow d\notin\operatorname{im}f. \end{aligned} $$

Limit of the argument

Infinite cardinal arithmetic does not follow finite intuition. Removing one element or doubling a countably infinite set does not change its cardinality.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] d(n)=1-f(n)(n)\Longrightarrow d\notin\operatorname{im}f \end{gathered}} $$

I would use the boxed line as a reference later, while returning to the full display whenever a hypothesis becomes uncertain. That division keeps compression from becoming ambiguity.

This article was posted on Tue 14 February 2012. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.