16
$\begingroup$

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?

$\endgroup$
12
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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 .

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.