Set of Infinite Sequences is Uncountable

From ProofWiki

Jump to: navigation, search

Theorem

Let $X$ be a set which contains more than one element.

Let $X^\infty$ denote the set of all sequences of elements of $X$.

Then $X^\infty$ is uncountable.

As $X$ has more than one element, it must have at least two.

So, let $a, b \in X$ be those two elements.

Let $Z$ be the set of all sequences from $\left\{{a, b}\right\}$.

Suppose $X^\infty$ were countable.

So by definition, it would be possible to set up a bijection $\phi: Z \leftrightarrow \N$ between $Z$ and the set $\N$ of natural numbers:

$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle 0$	$\leftrightarrow$	$\displaystyle \left \langle {z_0} \right \rangle = \left({z_{00}, z_{01}, z_{02}, \ldots, z_{0n}, \ldots}\right)$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle 1$	$\leftrightarrow$	$\displaystyle \left \langle {z_1} \right \rangle = \left({z_{10}, z_{11}, z_{12}, \ldots, z_{1n}, \ldots}\right)$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$\vdots$	$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle n$	$\leftrightarrow$	$\displaystyle \left \langle {z_n} \right \rangle = \left({z_{n0}, z_{n1}, z_{n2}, \ldots, z_{nn}, \ldots}\right)$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$\vdots$	$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $

where each of $z_{rs}$ is:

an element of $\left\{{a, b}\right\}$
the $s$'th element of $\left \langle {z_r} \right \rangle$, the particular sequence which is in correspondence with $r \in \N$.

Now we create the sequence $Q = \left \langle {q_{dd}}\right \rangle$ where:

$q_{dd} = \begin{cases} a & : z_{dd} = b \\ b & : z_{dd} = a \end{cases}$

Thus:

$\forall n \in \N: q_{nn} \notin \left \langle {z_n} \right \rangle$

and so:

$\forall n \in \N: Q \ne \left \langle {z_n} \right \rangle$

So $Q \notin Z$.

That is, we have constructed a sequence which has not been placed into correspondence with an element of $\N$.

Thus by definition $Z$ is uncountable.

Hence, by the Rule of Transposition, $X^\infty$ is likewise uncountable.

$\blacksquare$

\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle 0\)	\(\leftrightarrow\)	\(\displaystyle \left \langle {z_0} \right \rangle = \left({z_{00}, z_{01}, z_{02}, \ldots, z_{0n}, \ldots}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle 1\)	\(\leftrightarrow\)	\(\displaystyle \left \langle {z_1} \right \rangle = \left({z_{10}, z_{11}, z_{12}, \ldots, z_{1n}, \ldots}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\vdots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle n\)	\(\leftrightarrow\)	\(\displaystyle \left \langle {z_n} \right \rangle = \left({z_{n0}, z_{n1}, z_{n2}, \ldots, z_{nn}, \ldots}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\vdots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)