Set Theory – The Set of All Infinite Binary Sequences

elementary-set-theoryparadoxessequences-and-series

Let's assume that there exists the set $S$ of all possible infinite binary sequences $s_i$:

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

The sequences $s_i$ are such as $\{1,1,1,1,\ldots\}$, $\{0,0,0,0,\ldots\}$, $\{0,1,0,1,\ldots\}$ etc.

Following the Cantor's diagonal argument we can construct a sequence $s_0$ that is not in the set $S$. So there is a contradiction because we had assumed 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.

Where's the problem with my reasoning? How do we define/construct the set that contains all such sequences?

Best Answer

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.