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

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Set
AI Thread Summary
The set {0,1}^ω, representing infinite sequences of 0s and 1s, is proven to be uncountable through a contradiction argument. Assuming it is countable allows for the enumeration of its elements, leading to the construction of a new sequence that cannot be included in the enumeration. This demonstrates that {0,1}^ω cannot be equinumerous with the natural numbers, confirming its uncountability. The discussion also touches on the relationship between {0,1}^ω and its power set, suggesting that the uncountability of {0,1}^ω implies it is similar to the power set of the natural numbers. The importance of its infinitude is underscored in the context of these proofs.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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? :confused:
 
Physics news on Phys.org
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.
 
Which function could we pick in order to show that $\{0,1\}^{\omega} \sim \mathcal{P} (\omega)$ ?
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...

Similar threads

Replies
2
Views
3K
Replies
14
Views
2K
Replies
18
Views
2K
Replies
4
Views
2K
Replies
28
Views
6K
Replies
15
Views
2K
Back
Top