Namespaces
Variants
Actions

Difference between revisions of "Diagonal process"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (fix tex)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
<!--
 +
d0315101.png
 +
$#A+1 = 52 n = 0
 +
$#C+1 = 52 : ~/encyclopedia/old_files/data/D031/D.0301510 Diagonal process
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
{{MSC|03E20}}
 +
 
A method of using a sequence consisting of sequences
 
A method of using a sequence consisting of sequences
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d0315101.png" /></td> </tr></table>
+
$$
 +
\alpha _ {i}  = ( a _ {i1} , a _ {i2} , . . . ) ,\ \
 +
i = 1 , 2 \dots
 +
$$
  
to construct a sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d0315102.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d0315103.png" /> for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d0315104.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d0315105.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d0315106.png" />. The diagonal process was first used in its original form by G. Cantor
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d0315107.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d0315108.png" />, a sequence of functions converging on a countable subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d0315109.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151010.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151011.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151012.png" /> into correspondence with the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151013.png" />;<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151014.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151015.png" />;<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151016.png" /> and is used, for example, in proving that the union of a countable set of countable sets is itself countable [[#References|[2]]].
+
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 [[#References|[2]]].
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1a]</TD> <TD valign="top">  G. Cantor,  "Ueber eine Eigenschaft des Inbegriffes aller reelen algebraischen Zahlen" , ''Gesammelte Abhandlungen'' , G. Olms  (1932)  pp. 115–118</TD></TR><TR><TD valign="top">[1b]</TD> <TD valign="top">  G. Cantor,  "Ueber eine Eigenschaft des Inbegriffes aller reelen algebraischen Zahlen"  ''J. Reine Angew. Math.'' , '''77'''  (1874)  pp. 258–262</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A.N. Kolmogorov,  S.V. Fomin,  "Elements of the theory of functions and functional analysis" , '''1–2''' , Graylock  (1957–1961)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  R. Péter,  "Rekursive Funktionen" , Ungar. Akad. Wissenschaft.  (1957)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  S.C. Kleene,  "Mathematical logic" , Wiley  (1967)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  J.R. Shoenfield,  "Mathematical logic" , Addison-Wesley  (1967)</TD></TR></table>
 
<table><TR><TD valign="top">[1a]</TD> <TD valign="top">  G. Cantor,  "Ueber eine Eigenschaft des Inbegriffes aller reelen algebraischen Zahlen" , ''Gesammelte Abhandlungen'' , G. Olms  (1932)  pp. 115–118</TD></TR><TR><TD valign="top">[1b]</TD> <TD valign="top">  G. Cantor,  "Ueber eine Eigenschaft des Inbegriffes aller reelen algebraischen Zahlen"  ''J. Reine Angew. Math.'' , '''77'''  (1874)  pp. 258–262</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A.N. Kolmogorov,  S.V. Fomin,  "Elements of the theory of functions and functional analysis" , '''1–2''' , Graylock  (1957–1961)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  R. Péter,  "Rekursive Funktionen" , Ungar. Akad. Wissenschaft.  (1957)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  S.C. Kleene,  "Mathematical logic" , Wiley  (1967)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  J.R. Shoenfield,  "Mathematical logic" , Addison-Wesley  (1967)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
 
For the statement concerning functions of a complex variable see also [[Normal family|Normal family]].
 
For the statement concerning functions of a complex variable see also [[Normal family|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151017.png" /> be a square matrix consisting of, say, zeros and ones. Then it is possible to construct a sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151018.png" /> (of zeros and ones) which differs from every row (and column) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151019.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151020.png" />. Indeed, consider the diagonal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151021.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151022.png" />; define its  "dual"  <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151023.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151024.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151025.png" />. Whatever <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151026.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151027.png" /> cannot be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151028.png" /> since it has a different <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151029.png" />-th component. If the indices range over non-negative integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151030.png" />, this proves that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151031.png" /> (there are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151032.png" /> sequences of zeros and ones of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151033.png" /> and the diagonal argument shows that every series of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151034.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151035.png" /> with its associated set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151036.png" />, this proves Cantor's theorem (cf. [[Cantor theorem|Cantor theorem]]): in terms of [[Cardinality|cardinality]], each set has more subsets than it has elements. A more abstract (though equivalent) form occurs in the Russel paradox (cf. [[Antinomy|Antinomy]]) as follows. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151037.png" /> is a set and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151038.png" /> is a binary relation on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151039.png" />, then there is no <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151040.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151041.png" />. (Diagonalization is expressed here by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151042.png" />; negation corresponds to interchanging zeros and ones in the above argument.) Without diagonalization, the same effect (to be different from each set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151043.png" />) is obtained by taking, for instance, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151044.png" />. Apart from cardinality theory, similar diagonal arguments occur in proofs of, e.g., the [[Gödel incompleteness theorem|Gödel incompleteness theorem]], Tarski's undefinability theorem and the hierarchy theorems of recursion theory (cf. [[Recursive set theory|Recursive set theory]]) and [[Descriptive set theory|descriptive set theory]].
+
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|Cantor theorem]]): in terms of [[Cardinality|cardinality]], each set has more subsets than it has elements. A more abstract (though equivalent) form occurs in the Russell paradox (cf. [[Antinomy|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|Gödel incompleteness theorem]], Tarski's undefinability theorem and the hierarchy theorems of recursion theory (cf. [[Recursive set theory|Recursive set theory]]) and [[Descriptive set theory|descriptive set theory]].
  
A different way of using (different) diagonals occurs when arranging the elements of an infinite square matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151045.png" /> (where the indices now range over the set of all non-negative integers) in a denumerably infinite sequence as follows: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151046.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151047.png" />;<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151048.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151049.png" />;<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151050.png" />. This can be used to show that, e.g., the set of rational numbers and, more generally, countable unions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151051.png" /> of countable sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031510/d03151052.png" /> are denumerable.
+
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.

Latest revision as of 20:32, 21 January 2021

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.

How to Cite This Entry:
Diagonal process. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Diagonal_process&oldid=17762
This article was adapted from an original article by Yu.N. Subbotin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article