Let A be a set of all infinite sequences consisting of 0's and 1's. Prove that A is not countable.

Question

Sequences such as {010101010101...., 10100100100...., etc}

if i am not wrong these sequences can represent all the real numbers in the binary format, so a such a set will not be countable. but i am not sure how to go about proving it and how cantor's diagonalization fits in this case.

Answer 1

Assume it is countable, i.e. there exists an enumeration $(a_n)$ of $A$. Let $a_i:=a_i^1\cdots a_i^n\cdots$, $i=1,2,\cdots$. The element $$b=b_1\cdots b_n\cdots$$ such that $b_i\neq a_i^i$ does not coincide with any $a_i$.

Answer 2

Suppose $\{0,1\}^{\mathbb{N}}$ is countable. Then we can write $\{0,1\}^{\mathbb{N}}$ as a sequence which elements are sequences of $0$s and $1$s, $(x^1, x^2, \dots ) $. Because this has every sequence of $0$s and $1$s in fact we should have the sequence $(y_n)_{n\geq 1}$ such that $y_k = 1 -x_k^k$ that is $1$ minus the $k$-th element of the $k$-th sequence (note that this is well definided, that is $y_n$ is a sequence of $0$s and $1$s), now it follows that $(y_n)_{n\geq 1}$ must be an element of $(x^1, x^2, \dots ) $ for some $j$ that is $(y_n) = (x^j_n)$, we have arrived at a contradiction because:

$$y_j = x_j^j \quad \text{ and } \quad y_j = 1 - x_j^j$$

Answer 3

You can use Cantor's diagonalization argument.

Here's something to help you see it. If I recall correctly, this is how my prof explained it. Suppose we have the following sequences

0011010111010...

1111100000101...

0001010101010...

1011111111111...

. . .

And suppose that there are a countable number of such sequences. We can form another sequence that is different from every sequence in a list by doing the following:

For the first digit of the sequence, make it different from the first digit of the first sequence. For the second digit of the sequence, make it different from the second digit of the second sequence. For the third digit of the sequence, make it different from the third digit of the third sequence (and so on).

Thus, we can see that this sequence is different from every sequence we already had (specifically, this sequence is different from the nth sequence by the nth digit). So the set of all {0,1}-sequences is uncountable.

Note this isn't meant to be a proof.

Answer 4

This is equivalent to proof that: $|\{0,1\}^{\mathbb{N}}|=|P(\mathbb{N})|$

You can use that if $A⊆\mathbb{N}$, then $f(a)=1$ if $a∈A$ otherwise $f(b)=0$, then $$f:P(A)\to\{0,1\}^{\mathbb{N}}$$ is a bijection, and by Cantor's theorem, $∣\mathbb{N}∣<∣P(\mathbb{N})∣=|\{0,1\}^{\mathbb{N}}|$

Answer 5

Hint: The power set of $N$ is not countable. There is a natural correspondence between each subset of $N$ and an infinite sequence of $0$'s and $1$'s: The $n$th digit of the sequence being $0$ indicates that $n$ is not an element of the corresponding subset. The $n$th digit of the sequence being $1$ indicates that $n$ is an element of the corresponding subset.

Examples:

$\{2,5\}\to 01001000000000000000... $

$\emptyset \to 00000000000000000000...$

$N\to 11111111111111111111....$