Set of Infinite Sequences is Uncountable

From ProofWiki
Jump to navigation Jump to search


This article has been identified as a candidate for Featured Proof status.
If you do not believe that this proof is worthy of being a Featured Proof, please state your reasons on the talk page.
To discuss this page in more detail, feel free to use the talk page.


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

Retrieved from "https://proofwiki.org/w/index.php?title=Set_of_Infinite_Sequences_is_Uncountable&oldid=522585"