Transcript Diagonalization

Diagonalization
Fact: Many books exist.
Fact: Some books contain the titles of other books within them.
Fact: Some books contain their own titles within them.
Consider the following book with title The Special Book.
The Special Book is defined to be a book that contains the titles of all books
that do not contain their own titles.
Question: Does the special book exist? Could one write the special book?
A similar contradiction is known as The Barber of Seville Paradox.
1
Diagonalization
•
Definition:
P(N) is the set of all subsets of N.
P(N) = { {}, {0}, {0, 1}, {1, 2, 3}, {2, 5, 9, 13},…}
•
Theorem: P(N) is uncountable.
•
Proof: (by contradiction) Suppose that P(N) is countable. Then by definition
it is either finite or countably infinite. Clearly, it is not finite, therefore it must
be countably infinite. By definition, since it is countably infinite it has the
same cardinality as N (the natural numbers) and, by definition, there is a
bijection from N to P(N).
2
f: N => P(N)
0 => P0, 1 => P1, 2 => P2, …
*f is “onto” so every set in P(N) is in this
list.
Consider the following table:
0
1
2
3…
P0
d00
d01
d02
d03
P1
d10
d11
d12
d13
P2
:
d20
d21
d22
d23
0
dij = 
1

j  Pi
j  Pi
*The table for f provides a 2 dimensional bit vector.
Example: Set {2, 5, 6} => P* =0010011000…. , 1’s only for the present
number
3
•
Consider/define the set D such that for each j ≥ 0:
j  D if and only if j  Pj
(*)
Note that D is represented by the complement (1 0) of the diagonal.
•
Observations:
– D is a subset of P
– Since P0, P1, P2, … is a list of all the subsets of P, it follows that D = Pi (**), for
some i ≥ 0.
•
Question: Is i  D ?
– By definition of D given in *, i  D if and only if i  Pi
– But D = Pi by **, and substitution gives
i  Pi if and only if i  Pi
A contradiction. Hence, P(N) is uncountable.•
4
Diagonalization
•
Theorem: The real numbers are uncountable.
•
Proof: (by contradiction) Let R denote the set of all real numbers, and suppose
that R is countable. Then by definition it is either finite or countably infinite.
Clearly, it is not finite, therefore it must be countably infinite. By definition,
since it is countably infinite it has the same cardinality as N (the natural
numbers) and, by definition, there is a bijection from N to R.
5
f: N => R
0 => r0, 1 => r1, 2 => r2, …
*f is “onto” so every real number is in this list.
Consider the following table:
0
1
2
3…
r0
d00
d01
d02
d03
r1
d10
d11
d12
d13
r2
:
d20
d21
d22
d23
where ri = xi.di0 di1 di2 … dim … (padded with zero’s to the right)
Consider real numbers over [0, 1), or xi is 0
*The table is a 2 dimensional vector of digits.
6
• Consider/define the real number:
y = 0.y0y1y2…(infinite)
where:
yi = (dii +1) mod 10
for all i ≥ 0
(*)
• Observations:
– y is a real number
– Since r0, r1, r2, … is a list of all real numbers, it follows that y must be in this list,
i.e., y = rj, for some j ≥ 0.
– This means that y = rj = 0.dj0 dj1 dj2 … djj-1 djj djj+1 … (from the table)
– This also means that yi = dji, for all i ≥ 0, and, in particular, that:
yj = djj
But by *:
yj = (djj +1) mod 10
a contradiction. Therefore, no such one-to-one and onto function exists,
and therefore the real numbers are uncountable.
• So, real numbers with 0 as the integer part is uncountably infinite. Similarly,
reals with 1 as the integer part in uncounatbly infinite, and so on. •
7
• Rational number set is countable: represent with integers p and q (for
p/q) over a matrix, and index them in a special cross-diagonal pattern
• Is the set of 2-tuples of integers (p, q) countable?
• 3-tuples?
• n-tuples, for constant n?
8