example, has four distinct diagonals. A diagonal plane
for a polyhedron is any plane that passes through two
edges that are not adjacent.
diagonal argument The diagram at bottom right
shows that it is possible to match the elements of an
infinitely long line of objects with the elements of a
two-dimensional array of objects in a perfect one-to-
one correspondence (meaning that each and every ele-
ment of the first set is matched with exactly one
element of the second set, and vice versa). In some
sense, this shows that an infinite two-dimensional
array is no “larger” than an infinite one-dimensional
array. Similar constructions can be used to match ele-
ments of higher-dimensional arrays with the elements
of a single infinite line of objects.
The correspondence described is called a diagonal
argument of the first kind. It was first introduced by
German mathematician G
EORG
C
ANTOR
(1845–1918)
in 1891. This argument shows that the set of positive
RATIONAL NUMBERS
is of the same
CARDINALITY
(that
is, of exactly the same “size”) as the set of
NATURAL
NUMBERS
:
First list an infinite string including all of the
rationals with numerator 1: , , ,…. Under-
neath this string, list all the rationals with
numerator 2 that do not reduce to a fraction
with numerator 1: , , ,…, and under-
neath this, write the string of all rationals with
numerator 3 that do not reduce to a fraction
with numerator 1 or 2: ,,,,…; and so
forth. The diagonal argument now shows that
the set of all positive rationals can indeed be
presented as a single denumerable list:
,,,,,,,…
This shows that the set of rationals is
COUNTABLE
.
One can also use this argument to show that the
union of a countable number of countable sets is itself
countable: simply list the elements of each set in an
infinite string, one per line of a two-dimensional array,
and use the diagonal argument to provide a method of
listing all the elements in the array.
Cantor provided a “diagonal argument of the sec-
ond kind” to show that the set of real numbers is an
infinite set that, in some definite sense, is “larger” than
the set of counting numbers or the set of rationals. For
convenience, work with the set of real numbers in the
INTERVAL
[0,1]. Each such real number can be written
as an infinite decimal, using an infinite string of nines
if necessary. For example, 1/3 = 0.3333 … and 1/2 =
0.5 = 0.49999 … Cantor’s second-diagonal argument
proceeds as follows:
Suppose it is possible to produce a complete
list of all the real numbers from the interval
[0,1], each written as an infinite decimal
expansion:
0.a1a2a3a4a5a6…
0.b1b2b3b4b5b6…
0.c1c2c3c4c5c6…
0.d1d2d3d4d5d6…
0.e1e2e3e4e5e6…
Construct another real number x= 0.α1α2α3…
as follows:
Set α1equal to 1 if a1is equal to an 8
or a 9, and equal to 8 if a1is any
other number; set α2equal to 1 if b2is
…
4
–
1
1
–
3
2
–
3
3
–
1
1
–
2
2
–
1
1
–
1
3
–
5
3
–
4
3
–
2
3
–
1
2
–
5
2
–
3
2
–
1
1
–
3
1
–
2
1
–
1
diagonal argument 129
The diagonal correspondence