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-toone correspondence (meaning that each and every element 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 elements 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 GEORG CANTOR (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: , , ,…. Underneath this string, list all the rationals with
numerator 2 that do not reduce to a fraction
with numerator 1:
, , ,…, and underneath 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 second 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.a 1 a 2 a 3 a 4 a 5 a 6 …
0.b 1 b 2 b 3 b 4 b 5 b 6 …
0.c 1 c 2 c 3 c 4 c 5 c 6 …
0.d 1 d 2 d 3 d 4 d 5 d 6 …
0.e 1 e 2 e 3 e 4 e 5 e 6 …
Construct another real number x = 0.α 1 α 2 α 3 …
as follows:
Set α 1 equal to 1 if a 1 is equal to an 8
or a 9, and equal to 8 if a 1 is any
other number; set α 2 equal to 1 if b 2 is
…
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
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-toone correspondence (meaning that each and every element 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 elements 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 GEORG CANTOR (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: , , ,…. Underneath this string, list all the rationals with
numerator 2 that do not reduce to a fraction
with numerator 1:
, , ,…, and underneath 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 second 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.a 1 a 2 a 3 a 4 a 5 a 6 …
0.b 1 b 2 b 3 b 4 b 5 b 6 …
0.c 1 c 2 c 3 c 4 c 5 c 6 …
0.d 1 d 2 d 3 d 4 d 5 d 6 …
0.e 1 e 2 e 3 e 4 e 5 e 6 …
Construct another real number x = 0.α 1 α 2 α 3 …
as follows:
Set α 1 equal to 1 if a 1 is equal to an 8
or a 9, and equal to 8 if a 1 is any
other number; set α 2 equal to 1 if b 2 is
…
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