Difference between revisions of "User:Evin-/Draft:Ordinal"
(→The Veblen \phi functions) |
|||
Line 7: | Line 7: | ||
== The Veblen <math>\phi</math> functions == | == The Veblen <math>\phi</math> functions == | ||
Based on the definition of <math>\varepsilon_0</math>, Oswald Veblen in 1908 introduced an ordinal-indexed hierarchy of functions. <math>\phi_0(n)=\omega^n</math> and <math>\phi_k</math> enumerates the common fixed points of <math>\phi_m</math> for all <math>m<k</math>. <math>\phi_1(0)=\varepsilon_0</math>, <math>\phi_2(0)</math> is the smallest ordinal inaccessible from the <math>\varepsilon</math> ordinals. It is called <math>\zeta_0</math>. The set of all ordinals accessible from the <math>\phi</math> functions, addition, multiplication, and exponentiation is well-ordered. It has order type <math>\Gamma_0</math>, the Feferman–Schütte ordinal. It is the first fixed point of the map <math>\alpha\mapsto\phi_\alpha(0)</math>. | Based on the definition of <math>\varepsilon_0</math>, Oswald Veblen in 1908 introduced an ordinal-indexed hierarchy of functions. <math>\phi_0(n)=\omega^n</math> and <math>\phi_k</math> enumerates the common fixed points of <math>\phi_m</math> for all <math>m<k</math>. <math>\phi_1(0)=\varepsilon_0</math>, <math>\phi_2(0)</math> is the smallest ordinal inaccessible from the <math>\varepsilon</math> ordinals. It is called <math>\zeta_0</math>. The set of all ordinals accessible from the <math>\phi</math> functions, addition, multiplication, and exponentiation is well-ordered. It has order type <math>\Gamma_0</math>, the Feferman–Schütte ordinal. It is the first fixed point of the map <math>\alpha\mapsto\phi_\alpha(0)</math>. | ||
+ | |||
+ | == Ordinals 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 <math>\Omega</math> stand for the first uncountable ordinal, though it can be any ordinal which is of the form <math>\varepsilon_k</math> and is greater than all the ordinals we can construct, for example the Church-Kleene ordinal <math>\omega_1^{CK}</math>. Then we define <math>\psi(\alpha)</math> as the smallest ordinal that cannot be expressed from <math>\{0,1,\omega,\Omega\}</math> and using addition, multiplication, exponentiation, and applying the <math>\psi</math> function to ordinals less than <math>\alpha</math>. | ||
+ | |||
+ | === Examples === | ||
+ | Let's calculate <math>\psi(0)</math>. We can get ordinals like <math>1,5,\omega,\omega^2+1,\omega^\omega,\omega^{\omega^\omega},\dotsb</math>. We can also get uncountable ordinals such as <math>\Omega^\Omega,\Omega\omega,\Omega^\omega,\dotsb</math>. The smallest ordinal we can't get is <math>\varepsilon_0</math>. Therefore <math>\psi(0)=\varepsilon_0</math>. <math>\psi(\alpha)=\varepsilon_\alpha</math> holds until the first fixed point of <math>\alpha\mapsto\varepsilon_\alpha</math>, which is <math>\zeta_0</math>. | ||
+ | |||
+ | The function <math>\psi</math> is "stuck" at <math>\zeta_0</math> for all ordinals <math>\zeta_0\le o\le\Omega</math> because <math>\zeta_0</math> can't be constructed from smaller ordinals and <math>\psi</math>. However, since <math>\psi(\Omega)=\zeta_0</math>, for <math>\psi(\Omega+1)</math> we can get <math>\zeta_0</math> by using <math>\psi(\Omega)=\zeta_0</math>. Then <math>\psi(\Omega+1)=\varepsilon_{\zeta_0+1}</math>. | ||
+ | |||
+ | Some large notable ordinals are: | ||
+ | *The Feferman–Schütte ordinal <math>\psi(\Omega^\Omega)</math> | ||
+ | *The Ackermann ordinal <math>\psi(\Omega^{\Omega^2})</math> | ||
+ | *The small Veblen ordinal <math>\psi(\Omega^{\Omega^\omega})</math> | ||
+ | *The large Veblen ordinal <math>\psi(\Omega^{\Omega^2\Omega})</math> | ||
+ | |||
+ | The limit of <math>\psi(\Omega),\psi(\Omega^\Omega),\psi(\Omega^{\Omega^\Omega}),\dotsb</math> is <math>\psi(\varepsilon_{\Omega+1})</math> the Bachmann-Howard ordinal, after it <math>\psi</math> is constant. |
Revision as of 11:05, 5 June 2020
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 .
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 .
Ordinals 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.