The set of all infinite binary sequences

by Andyk   Last Updated September 21, 2018 18:20 PM - source

Let's suppose that we have the set $S$ of all possible infinite binary sequences $s_i$:

$$S=\{s_1,s_2,s_3,\ldots \}$$

where the sequences $s_i$ are like $\{1,1,1,1,\ldots\}$, $\{0,0,0,0,\ldots\}$, $\{0,1,0,1,\ldots\}$ etc.

However following the Cantor's diagonal argument we can construct an sequence $s_0$ that is not in the set $S$. So there is a contradiction because we had supposed that the set $S$ contains ALL such infinite sequences of $1$'s or $0$'s. If we add the $s_0$ to $S$, then we can again construct another $s_0'$ that will not be in the set $S$, and so on.

So where's the problem? How do we define/construct the set that contains all such sequences?

Answers 3

You were supposed to be assuming, for the sake of contradiction, that $S$ was countably infinite; Cantor's diagonal argument tells you how to construct, for any countably infinite collection of binary sequences, a binary sequence not in that collection. Thus, the set $S$ of all binary sequences (which is a perfectly well-defined object) is uncountable.

Zev Chonoles
Zev Chonoles
March 07, 2013 08:33 AM

To create a new set not in the collection, Cantor's argument starts as "Choose first element of new set such that it differs at first position from first set in collection, then choose second element for new set such that it differs at second position from second set in collection and so on...".

The fact that it uses is that you have a map from $\Bbb N\to A$ (the collection of all sequences(sets)), so it assumes that collection to be countable. But, since this argument contradicts the completeness of the collection , therefore, it implies that you can't have any map from $\Bbb N\to A$ and thus, $A$ is uncountable.

You can define $A$ or $S$ as $$\{(s_1,s_2,s_3,\cdots): s_i\in\{0,1\} \forall i\in \Bbb N\}$$

The only thing that cantor's diagonal argument prove is that this set of sequence is uncountable .

March 07, 2013 08:44 AM

Let $S$ denote the set of infinite binary sequences. Here is Cantor’s famous proof that $S$ is an uncountable set. Suppose that $f : S → \mathbb{N}$ is a bijection. We form a new binary sequence $A$ by declaring that the n'th digit of $A$ is the opposite of the n'th digit of $f^{−1} (n)$. The idea here is that $f ^{−1} (n)$ is some binary sequence and we can look at its n'th digit and reverse it. Supposedly, there is some N such that $f(A) = N$. But then the $N$'th digit of $A = f ^{−1} (N)$ is the opposite of the $N$'th digit of $A$, and this is a contradiction.

December 12, 2013 18:26 PM

Related Questions

Sum of infinite sequence in real world application?

Updated August 30, 2017 03:20 AM

Infinite series with finite sum

Updated March 01, 2018 15:20 PM

Infinity and Hilbert's hotel paradox

Updated February 26, 2017 22:20 PM

Why does the comparison test fail here?

Updated May 16, 2019 16:20 PM