Diagonal process
A method of using a sequence consisting of sequences
![]() |
to construct a sequence where
for any
or
for all
. The diagonal process was first used in its original form by G. Cantor
in his proof that the set of real numbers in the segment is not countable; the process is therefore also known as Cantor's diagonal process. A second form of the process is utilized in the theory of functions of a real or a complex variable in order to isolate, out of a family of bounded functions on a set
, a sequence of functions converging on a countable subset of
.
The diagonal process of renumbering puts the multiple sequence ,
;
into correspondence with the sequence
;
;
and is used, for example, in proving that the union of a countable set of countable sets is itself countable [2].
References
[1a] | G. Cantor, "Ueber eine Eigenschaft des Inbegriffes aller reelen algebraischen Zahlen" , Gesammelte Abhandlungen , G. Olms (1932) pp. 115–118 |
[1b] | G. Cantor, "Ueber eine Eigenschaft des Inbegriffes aller reelen algebraischen Zahlen" J. Reine Angew. Math. , 77 (1874) pp. 258–262 |
[2] | A.N. Kolmogorov, S.V. Fomin, "Elements of the theory of functions and functional analysis" , 1–2 , Graylock (1957–1961) (Translated from Russian) |
[3] | R. Péter, "Rekursive Funktionen" , Ungar. Akad. Wissenschaft. (1957) |
[4] | S.C. Kleene, "Mathematical logic" , Wiley (1967) |
[5] | J.R. Shoenfield, "Mathematical logic" , Addison-Wesley (1967) |
Comments
For the statement concerning functions of a complex variable see also Normal family.
In fact there is no diagonal process, but there are different forms of a diagonal method or diagonal argument. In its simplest form, it consists of the following. Let be a square matrix consisting of, say, zeros and ones. Then it is possible to construct a sequence
(of zeros and ones) which differs from every row (and column)
of
. Indeed, consider the diagonal
of
; define its "dual"
by
if and only if
. Whatever
,
cannot be
since it has a different
-th component. If the indices range over non-negative integers
, this proves that
(there are
sequences of zeros and ones of length
and the diagonal argument shows that every series of
sequences necessarily misses at least one sequence). Much more important, if the indices range over all non-negative integers, this proves that there are uncountably many infinite sequences of zeros and ones (hence, for instance, the set of real numbers is non-denumerable). But the argument does not depend on the indices ranging over a countable set, any set will do. Identifying a sequence
with its associated set
, this proves Cantor's theorem (cf. Cantor theorem): in terms of cardinality, each set has more subsets than it has elements. A more abstract (though equivalent) form occurs in the Russel paradox (cf. Antinomy) as follows. If
is a set and
is a binary relation on
, then there is no
such that
. (Diagonalization is expressed here by
; negation corresponds to interchanging zeros and ones in the above argument.) Without diagonalization, the same effect (to be different from each set
) is obtained by taking, for instance,
. Apart from cardinality theory, similar diagonal arguments occur in proofs of, e.g., the Gödel incompleteness theorem, Tarski's undefinability theorem and the hierarchy theorems of recursion theory (cf. Recursive set theory) and descriptive set theory.
A different way of using (different) diagonals occurs when arranging the elements of an infinite square matrix (where the indices now range over the set of all non-negative integers) in a denumerably infinite sequence as follows:
;
;
;
;
. This can be used to show that, e.g., the set of rational numbers and, more generally, countable unions
of countable sets
are denumerable.
Diagonal process. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Diagonal_process&oldid=46641