Set of Mappings from Integers to Boolean Set is Uncountable

Example of Use of Cantor's Diagonal Argument

Let $S$ be the Boolean set defined as:

$S = \set {0, 1}$

Let $\mathbb G$ be the set of all mappings from the integers $\Z$ to $S$:

$\mathbb G = \set {f: \Z \to S}$

Then $\mathbb G$ is uncountably infinite.

Proof

This is an instance of the corollary to Cantor's Diagonal Argument.

$\blacksquare$

Sources

• 1979: John E. Hopcroft and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation ... (previous) ... (next): Chapter $1$: Preliminaries: $1.4$ Set Notation: Infinite sets