# Cantor's diagonal argument: the coherence of the sequence constructed to prove that 2[N] has a higher cardinality than N

I think I have a good understanding of how Cantor's argument for showing larger cardinalities works; but I do have a continuing problem with one part of it, namely the construction of the element (sequence) that serves to demonstrate that very difference in cardinality, for example by showing that the said sequence is not in the image of any function from $N$. Following the previously published and very detailed and informative answer here: How does Cantor's diagonal argument work?, I will also consider the argument for the case of a function $f$ from $N$ to $2^N$, where the latter is a set of all binary sequences.

The key is to show that for any $f: N \to 2^N$, so that $f(n) = (a_{1n}, a_{2n}, ..., a_{kn}, ...)$, where all $a$ are $0, 1$; there exists some $s_f$, an infinite binary tuple, that is not equal to $f(n)$ for any $n$. The standard way to do so seems to be to "construct" $s_f$ by the following rule:

$s_f = (s_1, s_2, ..., s_k, ...)$, such that for the particular $f(n)$ under consideration,

$s_k = 1$ if $a_{kn} = 0$ and $s_k = 0$ if $a_{kn} = 1$

Now this definition by construction gives us a tuple that is a perfect inverse of the tuple returned by $f(n)$ for any $n$ that we care to consider. In other words, for any $n$, $s_f \neq f(n)$, thus we conclude that $s_f$ is not the image of $f$, and thus $f$ is not surjective.

Now, the question that I have is why don't we just go one step further? If we can define a deliberately foiling tuple $s_f$, so why not now define a function $g(n): N \to 2^N = (b_{1n}, b_{2n}, ..., b_{kn}, ...)$, such that $b_{kn} = s_{k}$ for $n = 1$ and $b_{kn} = a_{k(n-1)}$ for all other $n$? You can even generalize it for any $k$ tuples you have managed to come up with that are not in the image of $f(n)$, enumerate these tuples, and then define $g$ by appending the image of $f(n)$ to the enumeration. If we define $g$ in this way, would not $g$ be surjective by construction, much like $s_f$ is not in the image of $f(n)$ by construction?

More generally, however, I am bugged by this question — can you really attempt to assess an equality between an object, in this case, $f(n)$ and another object, in this case, $s_f$, defined entirely in terms of the first object? Is not $s_f$ an object of a higher order, or a higher type to $f(n)$? We seem to treat $s_f$ as if it's just any infinite binary sequence, but it isn't, we can't even right it down on its own terms, until we know $f$. You could say that $s_f$ is just a name for a binary sequence that is somewhere out there in $2^N$; but because we defined $s_f$ to be a sequence not in the image of $f(n)$, the very assertion that $s_f$ refers to an extant sequence in $2^N$ is asserting our very result — that there are elements of $2^N$ that are not in the image of $f(n)$. Yet we don't seem to have done any work to actually prove that the sequence we purport to construct by the rules defining $s_f$ is constructible or that it's in $2^N$. Does it have to be in $2^N$ just because we formulated a rule on top of another, undefined rule of how to map the naturals onto {0, 1}? Wouldn't that assume that $2^N$ is closed under all fathomable operations, which seems to be a tall ask and, in any case, unproven?

-
Can you really assess that $1+1=2$, if $2$ is defined as $S(1)$ (the successor of $1$)? –  Asaf Karagila Jun 22 '14 at 17:11
I did wonder whether to include an aside discussing this point in greater detail, but felt it would be bloating an already verbiose question too much. You can assess $1+1=2$ and even $1 = 2$ (as wrong) because {1, 2} are members of the same set, with the operation addition defined in a systematic way across all elements. Now, there is an infinite amount of ways to define natural numbers in terms of each other, but fundamentally they are not higher order entities relative to one another. My final question is precisely that — is $s_f$ really just a binary string within $2^N$? How do we know? –  Bacchus Jun 22 '14 at 17:26
We know because we defined it to be a function from $\Bbb N$ to $\{0,1\}$. Therefore it is an infinite binary string. –  Asaf Karagila Jun 22 '14 at 17:30
It's not really a function from $N$, though, it's a function from a result of $f(n)$. So, if anything, it's a function from $2^N$ to ... something, perhaps to $2^N$, but I would like to see proof. Edit: Just saw your answer. –  Bacchus Jun 22 '14 at 17:37
No, $f$ is a function from $\Bbb N$ to $2^\Bbb N$; but $f(n)$ and $s_f$ are both functions from $\Bbb N$ to $\{0,1\}$. –  Asaf Karagila Jun 22 '14 at 18:17

Luckily for set theory, it is not type theory. So there's no issue of "types". And since we're also not limited to objects definable by particular types of formulas (like the comparison of recursive and recursively enumerable sets), there's no issue here.

We just use $f$ as a parameter in the definition of $s_f$. Namely, we have a formula $\varphi(x,y)$ in the language of set theory, that whenever we put a function $f\colon\Bbb N\to2^\Bbb N$, the only $y$ which satisfies it with $f$, is such that $y\neq f(n)$ for all $n$.

How is this formula defined? Loosely, something like "If $x$ is a function whose domain is $\Bbb N$, and for each element in the domain, $x(n)$ is a function from $\Bbb N$ into $\{0,1\}$; then $y$ is a function from $\Bbb N$ to $\{0,1\}$ such that for all $n\in\Bbb N$, it holds that $1-y(n)=x(n)(n)$".

So if you believe that this $\varphi$ is possible to write in the language of set theory, then the axioms of set theory tell you that if we fix $f$, then there exists $y$ such that $\varphi(f,y)$ is true. How is that possible? Well, there are several ways, here's one which is general enough to hold when we move from $\Bbb N$ to larger domains:

Given $n\in\Bbb N$ there is (a unique) $t$ such that $(n,t)\in f$, and there is (a unique) $t_n$ such that $(n,t_n)\in t$. This is because $f$ and $t$ are functions. Therefore there is a unique value $y_n$ such that $1-y_n=t_n$. The formula:

$$\psi(n,u,f)=\exists t\exists v\exists w\Big((n,t)\in f\land (n,v)\in t\land w=1-v\land u=(n,w)\Big)$$

If functional for $\Bbb N$, after setting $f$ as a parameter. So its range is a set. But its range is exactly $s_f$ that we wanted.

In fact, we can go even further, and define a formula which uniformly works for every $X$, not just $\Bbb N$. Simply by requiring that $f$ is a function from $X$ to $2^X$, and so on.

-
Sorry, what is $t$ in this case? –  Bacchus Jun 23 '14 at 23:48
It's a letter used to denote a variable. In this case, since it is the right coordinate of an ordered pair which appears in $f$, this means that $t$ is a function from $\Bbb N$ to $\{0,1\}$, or in proper terms, a binary string. –  Asaf Karagila Jun 23 '14 at 23:49