Ordinal
Ordinals are an extension of the natural numbers. Ordinals can be used to describe the order type of a set. The order type of the natural numbers is the first infinite ordinal, . Ordinals can be added and multiplied. The sum of two ordinals and is the ordinal that describes the order type of a set with order type a concatenated with one of order type b. Warning! Ordinal addition is not commutative. For example , while .
Every ordinal characterizes the order type of the ordered ordinals less than it. For example, has order type .
The smallest ordinal that can't be constructed from by addition, multiplication, and exponentiation is , the first fixed point of the map .
Contents
[hide]The Veblen functions
Based on the definition of , Oswald Veblen in 1908 introduced an ordinal-indexed hierarchy of functions. and enumerates the common fixed points of for all . , is the smallest ordinal inaccessible from the ordinals. It is called . The set of all ordinals accessible from the functions, addition, multiplication, and exponentiation is well-ordered. It has order type , the Feferman–Schütte ordinal. It is the first fixed point of the map .
Ordinal collapsing functions
Ordinal collapsing functions, or OCFs, "collapse" uncountable ordinals to give large countable ordinals. One example is a simplified version of Buchholz's OCF.
First, let stand for the first uncountable ordinal, though it can be any ordinal which is of the form and is greater than all the ordinals we can construct, for example the Church-Kleene ordinal . Then we define as the smallest ordinal that cannot be expressed from and using addition, multiplication, exponentiation, and applying the function to ordinals less than .
Examples
Let's calculate . We can get ordinals like . We can also get uncountable ordinals such as . The smallest ordinal we can't get is . Therefore . holds until the first fixed point of , which is .
The function is "stuck" at for all ordinals because can't be constructed from smaller ordinals and . However, since , for we can get by using . Then .
Some large notable ordinals are:
- The Feferman–Schütte ordinal
- The Ackermann ordinal
- The small Veblen ordinal
- The large Veblen ordinal
The limit of is the Bachmann-Howard ordinal, after it is constant.
Ordinal analysis
In modern mathematics, ordinals have been used to measure the strengths of various system. For example the ordinal strength of Peano arithmetic is , which makes it one of the weakest systems studied in mathematics! Kripke–Platek set theory, a weakened form of Zermelo-Fraenkel set-theory, has ordinal strength equal to the Bachmann-Howard ordinal. Zermelo-Fraenkel set theory itself has an unknown ordinal strength.
Ordinal strengths can be used to show that certain statements are unprovable in certain systems. For example, the Kirby-Paris hydra theorems requires induction on the Bachmann-Howard ordinal, which means it is unprovable in Kripke-Platek set theory and Peano arithmetic. As another example, consider Gabriel Nivasch's fusible numbers [1], defined by and if and then . Since has order type , statements like "For every there is a unique smallest and ."
References
- Jeff Erickson, Gabriel Nivasch, Juyan Xu (2003): "Fusible numbers and Peano arithmetic" arXiv:2003.14342v2