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?

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.

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 inﬁnite 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

- Serverfault Help
- Superuser Help
- Ubuntu Help
- Webapps Help
- Webmasters Help
- Programmers Help
- Dba Help
- Drupal Help
- Wordpress Help
- Magento Help
- Joomla Help
- Android Help
- Apple Help
- Game Help
- Gaming Help
- Blender Help
- Ux Help
- Cooking Help
- Photo Help
- Stats Help
- Math Help
- Diy Help
- Gis Help
- Tex Help
- Meta Help
- Electronics Help
- Stackoverflow Help
- Bitcoin Help
- Ethereum Help