After my first exposure to diagonalization argument in a proof for the proposition $$\mathbb N < \mathbb R$$ I hunted around on S.E. for a more in-depth breakdown. I found this post How does Cantor's diagonal argument work?, and enjoyed a lovely response, which was the accepted answer.
In the supplied response to the aforementioned post, the following framework is posed: define a function $f: \mathbb N \to 2^{\mathbb N}$ and prove that it cannot be surjective by virtue of strategically constructing an element of $2^{\mathbb N}$ (call it $s_f$) for which no $n$ can map into via $f$…i.e. such that $\forall n f(n) \neq s_f$.
This was a very cool argument, and it made me think of the collection of all such functions that follow the "form" of $f: \mathbb N \to 2^{\mathbb N}$.
So, for example, let's start by saying that there is an: $$f_1 : \mathbb N \to 2^{\mathbb N}$$
Then there is an: $$ f_2\neq f_1\ \ \ \text{s.t.}\ \ \ f_2: \mathbb N \to 2^{\mathbb N}$$
Then there is an: $$ f_3\neq f_2,f_1\ \ \ \text{s.t.}\ \ \ f_3: \mathbb N \to 2^{\mathbb N}$$ etc, etc.
Suppose I define the union: $\bigcup_{i=1}^\infty \{\text{range}(f_i)\}$…note the set-brackets around $\text{range}(f_i)$ . Does this equal $2^{\mathbb N}$? Said differently, can I union countably infinite numbers of sets in order to create a set (in this case $2^{\mathbb N}$) that is not countably infinite?
I assume the answer is no (see here: countably infinite union of countably infinite sets is countable), but I am having a little difficulty understanding why this must be so.
In natural language, $2^{\mathbb N}$ "describes the set of all functions from $\mathbb N$ to $\{0,1\}$". But isn't that precisely what the infinite union of all sets $\{\text{range}(f_i)\}$ is describing?
Any insight is greatly appreciated!
Best Answer
Unfortunately, these countably infinitely many functions still only hit a small part of $2^{\Bbb N}$. We can do a very similar diagonalisation argument to show that no matter which functions $f_i$ you choose, there will always be some $s\in 2^{\Bbb N}$ that none of them hit.
This will require a bit more book-keeping than the standard diagonalisation argument for a single function. So it can look a bit messy. But if you keep in the back of your mind that the basic idea is basically the same, you should be able to transfer your understanding of the diagonal proof to this one.
Let $2^{\Bbb N}$ be the set of all countably infinite binary sequences, and assume that for each $i\in \Bbb N$, we have a function $f_i:\Bbb N\to 2^{\Bbb N}$ (we can require that these all be distinct, or even that all their ranges are disjoint, but there is no need for such requirements).
For simplicity, we establish the following notation: Given a binary sequence $t$, let $t_i$ be the $i$th entry.
Now for the proof. We set $$ s_1 = 1-f_1(1)_1\\ s_2 = 1-f_1(2)_2\\ s_3 = 1-f_2(1)_3\\ s_4 = 1-f_1(3)_4\\ s_5 = 1-f_2(2)_5\\ s_6 = 1-f_3(1)_6\\ s_7 = 1-f_1(4)_7\\ s_8 = 1-f_2(3)_8\\ s_9 = 1-f_3(2)_9\\ s_{10} = 1-f_4(1)_{10}\\ \vdots $$ The idea goes as follows: For the $i$th component of $s$, we take the $i$th component of some $f_m(n)$ and flip it. This ensures $s\neq f_m(n)$. Then we go through all possible $f_m(n)$ one by one in a manner that ensures that we eventually go through them all. In this case, that manner is to first do $f_1(1)$. Then $f_1(2)$ and $f_2(1)$. Then $f_1(3)$, $f_2(2)$ and $f_3(1)$. And so on.