Information Technology Reference
In-Depth Information
Ta b l e 5 . 4
Cantor's square of binary sequences
1
010011. . .
1
0
00011. . .
10
1
0001. . .
111
0
011. . .
1010
1
1 1 ...
10110
1
1 ...
101011
0
...
... ... ... ... ... ... ... ...
No infinite list of binary sequences can contain all the infinite binary se-
quences
.The
anti-diagonal sequence
, where each symbol of the diagonal is
changed, must differ from any sequence of an infinite list. For example,
010
1001...
differs from the seven sequences explicitly indicated in the list of
Table 5.4: from the first one in its first digit, from the second one in its second
digit, and so on.
An argument similar to Cantor's diagonal argument, due to Bertrand Russell, shows
that no set
A
can be put in one-to-one correspondence with its power set
P(
A
)
.In
fact, assume, that a bijective function
f
(
x
)
could provide such a correspondence
between
A
and
P(
A
)
.Let
D
=
{
x
|
x
∈
f
(
x
)
}
then, some
y
∈
A
must exist such that
D
=
f
(
y
)
. But, for such a
y
either of the
following statements leads to a contradiction:
i
)
y
∈
D
ii
)
y
∈
D
.
In fact,
i
)
implies
y
∈
f
(
y
)
, because
y
has to satisfy the property, holding for all
the elements of
D
,
x
∈
f
(
x
)
, and by the equation
f
(
y
)=
D
defining
y
, we deduce
y
∈
D
, therefore
i
)
implies
ii
)
. Analogously,
ii
)
implies, by the equation
D
=
f
(
y
)
,
that
y
∈
f
(
y
)
, thus
y
satisfies the property of the elements of
D
, that is, we deduce
y
∈
.
According to Russell's argument, the powerset
D
, therefore
ii
)
implies
i
)
P(N)
cannot be put in one-to-one
correspondence with
. Moreover, any subset of the natural numbers identifies a
binary infinite sequence
s
(and vice versa) when we consider the numbers in this
subset as the ordinal positions in the sequence where
s
takes the value 1. But, these
sequences are in one-to-one correspondence with
N
, therefore by Russel's argument
we obtain another proof that the set of infinite binary sequences (bijective with the
reals) cannot be put in bijective correspondence with the set of the natural numbers.
R
