Diagonal process

2020 Mathematics Subject Classification: Primary: 03E20 [MSN][ZBL]

A method of using a sequence consisting of sequences

$$ \alpha _ {i} = ( a _ {i1} , a _ {i2} , . . . ) ,\ \ i = 1 , 2 \dots $$

to construct a sequence $ \alpha = ( a _ {1} , a _ {2} , . . . ) $ where $ a _ {i} \neq a _ {ii} $ for any $ i = 1 , 2 \dots $ or $ a _ {i} = a _ {ii} $ for all $ i $. 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 $ [ 0, 1 ] $ 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 $ E $, a sequence of functions converging on a countable subset of $ E $.

The diagonal process of renumbering puts the multiple sequence $ \{ a _ {ik} \} $, $ i = 1 , 2 , . . . $; $ k = 1 , 2 , . . . $ into correspondence with the sequence $ a _ {11} , a _ {12} , a _ {21} $; $ \dots $ $ a _ {k,1} , a _ {k- 1,2} \dots a _ {k- i,i+ 1} \dots a _ {1,k} $; $ \dots $ 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 $ M = \{ a _ {ik} \} _ {i,k} $ be a square matrix consisting of, say, zeros and ones. Then it is possible to construct a sequence $ \{ b _ {i} \} _ {i} $( of zeros and ones) which differs from every row (and column) $ \{ a _ {ik} \} _ {i} $ of $ M $. Indeed, consider the diagonal $ \{ a _ {ii} \} _ {i} $ of $ M $; define its "dual" $ \{ b _ {i} \} _ {i} $ by $ b _ {i} = 0 $ if and only if $ a _ {ii} = 1 $. Whatever $ k $, $ \{ b _ {i} \} _ {i} $ cannot be $ \{ a _ {ik} \} _ {i} $ since it has a different $ k $- th component. If the indices range over non-negative integers $ < m $, this proves that $ m < 2 ^ {m} $( there are $ 2 ^ {m} $ sequences of zeros and ones of length $ m $ and the diagonal argument shows that every series of $ m $ 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 $ \{ b _ {i} \} _ {i} $ with its associated set $ \{ {i } : {b _ {i} = 1 } \} $, 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 Russell paradox (cf. Antinomy) as follows. If $ A $ is a set and $ R $ is a binary relation on $ A $, then there is no $ b \in A $ such that $ \{ {a \in A } : {\neg aRa } \} = \{ {a \in A } : {aRb } \} $. (Diagonalization is expressed here by $ a R a $; negation corresponds to interchanging zeros and ones in the above argument.) Without diagonalization, the same effect (to be different from each set $ \{ {a \in A } : {aRb } \} $) is obtained by taking, for instance, $ \{ {a \in A } : {\textrm{ there is no infinite sequence } \dots a _ {1} Ra _ {0} Ra } \} $. 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 $ M = \{ a _ {i,k} \} _ {i,k} $( where the indices now range over the set of all non-negative integers) in a denumerably infinite sequence as follows: $ a _ {0,0} $; $ a _ {0,1} , a _ {1,0} $; $ \dots $; $ a _ {k,0} , a _ {k - 1,1 } \dots a _ {k - i,i } \dots a _ {0,k} $; $ \dots $. This can be used to show that, e.g., the set of rational numbers and, more generally, countable unions $ \{ {a _ {i,k} } : {i, k \in \mathbf N } \} = \cup _ {k} \{ {a _ {i,k} } : {i \in \mathbf N } \} $ of countable sets $ \{ {a _ {i,k} } : {i \in \mathbf N } \} $ are denumerable.