Possibly not an acceptable proof for uncountablity of countable product of countable sets

Question

Here is a text from the book Topology by Munkres:

Theorem 7.7. $ \ \ \ $ Let $X$ denote the two element set $\{0,1\}.$ Then the set $X^\omega$ is uncountable.

Proof. $\ \ \ \ $ We show that, given any function $$g:\mathbb{Z}_+\longrightarrow X^\omega,$$ $g$ is not surjective. For this purpose, let us denote $g(n)$ as follows: $$g(n)=(x_{n1},x_{n2},x_{n3},..,x_{nn},...),$$ where each $x_{ij}$ is either $0$ or $1$. Then we define an element ${\bf y}=(y_1,y_2,...,y_n,...)$ of $X^\omega$ by letting $$y_n=\begin{cases}0 &\text{if }x_{nn}=1, \\ 1 &\text{if }x_{nn}=0. \end{cases}$$ (If we write the numbers $x_{ni}$ in a rectangular array, the particular elements $x_{nn}$ appear as the diagonal entries in this array; we choose $\bf y$ so that its $n$th coordinate differs from the diagonal entry $x_{nn}$.)

Now $\bf y$ is an element of $X^\omega$, and $\bf y$ does not lie in the image of $g$; given $n$, the point $g(n)$ and the point $\bf y$ differ in at least one coordinate, namely, the $n$th. Thus, $g$ is not surjective. $$\tag*{$\blacksquare$}$$

I understand the text but I don't think that the argument is correct to be considered as proof. After choosing some arbitrary sequence of $0$'s and $1$'s (say $\alpha$), we fix it before defining $y$; i.e. $y$ is defined based on a fixed element of $g(n)$, i.e. $\alpha$, so

$1$ - How to prove that if $y\ne \alpha$ then $y\notin g(n)$ ? [note that $y$ is not a fixed unique entity]

$2$ - (Clarifications about the the mentioned proof and/or) A simpler more clear alternative proof much be appreciated.

---

Easier but similar example : Let $Y={\{1,2,3}\}$ and $Z={\{a_1,a_2,a_3}\}$ and suppose that I want to show that given any function $f: Y\rightarrow Z$, $f$ is not surjective. Let us define $f(i)=a_i$. Choose one of $a_i$'s arbitrarily and define $z=a_{i+1}$ (mod $\mathbb {Z_3}$). Since $y=a_{i+1}\ne a_i$, and $a_i$ was chosen arbitrarily so $y$ is not the image of $f$ so $f$ is not surjective. Same absurdness is going on the mentioned text from the book.

Answer 1

The argument is fine and is arguably the simplest possible argument; you’ve simply misunderstood it. I have no idea what your $\alpha$ is. The element $y$ of $X^\omega$ is not defined from some particular sequence of zeroes and ones; it depends only on the function $g$, and once $g$ has been given, $y$ is fixed.

The idea of the proof is very simple. It gives an algorithm for taking any function $g:\Bbb Z_+\to X^\omega$ and constructing from $g$ an element $y^{(g)}=\langle y_1^{(g)},y_2^{(g)},y_3^{(g)},\ldots\rangle$ of $X^\omega$ in such a way that $y^{(g)}$ is not in the range of $g$. This shows that there is no surjection from $\Bbb Z_+$ to $X^\omega$ and hence certainly no bijection.

How do we make sure that $y^{(g)}\ne g(n)$ for any $n\in\omega$? We simply make sure to define $y^{(g)}$ so that it differs from $g(n)$ in the $n$-th position. If $g(n)$ has a $0$ in the $n$-th position (i.e., if $x_{nn}=0$), then we make sure that $y_n^{(g)}=1$ instead, and if $g(n)$ has a $1$ in the $n$-th position (i.e., if $x_{nn}=1$), then we make sure that $y_n^{(g)}=0$ instead.

Imagine arranging the sequences $g(1),g(2),g(3),\ldots$ in a column, like this:

$$\begin{array}{ccc} \color{red}{x_{11}}&x_{12}&x_{13}&x_{14}&x_{15}&\ldots\\ x_{21}&\color{red}{x_{22}}&x_{23}&x_{24}&x_{25}&\ldots\\ x_{31}&x_{32}&\color{red}{x_{33}}&x_{34}&x_{35}&\ldots\\ x_{41}&x_{42}&x_{43}&\color{red}{x_{44}}&x_{45}&\ldots\\ x_{51}&x_{52}&x_{53}&x_{54}&\color{red}{x_{55}}&\ldots\\ \vdots&\vdots&\vdots&\vdots&\vdots& \end{array}$$

This array is completely determined by the function $g$ that we’re given. Now we look at the diagonal sequence of zeroes and ones, which I’ve marked in red:

$$x_{11},x_{22},x_{33},x_{44},x_{55},\ldots\tag{1}$$

This is a sequence of zeroes and ones that is determined by the function $g$. We create a new sequence $y^{(g)}$ (Munkres’ $y$, but I’m emphasizing its dependence on $g$) by changing each $0$ in the sequence $(1)$ to a $1$ and each $1$ to a $0$. Can this sequence

$$y_1^{(g)},y_2^{(g)},y_3^{(g)},y_4^{(g)},y_5^{(g)},\ldots$$

be equal to any row of the array? No: it differs from row $3$, for instance, which is the sequence $g(3)$, in the $3$-rd position: $g(3)$ has $x_{33}$ there, and $y_3^{(g)}$ is whichever of $0$ and $1$ is not $x_{33}$. The same goes for each row of the array, i.e., for each of the sequences $g(n)$, so the sequence $y^{(g)}$ is not equal to $g(n)$ for any $n\in\Bbb Z_+$. It’s an element of $X^\omega$ that is not in the range of $g$, so $g$ cannot be surjective. And since this algorithm works no matter what function $g$ we start with, no function $g:\Bbb Z_+\to X\to\omega$ can be surjective.

Answer 2

For your reference, this is the classical proof of the theorem. The argument is called Cantor's Diagonalization Argument.

$y$ is not based on a fixed element of $g(n)$, it is made from all the values $g$ may take.

Here is how it is constructed in more detail. We choose some arbitrary, but fixed, function $g:\mathbb{Z}^+ \to X^\omega$. For our example we will let $g(1)=\{1,1,0,1,...\}$, $g(2)=\{1,0,1,0,...\}$, $g(3)=\{0,0,0,0,...\}.$

Now we construct $y$. Since the first element of the sequence of $g(1)$ is $1$, we make $y_1$ the opposite, that is $y_1=0$. Now the second element of $g(2)$ is $0$, so $y_2=1$. Now the third element of $g(3)$ is $0$, so $y_3=1$. The process continues for defining all the elements of $y$.

Now we compare $y = \{0,1,1,...\}$ with $g(n)$. By the way it was constructed we see that $y\neq g(1)$, $y\neq g(2)$, $y \neq g(3)$, and so forth.

Thus $g$ misses a sequence contained in $X^\omega$. Such a sequence can be constructed for any such function $g$. If $g$ didn't miss a sequence, then $g$ would be surjective and $X^\omega$ would be countable. Conversely, if $X^\omega$ was countable, there must be some function $g : \mathbb{Z}^+ \to X^\omega$ such that $g$ is surjective.

We have just shown that any such function $g$ cannot be surjective, thus $X^\omega$ is not countable.