Show that infinite Cartesian product is uncountable

Question

let $A_i=\{0,1\} \forall i \in \mathbb Z^+$ and $A^{\omega}= \prod _\limits{i \in \mathbb Z^+}A_i$ thus $A^\omega=\{(a_i)|a_i=1,2 \forall i\in \mathbb Z^+\}$

now here is my problem

let $(\underline x_n)_{n \in \mathbb Z^+}$ where $\underline x_n=(x_{nk})_{k \in \mathbb Z^+}$ be a sequence in $A^\omega$. Define $\underline y=(y_n)_{n \in \mathbb Z^+}$ by $y_n=1-x_{nn}$ for all $n \in \mathbb Z^+$

a) Show that $\underline y \in A^\omega $ and $\underline y \neq \underline x_n$ for all $n\in \mathbb Z^+$

b) $\mathbf{using}$ $\mathbf{a)}$ show that $A^\omega$ is not countable

I did the a) part. And I can prove the part b) $A^\omega$ is uncountable by using diagonal argument. but here i should use the part a). my attempt was

first, I suppose $ A^\omega$ is countable.

then there exists a bijection from $f:\mathbb Z^+\to A^\omega$.

then I can list out all elements in $A^\omega$.

then since I should use a) I have to find a connection between this list and $\underline x_n$s. I am stuck here.

Answer 1

Given any function $f \colon \mathbb{Z}^+ \to A^\omega$, let $\underline{x}_n = f(n)$. Then use (a) to show that $f$ can't be surjective.

Answer 2

Hint: If $A^{\omega}$ was countable, you could choose $(\underline{x}_n)_{n \in \mathbb{Z^+}}$ to take every value of $A^{\omega}$ (Because there is a bijection between $A^{\omega}$ and $\mathbb{Z}^+$). Now, why is that impossible from (a)? (Notice that this is exactly the diagonal argument)

Answer 3

The OP's

a) / b) problem

no doubt was found in some math text book where the author wanted to break down a concept into two parts for the student to work on. But in order to understand the claimed result, the student must be able to perform logical translations between infinite products, sequences and functions.

When getting into abstract concepts, a student must be able to stand on their own two feet - a 'cookie cutter' approach doesn't 'seal the deal'. So here is my advice:

The OP should read over the problem and think about what is going on. Then they should get out a blank piece of paper and attempt a proof.

Since some time has elapsed and the OP has moved on, here we solve the problem using different notation that, in our opinion, follows naturally (working in our modern backdrop) from our rewording of the assignment. Today, Cantor's diagonal argument seems to present itself by just following the logic flow.

Let $A = \{0, 1\}$.

Let $2^{\mathbb Z_+}$ denote the set of all functions from

$\quad \mathbb Z_+$ to $A$.

Consider any function $X: \mathbb Z_+ \to 2^{\mathbb Z_+}$.

Exercise: Show that $X$ can't be a surjection.

For any fixed $n_0 \in \mathbb Z_+$, denote the function $X(n_0): \mathbb Z_+ \to A$ by $X_{n_0}$ and denote the value of this function on $n_0$, $X_{n_0}(n_0)$, by $x_{n_0}$. Letting $n_0$ vary, define a mapping $Z$ from $\mathbb Z_+$ into $A$ defined by

$\quad n \mapsto x_n - 1$.

For any $n_0 \in \mathbb Z_+$, $Z$ has a different value at $n_0$ than the function $X_{n_0}$, and so $X_{n_0} \ne Z$. Since we can let $n_0$ over all $n$ in the domain of $\mathbb Z_+$ of $X$, $Z$ is not in the image of $X$.