# Set of Infinite Sequences is Uncountable

## Theorem

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

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

Then $S^\infty$ is uncountable.

## Proof

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

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

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

Suppose $S^\infty$ were countable.

From Subset of Countably Infinite Set is Countable, $Z$ is likewise 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:

\(\ds 0\) | \(\leftrightarrow\) | \(\ds \sequence {z_0} = \tuple {z_{00}, z_{01}, z_{02}, \ldots, z_{0n}, \ldots}\) | ||||||||||||

\(\ds 1\) | \(\leftrightarrow\) | \(\ds \sequence {z_1} = \tuple {z_{10}, z_{11}, z_{12}, \ldots, z_{1n}, \ldots}\) | ||||||||||||

\(\ds \) | \(\vdots\) | \(\ds \) | ||||||||||||

\(\ds n\) | \(\leftrightarrow\) | \(\ds \sequence {z_n} = \tuple {z_{n0}, z_{n1}, z_{n2}, \ldots, z_{nn}, \ldots}\) | ||||||||||||

\(\ds \) | \(\vdots\) | \(\ds \) |

where each of $z_{rs}$ is:

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

Now we create the sequence $Q = \sequence {q_{dd} }$ where:

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

Thus:

- $\forall n \in \N: q_{nn} \notin \sequence {z_n}$

and so:

- $\forall n \in \N: Q \ne \sequence {z_n}$

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, $S^\infty$ is likewise uncountable.

$\blacksquare$

## Sources

- 1971: Allan Clark:
*Elements of Abstract Algebra*... (previous) ... (next): Chapter $1$: Mappings: $\S 15 \zeta$ - 2005: René L. Schilling:
*Measures, Integrals and Martingales*... (previous) ... (next): $2.9$