Namespaces
Variants
Actions

Ordinal number

From Encyclopedia of Mathematics
(Redirected from Cofinality)
Jump to: navigation, search

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:
Cofinality. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Cofinality&oldid=51159