The proof of the undecidability of ATM uses a technique called diagonalization,
discovered by mathematician Georg Cantor.
Cantor was concerned with the problem of measuring the sizes of infinite sets.
If we have two infinite sets, how can we tell whether one is larger than the other or whether they are of
the same size? For finite sets, of course, answering these questions is easy. We
simply count the elements in a finite set, and the resulting number is its size.
But if we try to count the elements of an infinite set, we will never finish! So we can’t
use the counting method to determine the relative sizes of infinite sets.
Cantor proposed a rather nice solution to this problem. He observed that two
finite sets have the same size if the elements of one set can be paired with the
elements of the other set. This method compares the sizes without resorting to
counting. We can extend this idea to infinite sets.
Let N be the set of natural numbers {1, 2, 3, . . .} and let E be the set of even
natural numbers {2, 4, 6, . . .}. Using Cantor’s definition of size, we can see that
N and E have the same size. The correspondence f mapping N to E is simply
f(n) = 2n. We can visualize f more easily with the help of a table.
n f(n)
1 2
2 4
3 6
Of course, this example seems bizarre. Intuitively, E seems smaller than N because
E is a proper subset of N. But pairing each member of N with its own
member of E is possible, so we declare these two sets to be the same size.
so, cantor's theorem: A set A is countable if either it is finite or it has the same size as N.
diagonalization theorem:
If we let Q = {m/n | m, n belongs to N} be the
set of positive rational numbers, Q seems to be much larger than N. Yet these
two sets are the same size according to our definition. We give a correspondence
with N to show that Q is countable. One easy way to do so is to list all the
elements of Q. Then we pair the first element on the list with the number 1
from N, the second element on the list with the number 2 from N, and so on.
We must ensure that every member of Q appears only once on the list.
To get this list, we make an infinite matrix containing all the positive rational
numbers. The ith row contains all numbers with
numerator i and the jth column has all numbers with denominator j. So the
number i
j occurs in the ith row and jth column.
Now we turn this matrix into a list. One (bad) way to attempt it would be to
begin the list with all the elements in the first row. That isn’t a good approach
because the first row is infinite, so the list would never get to the second row.
Instead we list the elements on the diagonals, which are superimposed on the
diagram, starting from the corner. The first diagonal contains the single element
1/1 , and the second diagonal contains the two elements 2/1 and 1/2 . So the first
three elements on the list are 1/1 , 2/1 , and 1/2 . In the third diagonal, a complication
arises. It contains 3/1 , 2/2 , and 1/3 . If we simply added these to the list, we would
repeat 1/1 = 2/2 . We avoid doing so by skipping an element when it would cause
a repetition. So we add only the two new elements 3/1 and 1/3 . Continuing in this
way, we obtain a list of all the elements of Q.
diagonalization technique
