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"
(→‎Ordinals collapsing functions)
 
(5 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
{{User:Evin-/Template:Draft}}
 
'''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, <math>\omega</math>. Ordinals can be added and multiplied. The sum of two ordinals <math>a</math> and <math>b</math> 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 <math>1+\omega=\omega</math>, while <math>\omega+1>\omega</math>.
 
'''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, <math>\omega</math>. Ordinals can be added and multiplied. The sum of two ordinals <math>a</math> and <math>b</math> 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 <math>1+\omega=\omega</math>, while <math>\omega+1>\omega</math>.
  
Line 6: 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>.
+
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>.
 +
 
 +
== 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 <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^\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.

Latest revision as of 13:00, 5 June 2020

Remember this is only a draft. This page is not yet in the Main namespace. Discuss about adding it into the main namespace on the Talk page

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)$.

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 $\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^\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=123886"