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.

 

[blue_raver22]

To deduce that the powerset of $\{0,1\}^{\omega}$ is $\omega$, we can use the Cantor's theorem which states that the cardinality of the powerset of a set is always greater than the cardinality of the original set. Since $\omega$ is the smallest infinite cardinal number, it follows that the powerset of $\{0,1\}^{\omega}$ must have a cardinality greater than $\omega$, and therefore cannot be equal to $\omega$.

We use the fact that $\{0,1\}^{\omega}$ is infinite in the proof by contradiction. If we assume that $\{0,1\}^{\omega}$ is countable, then it would be equinumerous with $\omega$ and therefore its powerset would also be equinumerous with $\omega$. However, this contradicts Cantor's theorem, as discussed above. Therefore, we can conclude that $\{0,1\}^{\omega}$ is not countable.