Namespaces
Variants
Actions

Difference between revisions of "Ordinal number"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (link)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 
''transfinite number, ordinal''
 
''transfinite number, ordinal''
  
The [[Order type|order type]] of a [[Well-ordered set|well-ordered set]]. This notion was introduced by G. Cantor in 1883 (see [[#References|[2]]]). For instance, the ordinal number of the set of all positive integers ordered by the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o0701801.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o0701802.png" />. The ordinal number of the set consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o0701803.png" /> and of the numbers of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o0701804.png" />, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o0701805.png" /> ordered by the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o0701806.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o0701807.png" />. One says that an ordinal number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o0701808.png" /> is equal to (less than) an ordinal number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o0701809.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018010.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018011.png" />) if a set of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018012.png" /> is similar to (a proper segment of) a set of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018013.png" />. For arbitrary ordinal numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018014.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018015.png" /> one and only one of the following possibilities holds: either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018016.png" />, or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018017.png" />, or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018018.png" />. The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018019.png" /> of all ordinal numbers less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018020.png" /> is well-ordered with type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018021.png" /> by the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018022.png" />. Moreover, any set of ordinal numbers is well-ordered by the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018023.png" />, i.e. any non-empty set of ordinal numbers contains a least ordinal number. For any set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018024.png" /> of ordinal numbers there exists an ordinal number greater than any ordinal number from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018025.png" />. Accordingly, the set of all ordinal numbers does not exist. The smallest of the ordinal numbers following an ordinal number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018026.png" /> is called the successor of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018027.png" /> and is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018028.png" />. The ordinal number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018029.png" /> is called the predecessor of the ordinal number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018030.png" />. An ordinal number is called a limit (ordinal) number if it does not have a predecessor. Thus, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018031.png" /> is a limit number. Any ordinal number can be represented in the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018032.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018033.png" /> is a limit number and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018034.png" /> is an integer, the sum is understood in the sense of addition of order types (cf. [[Order type|Order type]]).
+
The [[Order type|order type]] of a [[Well-ordered set|well-ordered set]]. This notion was introduced by G. Cantor in 1883 (see [[#References|[2]]]). For instance, the ordinal number of the set $ \mathbf{N} $ of all positive integers, ordered by the relation $ \leq $, is $ \omega $. The ordinal number of the set consisting of $ 1 $ and numbers of the form $ 1 - \dfrac{1}{n} $ where $ n \in \mathbf{N} $, ordered by the relation $ \leq $, is $ \omega + 1 $. One says that an ordinal number $ \alpha $ is '''equal to''' ('''less than''') an ordinal number $ \beta $, written $ \alpha = \beta $ ($ \alpha < \beta $), if and only if a set of type $ \alpha $ is similar to (a proper segment of) a set of type $ \beta $. For arbitrary ordinal numbers $ \alpha $ and $ \beta $, one and only one of the following possibilities holds:
  
A transfinite sequence of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018035.png" />, or an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018037.png" />-sequence, is a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018038.png" /> defined on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018039.png" />. If the values of this sequence are ordinal numbers and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018040.png" /> implies that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018041.png" />, then it is called an ascending sequence. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018042.png" /> denote a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018043.png" />-sequence, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018044.png" /> is a limit number. The least of the ordinal numbers greater than any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018045.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018046.png" />, is called the limit of the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018047.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018048.png" /> and is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018049.png" />. For instance, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018050.png" />. An ordinal number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018051.png" /> is cofinal to a limit number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018052.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018053.png" /> is the limit of an ascending <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018054.png" />-sequence: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018055.png" />. The ordinal number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018056.png" /> is the least ordinal number to which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018057.png" /> is cofinal.
+
* $ \alpha < \beta $.
 +
* $ \alpha = \beta $.
 +
* $ \alpha > \beta $.
  
An ordinal number is called regular if it is not cofinal to any smaller ordinal number, otherwise it is called singular. An infinite ordinal number is called an initial ordinal number of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018058.png" /> if it is the least among the ordinal numbers of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018059.png" /> (i.e. among the order types of well-ordered sets of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018060.png" />). Hence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018061.png" /> is the least initial number. The initial ordinal number of power <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018062.png" /> is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018063.png" />. The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018064.png" /> of all initial ordinal numbers of infinite cardinality less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018065.png" /> is well-ordered. If the ordinal number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018066.png" /> is its order type, then one puts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018067.png" />. Thus, every initial ordinal number is provided with an index equal to the order type of the set of all initial ordinal numbers less than it. In particular, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018068.png" />. Different indices correspond to different initial numbers. Each ordinal number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018069.png" /> is the index of some initial number. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018070.png" /> is a limit ordinal number, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018071.png" /> is a regular initial number.
+
The set $ \{ \beta \mid \beta < \alpha \} $ of all ordinal numbers less than $ \alpha $ is well-ordered with type $ \alpha $ by the relation $ \leq $. Moreover, any set of ordinal numbers is well-ordered by the relation $ \leq $, i.e., any non-empty set of ordinal numbers contains a least ordinal number. For any set $ Z $ of ordinal numbers, there exists an ordinal number greater than any ordinal number from $ Z $. Accordingly, the set of all ordinal numbers does not exist. The smallest of the ordinal numbers following an ordinal number $ \alpha $ is called the '''successor''' of $ \alpha $ and is denoted by $ \alpha + 1 $. The ordinal number $ \alpha $ is called the '''predecessor''' of the ordinal number $ \alpha + 1 $. An ordinal number is called a '''limit''' ordinal number if and only if it does not have a predecessor. Thus, $ 0 $ is a limit ordinal number. Any ordinal number can be represented in the form $ \alpha = \lambda + n $, where $ \lambda $ is a limit ordinal number and $ n $ is an integer, the sum being understood in the sense of addition of [[Order type|order types]].
  
An initial number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018072.png" /> is called weakly inaccessible if it is regular and its index <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018073.png" /> is a limit number. For instance, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018074.png" /> is weakly inaccessible, but <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018075.png" /> is singular and, thus, is not weakly inaccessible. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018076.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018077.png" /> is weakly inaccessible if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018078.png" />.
+
A '''transfinite sequence''' of type $ \alpha $, or an '''$ \alpha $-sequence''', is a function $ \phi $ defined on $ \{ \beta \mid \beta < \alpha \} $. If the values of this sequence are ordinal numbers, and if $ \gamma < \beta < \alpha $ implies that $ \phi(\gamma) < \phi(\beta) $, then it is called an '''ascending sequence'''. Let $ \phi $ denote a $ \lambda $-sequence, where $ \lambda $ is a limit ordinal number. The least of the ordinal numbers greater than any $ \phi(\gamma) $, where $ \gamma < \lambda $, is called the '''limit''' of the sequence $ (\phi(\gamma))_{\gamma < \lambda} $ and is denoted by $ \displaystyle \lim_{\gamma < \lambda} \phi(\lambda) $. For instance, $ \displaystyle \omega = \lim_{n < \omega} n = \lim_{n < \omega} n^{2} $. An ordinal number $ \lambda $ is '''cofinal''' to a limit ordinal number $ \alpha $ if and only if $ \lambda $ is the limit of an ascending $ \alpha $-sequence: $ \displaystyle \lambda = \lim_{\xi < \alpha} \phi(\xi) $. The ordinal number $ \mathsf{cf}(\lambda) $ is the least ordinal number to which $ \lambda $ is cofinal.
  
Weakly-inaccessible ordinal numbers allow a classification similar to the classification of inaccessible cardinal numbers (cf. [[Cardinal number|Cardinal number]]). The sum and the product of two ordinal numbers is an ordinal number. If the set of indices is well-ordered, then the well-ordered sum of ordinal numbers is an ordinal number. One can also introduce the operation of raising to a power, by [[Transfinite induction|transfinite induction]]: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018079.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018080.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018081.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018082.png" /> is a limit number. The number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018083.png" /> is called a power of a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018084.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018085.png" /> is the base of the power and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018086.png" /> is the exponent of the power. For example, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018087.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018088.png" />, one obtains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018089.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018090.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018091.png" />. The limit of this sequence, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018092.png" />, is the least critical number of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018093.png" />, i.e. the least ordinal number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018094.png" /> among those for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018095.png" />. Numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018096.png" /> for which this equality holds are called epsilon-ordinals.
+
An ordinal number is called '''regular''' if and only if it is not cofinal to any smaller ordinal number, otherwise it is called '''singular'''. An infinite ordinal number is called an '''initial''' ordinal number of cardinality $ \tau $ if and only if it is the least among the ordinal numbers of cardinality $ \tau $ (i.e., among the order types of well-ordered sets of cardinality $ \tau $). Hence, $ \omega $ is the least initial ordinal number. The initial ordinal number of power $ \tau $ is denoted by $ \omega(\tau) $. The set $ \{ \omega(\delta) \mid \aleph_{0} \leq \delta < \tau \} $ of all initial ordinal numbers of infinite cardinality less than $ \tau $ is well-ordered. If the ordinal number $ \alpha $ is its order type, then one puts $ \omega(\tau) = \omega_{\alpha} $. Therefore, every initial ordinal number is provided with an index equal to the order type of the set of all initial ordinal numbers less than it. In particular, $ \omega_{0} = \omega $. Different indices correspond to different initial ordinal numbers. Each ordinal number $ \alpha $ is the index of some initial ordinal number. If $ \lambda $ is a limit ordinal number, then $ \mathsf{cf}(\lambda) $ is a regular initial ordinal number.
  
Raising to a power can be used to represent ordinal numbers in a form resembling decimal representation of positive integers. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018097.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018098.png" />, then there exists a positive integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o07018099.png" /> and sequences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o070180100.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o070180101.png" /> such that
+
An initial ordinal number $ \omega_{\alpha} $ is called '''weakly inaccessible''' if and only if it is regular and its index $ \alpha $ is a limit ordinal number. For instance, $ \omega = \omega_{0} $ is weakly inaccessible, but $ \omega_{\omega} $ is singular and is thus not weakly inaccessible. If $ \alpha > 0 $, then $ \omega_{\alpha} $ is weakly inaccessible if and only if $ \alpha = \omega_{\alpha} = \mathsf{cf}(\alpha) $.
  
<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/o/o070/o070180/o070180102.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
Weakly-inaccessible ordinal numbers allow a classification similar to the classification of [[inaccessible cardinal]]s (cf. [[Cardinal number]]). The sum and the product of two ordinal numbers is an ordinal number. If the set of indices is well-ordered, then the well-ordered sum of ordinal numbers is an ordinal number. One can also introduce the operation of raising to a power, by [[Transfinite induction|transfinite induction]]:
  
<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/o/o070/o070180/o070180103.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
* $ \gamma^{0} \stackrel{\text{df}}{=} 1 $.
 +
* $ \gamma^{\xi + 1} \stackrel{\text{df}}{=} \gamma^{\xi} \cdot \gamma $.
 +
* $ \displaystyle \gamma^{\lambda} \stackrel{\text{df}}{=} \lim_{\xi < \lambda} \gamma^{\xi} $, where $ \lambda $ is a limit ordinal number.
  
for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o070180104.png" />. Formula (1) for the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o070180105.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o070180106.png" /> satisfying the conditions (2) is called the representation of the ordinal number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o070180107.png" /> in the base <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o070180108.png" />. The numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o070180109.png" /> are called the digits, and the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o070180110.png" /> are called the exponents of this representation. The representation of an ordinal number in a given base is unique. The representation of ordinal numbers in the base <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o070180111.png" /> is used to define the natural sum and the natural product of ordinal numbers.
+
The number $ \gamma^{\alpha} $ is called a '''power''' of a number $ \gamma $, where $ \gamma $ is called the '''base''' of the power and $ \alpha $ the '''exponent''' of the power. For example, if $ \gamma = \omega $ and $ \alpha_{0} = 1 $, then one obtains
 +
$$
 +
\alpha_{1} = \gamma^{\alpha_{0}}, \quad \alpha_{2} = \omega^{\omega}, \quad \alpha_{3} = \omega^{\omega^{\omega}}, \quad \ldots.
 +
$$
 +
The limit of this sequence, $ \displaystyle \epsilon \stackrel{\text{df}}{=} \lim_{n < \omega} \alpha_{n} $, is the least critical number of the function $ \xi \mapsto \omega^{\xi} $, i.e., the least ordinal number $ \alpha $ among those for which $ \omega^{\alpha} = \alpha $. Numbers $ \alpha $ for which this equality holds are called '''epsilon-ordinals'''.
 +
 
 +
Raising to a power can be used to represent ordinal numbers in a form resembling the decimal representation of positive integers. If $ \gamma > 1 $ and $ 1 \leq \alpha < \gamma^{\eta} $, then there exists a positive integer $ n $ and sequences $ \beta_{1},\ldots,\beta_{n} $ and $ \eta_{1},\ldots,\eta_{n} $ such that
 +
\begin{gather}
 +
\alpha = \gamma^{\eta_{1}} \cdot \beta_{1} + \cdots + \gamma^{\eta_{n}} \cdot \beta_{n}, \qquad (1) \\
 +
\eta > \eta_{1} > \ldots > \eta_{n}, \qquad 0 \leq \beta_{i} < \gamma, \qquad (2)
 +
\end{gather}
 +
for $ i \in \{ 1,\ldots,n \} $. Formula (1) for the numbers $ \beta_{j} $ and $ \eta_{j} $ satisfying the conditions in (2) is called the '''representation''' of the ordinal number $ \alpha $ in the base $ \gamma $. The numbers $ \beta_{i} $ are called the '''digits''', and the numbers $ \eta_{i} $ the '''exponents''' of this representation. The representation of an ordinal number in a given base is unique. The representation of ordinal numbers in the base $ \omega $ is used to define the natural sum and the natural product of ordinal numbers.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  P.S. Aleksandrov,  "Einführung in die Mengenlehre und die Theorie der reellen Funktionen" , Deutsch. Verlag Wissenschaft.  (1956)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  G. Cantor,  "Contributions to the founding of the theory of transfinite numbers" , Dover, reprint  (1952)  (Translated from German)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  F. Hausdorff,  "Grundzüge der Mengenlehre" , Leipzig  (1914)  (Reprinted (incomplete) English translation: Set theory, Chelsea (1978))</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  K. Kuratowski,  A. Mostowski,  "Set theory" , North-Holland  (1968)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  W. Sierpiński,  "Cardinal and ordinal numbers" , PWN  (1958)</TD></TR></table>
 
  
 +
<table>
 +
<TR><TD valign="top">[1]</TD><TD valign="top">
 +
P.S. Aleksandrov, “Einführung in die Mengenlehre und die Theorie der reellen Funktionen”, Deutsch. Verlag Wissenschaft. (1956). (Translated from Russian)</TD></TR>
 +
<TR><TD valign="top">[2]</TD><TD valign="top">
 +
G. Cantor, “Contributions to the founding of the theory of transfinite numbers”, Dover, reprint (1952). (Translated from German)</TD></TR>
 +
<TR><TD valign="top">[3]</TD><TD valign="top">
 +
F. Hausdorff, “Grundzüge der Mengenlehre”, Leipzig (1914). (Reprinted (incomplete) English translation: Set theory, Chelsea (1978)).</TD></TR>
 +
<TR><TD valign="top">[4]</TD><TD valign="top">
 +
K. Kuratowski, A. Mostowski, “Set theory”, North-Holland (1968).</TD></TR>
 +
<TR><TD valign="top">[5]</TD><TD valign="top">
 +
W. Sierpiński, “Cardinal and ordinal numbers”, PWN (1958).</TD></TR>
 +
</table>
  
 +
====Comments====
  
====Comments====
+
The ordinal $ \mathsf{cf}(\lambda) $, the least ordinal number to which $ \lambda $ is cofinal, is called the '''cofinality''' of $ \lambda $.
The ordinal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o070180112.png" />, the least ordinal number to which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o070180113.png" /> is cofinal, is called the cofinality of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o070180114.png" />.
 
  
The ordinal number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o070180115.png" /> and (by the [[Axiom of choice|axiom of choice]]) each initial ordinal number with a successor-index are regular. Initial ordinal numbers with a limit-index are singular, in general. More precisely, if the axioms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o070180116.png" /> set theory are consistent, they remain so after the addition of the axiom stating that all initials with limit-index <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o070180117.png" /> are singular. Thus, the axioms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o070180118.png" />, if consistent, cannot prove that there are any weakly-inaccessible ordinal numbers other than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070180/o070180119.png" />.
+
The ordinal number $ \omega $ and (by the [[Axiom of choice|axiom of choice]]) each initial ordinal number with a successor-index are regular. Initial ordinal numbers with a limit-index are singular in general. More precisely, if the axioms of $ \mathsf{ZF} $ are consistent, they remain so after the addition of the axiom that states that all initial ordinal numbers with limit-index $ > 0 $ are singular. Therefore, the axioms of $ \mathsf{ZF} $, if consistent, cannot prove that there are any weakly-inaccessible ordinal numbers other than $ \omega $.
  
For countable ordinal numbers see also [[Descriptive set theory|Descriptive set theory]].
+
For countable ordinal numbers, see also [[Descriptive set theory|Descriptive set theory]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> K. Kuratowski,   "Introduction to set theory and topology" , Pergamon (1972) (Translated from Polish)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> T.J. Jech,   "Set theory" , Acad. Press (1978) (Translated from German)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> J. Barwise (ed.) , ''Handbook of mathematical logic'' , North-Holland (1977) ((especially the article of D.A. Martin on Descriptive set theory))</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> A. Levy,   "Basic set theory" , Springer (1979)</TD></TR></table>
+
 
 +
<table>
 +
<TR><TD valign="top">[a1]</TD><TD valign="top">
 +
K. Kuratowski, “Introduction to set theory and topology”, Pergamon (1972). (Translated from Polish)</TD></TR>
 +
<TR><TD valign="top">[a2]</TD><TD valign="top">
 +
T.J. Jech, “Set theory”, Acad. Press (1978). (Translated from German)</TD></TR>
 +
<TR><TD valign="top">[a3]</TD><TD valign="top">
 +
J. Barwise (ed.), ''Handbook of mathematical logic'', North-Holland (1977). (Especially the article of D.A. Martin on Descriptive set theory).</TD></TR>
 +
<TR><TD valign="top">[a4]</TD><TD valign="top">
 +
A. Levy, “Basic set theory”, Springer (1979).</TD></TR>
 +
</table>

Latest revision as of 18:33, 4 December 2017

transfinite number, ordinal

The order type of a well-ordered set. This notion was introduced by G. Cantor in 1883 (see [2]). For instance, the ordinal number of the set $ \mathbf{N} $ of all positive integers, ordered by the relation $ \leq $, is $ \omega $. The ordinal number of the set consisting of $ 1 $ and numbers of the form $ 1 - \dfrac{1}{n} $ where $ n \in \mathbf{N} $, ordered by the relation $ \leq $, is $ \omega + 1 $. One says that an ordinal number $ \alpha $ is equal to (less than) an ordinal number $ \beta $, written $ \alpha = \beta $ ($ \alpha < \beta $), if and only if a set of type $ \alpha $ is similar to (a proper segment of) a set of type $ \beta $. For arbitrary ordinal numbers $ \alpha $ and $ \beta $, one and only one of the following possibilities holds:

  • $ \alpha < \beta $.
  • $ \alpha = \beta $.
  • $ \alpha > \beta $.

The set $ \{ \beta \mid \beta < \alpha \} $ of all ordinal numbers less than $ \alpha $ is well-ordered with type $ \alpha $ by the relation $ \leq $. Moreover, any set of ordinal numbers is well-ordered by the relation $ \leq $, i.e., any non-empty set of ordinal numbers contains a least ordinal number. For any set $ Z $ of ordinal numbers, there exists an ordinal number greater than any ordinal number from $ Z $. Accordingly, the set of all ordinal numbers does not exist. The smallest of the ordinal numbers following an ordinal number $ \alpha $ is called the successor of $ \alpha $ and is denoted by $ \alpha + 1 $. The ordinal number $ \alpha $ is called the predecessor of the ordinal number $ \alpha + 1 $. An ordinal number is called a limit ordinal number if and only if it does not have a predecessor. Thus, $ 0 $ is a limit ordinal number. Any ordinal number can be represented in the form $ \alpha = \lambda + n $, where $ \lambda $ is a limit ordinal number and $ n $ is an integer, the sum being understood in the sense of addition of order types.

A transfinite sequence of type $ \alpha $, or an $ \alpha $-sequence, is a function $ \phi $ defined on $ \{ \beta \mid \beta < \alpha \} $. If the values of this sequence are ordinal numbers, and if $ \gamma < \beta < \alpha $ implies that $ \phi(\gamma) < \phi(\beta) $, then it is called an ascending sequence. Let $ \phi $ denote a $ \lambda $-sequence, where $ \lambda $ is a limit ordinal number. The least of the ordinal numbers greater than any $ \phi(\gamma) $, where $ \gamma < \lambda $, is called the limit of the sequence $ (\phi(\gamma))_{\gamma < \lambda} $ and is denoted by $ \displaystyle \lim_{\gamma < \lambda} \phi(\lambda) $. For instance, $ \displaystyle \omega = \lim_{n < \omega} n = \lim_{n < \omega} n^{2} $. An ordinal number $ \lambda $ is cofinal to a limit ordinal number $ \alpha $ if and only if $ \lambda $ is the limit of an ascending $ \alpha $-sequence: $ \displaystyle \lambda = \lim_{\xi < \alpha} \phi(\xi) $. The ordinal number $ \mathsf{cf}(\lambda) $ is the least ordinal number to which $ \lambda $ is cofinal.

An ordinal number is called regular if and only if it is not cofinal to any smaller ordinal number, otherwise it is called singular. An infinite ordinal number is called an initial ordinal number of cardinality $ \tau $ if and only if it is the least among the ordinal numbers of cardinality $ \tau $ (i.e., among the order types of well-ordered sets of cardinality $ \tau $). Hence, $ \omega $ is the least initial ordinal number. The initial ordinal number of power $ \tau $ is denoted by $ \omega(\tau) $. The set $ \{ \omega(\delta) \mid \aleph_{0} \leq \delta < \tau \} $ of all initial ordinal numbers of infinite cardinality less than $ \tau $ is well-ordered. If the ordinal number $ \alpha $ is its order type, then one puts $ \omega(\tau) = \omega_{\alpha} $. Therefore, every initial ordinal number is provided with an index equal to the order type of the set of all initial ordinal numbers less than it. In particular, $ \omega_{0} = \omega $. Different indices correspond to different initial ordinal numbers. Each ordinal number $ \alpha $ is the index of some initial ordinal number. If $ \lambda $ is a limit ordinal number, then $ \mathsf{cf}(\lambda) $ is a regular initial ordinal number.

An initial ordinal number $ \omega_{\alpha} $ is called weakly inaccessible if and only if it is regular and its index $ \alpha $ is a limit ordinal number. For instance, $ \omega = \omega_{0} $ is weakly inaccessible, but $ \omega_{\omega} $ is singular and is thus not weakly inaccessible. If $ \alpha > 0 $, then $ \omega_{\alpha} $ is weakly inaccessible if and only if $ \alpha = \omega_{\alpha} = \mathsf{cf}(\alpha) $.

Weakly-inaccessible ordinal numbers allow a classification similar to the classification of inaccessible cardinals (cf. Cardinal number). The sum and the product of two ordinal numbers is an ordinal number. If the set of indices is well-ordered, then the well-ordered sum of ordinal numbers is an ordinal number. One can also introduce the operation of raising to a power, by transfinite induction:

  • $ \gamma^{0} \stackrel{\text{df}}{=} 1 $.
  • $ \gamma^{\xi + 1} \stackrel{\text{df}}{=} \gamma^{\xi} \cdot \gamma $.
  • $ \displaystyle \gamma^{\lambda} \stackrel{\text{df}}{=} \lim_{\xi < \lambda} \gamma^{\xi} $, where $ \lambda $ is a limit ordinal number.

The number $ \gamma^{\alpha} $ is called a power of a number $ \gamma $, where $ \gamma $ is called the base of the power and $ \alpha $ the exponent of the power. For example, if $ \gamma = \omega $ and $ \alpha_{0} = 1 $, then one obtains $$ \alpha_{1} = \gamma^{\alpha_{0}}, \quad \alpha_{2} = \omega^{\omega}, \quad \alpha_{3} = \omega^{\omega^{\omega}}, \quad \ldots. $$ The limit of this sequence, $ \displaystyle \epsilon \stackrel{\text{df}}{=} \lim_{n < \omega} \alpha_{n} $, is the least critical number of the function $ \xi \mapsto \omega^{\xi} $, i.e., the least ordinal number $ \alpha $ among those for which $ \omega^{\alpha} = \alpha $. Numbers $ \alpha $ for which this equality holds are called epsilon-ordinals.

Raising to a power can be used to represent ordinal numbers in a form resembling the decimal representation of positive integers. If $ \gamma > 1 $ and $ 1 \leq \alpha < \gamma^{\eta} $, then there exists a positive integer $ n $ and sequences $ \beta_{1},\ldots,\beta_{n} $ and $ \eta_{1},\ldots,\eta_{n} $ such that \begin{gather} \alpha = \gamma^{\eta_{1}} \cdot \beta_{1} + \cdots + \gamma^{\eta_{n}} \cdot \beta_{n}, \qquad (1) \\ \eta > \eta_{1} > \ldots > \eta_{n}, \qquad 0 \leq \beta_{i} < \gamma, \qquad (2) \end{gather} for $ i \in \{ 1,\ldots,n \} $. Formula (1) for the numbers $ \beta_{j} $ and $ \eta_{j} $ satisfying the conditions in (2) is called the representation of the ordinal number $ \alpha $ in the base $ \gamma $. The numbers $ \beta_{i} $ are called the digits, and the numbers $ \eta_{i} $ the exponents of this representation. The representation of an ordinal number in a given base is unique. The representation of ordinal numbers in the base $ \omega $ is used to define the natural sum and the natural product of ordinal numbers.

References

[1] P.S. Aleksandrov, “Einführung in die Mengenlehre und die Theorie der reellen Funktionen”, Deutsch. Verlag Wissenschaft. (1956). (Translated from Russian)
[2] G. Cantor, “Contributions to the founding of the theory of transfinite numbers”, Dover, reprint (1952). (Translated from German)
[3] F. Hausdorff, “Grundzüge der Mengenlehre”, Leipzig (1914). (Reprinted (incomplete) English translation: Set theory, Chelsea (1978)).
[4] K. Kuratowski, A. Mostowski, “Set theory”, North-Holland (1968).
[5] W. Sierpiński, “Cardinal and ordinal numbers”, PWN (1958).

Comments

The ordinal $ \mathsf{cf}(\lambda) $, the least ordinal number to which $ \lambda $ is cofinal, is called the cofinality of $ \lambda $.

The ordinal number $ \omega $ and (by the axiom of choice) each initial ordinal number with a successor-index are regular. Initial ordinal numbers with a limit-index are singular in general. More precisely, if the axioms of $ \mathsf{ZF} $ are consistent, they remain so after the addition of the axiom that states that all initial ordinal numbers with limit-index $ > 0 $ are singular. Therefore, the axioms of $ \mathsf{ZF} $, if consistent, cannot prove that there are any weakly-inaccessible ordinal numbers other than $ \omega $.

For countable ordinal numbers, see also Descriptive set theory.

References

[a1] K. Kuratowski, “Introduction to set theory and topology”, Pergamon (1972). (Translated from Polish)
[a2] T.J. Jech, “Set theory”, Acad. Press (1978). (Translated from German)
[a3] J. Barwise (ed.), Handbook of mathematical logic, North-Holland (1977). (Especially the article of D.A. Martin on Descriptive set theory).
[a4] A. Levy, “Basic set theory”, Springer (1979).
How to Cite This Entry:
Ordinal number. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Ordinal_number&oldid=15565
This article was adapted from an original article by B.A. Efimov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article