The set {0,1}^ω is not countable

[evinda]

Hello! (Smile)

Proposition:

The set $\{0,1\}^{\omega}$ of the finite sequences with values at $\{0,1\}$ is not countable.

Proof:

$$\{ 0,1 \}^{\omega}=\{ (x_n)_{n \in \omega}: \forall n \in \omega \ x_n \in \{0,1\} \}$$

From the following theorem:

[m] No set is equinumerous with its power set.[/m]

and since the set $\{0,1\}^{\omega}$ is infinite, we have that the set $\{0,1\}^{\omega}$ is not equinumerous with $\omega$.
So this means that the powerset of $\{ 0,1 \}^{\omega}$ is $\omega$, right?But how do we deduce that?

Also at which point do we use the fact that $\{ 0,1 \}^{\omega}$ si infinite?

 

[Euge]

Hi evinda,

To show that $\{0,1\}^\omega$ is uncountable, argue indirectly. Suppose, by way of contradiction, that $\{0,1\}^\omega$ is countable. Then the elements can be enumerated

$$x^{(1)}, x^{(2)}, x^{(3)},\ldots$$

Let $y$ be the element of $\{0,1\}^\omega$ such that $y_n = 1 - x_n^{(n)}$ for all $n\in \omega$, i.e., $y_n = 0$ if $x_n^{(n)} = 1$ and $y_n = 1$ if $x_n^{(n)} = 0$. Then $y$ does not belong to the list of $x$'s. Therefore, $\{0,1\}^\omega$ is uncountable.

 

[evinda]

Which function could we pick in order to show that $\{0,1\}^{\omega} \sim \mathcal{P} (\omega)$ ?

 

[Evgeny.Makarov]

See characteristic function.