Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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 12: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, $\omega$. Ordinals can be added and multiplied. The sum of two ordinals $a$ and $b$ 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 $1+\omega=\omega$, while $\omega+1>\omega$.

Every ordinal characterizes the order type of the ordered ordinals less than it. For example, $0,1,2,\dotsb,\omega$ has order type $\omega+1$.

The smallest ordinal that can't be constructed from $\omega$ by addition, multiplication, and exponentiation is $\varepsilon_0$, the first fixed point of the map $\alpha\mapsto\omega^\alpha$.

The Veblen $\phi$ functions

Based on the definition of $\varepsilon_0$, Oswald Veblen in 1908 introduced an ordinal-indexed hierarchy of functions. $\phi_0(n)=\omega^n$ and $\phi_k$ enumerates the common fixed points of $\phi_m$ for all $m<k$. $\phi_1(0)=\varepsilon_0$, $\phi_2(0)$ is the smallest ordinal inaccessible from the $\varepsilon$ ordinals. It is called $\zeta_0$. The set of all ordinals accessible from the $\phi$ functions, addition, multiplication, and exponentiation is well-ordered. It has order type $\Gamma_0$, the Feferman–Schütte ordinal. It is the first fixed point of the map $\alpha\mapsto\phi_\alpha(0)$.

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 $\Omega$ stand for the first uncountable ordinal, though it can be any ordinal which is of the form $\varepsilon_k$ and is greater than all the ordinals we can construct, for example the Church-Kleene ordinal $\omega_1^{CK}$. Then we define $\psi(\alpha)$ as the smallest ordinal that cannot be expressed from $\{0,1,\omega,\Omega\}$ and using addition, multiplication, exponentiation, and applying the $\psi$ function to ordinals less than $\alpha$.

Examples

Let's calculate $\psi(0)$. We can get ordinals like $1,5,\omega,\omega^2+1,\omega^\omega,\omega^{\omega^\omega},\dotsb$. We can also get uncountable ordinals such as $\Omega^\Omega,\Omega\omega,\Omega^\omega,\dotsb$. The smallest ordinal we can't get is $\varepsilon_0$. Therefore $\psi(0)=\varepsilon_0$. $\psi(\alpha)=\varepsilon_\alpha$ holds until the first fixed point of $\alpha\mapsto\varepsilon_\alpha$, which is $\zeta_0$.

The function $\psi$ is "stuck" at $\zeta_0$ for all ordinals $\zeta_0\le o\le\Omega$ because $\zeta_0$ can't be constructed from smaller ordinals and $\psi$. However, since $\psi(\Omega)=\zeta_0$, for $\psi(\Omega+1)$ we can get $\zeta_0$ by using $\psi(\Omega)=\zeta_0$. Then $\psi(\Omega+1)=\varepsilon_{\zeta_0+1}$.

Some large notable ordinals are:

  • The Feferman–Schütte ordinal $\psi(\Omega^\Omega)$
  • The Ackermann ordinal $\psi(\Omega^{\Omega^2})$
  • The small Veblen ordinal $\psi(\Omega^{\Omega^\omega})$
  • The large Veblen ordinal $\psi(\Omega^{\Omega^2\Omega})$

The limit of $\psi(\Omega),\psi(\Omega^\Omega),\psi(\Omega^{\Omega^\Omega}),\dotsb$ is $\psi(\varepsilon_{\Omega+1})$ the Bachmann-Howard ordinal, after it $\psi$ is constant.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=User:Evin-/Draft:Ordinal&oldid=123878"