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 "Ordinal"

(Created page with "'''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 o...")
 
(→‎Ordinal analysis)
 
(4 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
'''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 [[addition|added]] and [[multiplication|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>.
  
 
Every ordinal characterizes the order type of the ordered ordinals less than it. For example, <math>0,1,2,\dotsb,\omega</math> has order type <math>\omega+1</math>.
 
Every ordinal characterizes the order type of the ordered ordinals less than it. For example, <math>0,1,2,\dotsb,\omega</math> has order type <math>\omega+1</math>.
Line 25: Line 25:
  
 
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.
 
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.
 +
 +
== 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 <math>\varepsilon_0</math>, 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 <math>\mathcal{F}</math>'' <sup>[[#CITEREF1|<nowiki>[1]</nowiki>]]</sup>, defined by <math>0\in\mathcal{F}</math> and if <math>x\in\mathcal{F}</math> and <math>y\in\mathcal{F}</math> then <math>\frac{x+y+1}{2}\in\mathcal{F}</math>. Since <math>\mathcal{F}</math> has order type <math>\varepsilon_0</math>, statements like "For every <math>x\in\mathcal{F}</math> there is a unique smallest <math>y>x</math> and <math>y\in\mathcal{F}</math>."
 +
 +
== References ==
 +
#<div id="CITEREF1">Jeff Erickson, Gabriel Nivasch, Juyan Xu (2003): "Fusible numbers and Peano arithmetic" [https://arxiv.org/abs/2003.14342 arXiv:2003.14342v2]</div>

Latest revision as of 13:16, 7 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)$.

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.

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 $\varepsilon_0$, 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 $\mathcal{F}$ [1], defined by $0\in\mathcal{F}$ and if $x\in\mathcal{F}$ and $y\in\mathcal{F}$ then $\frac{x+y+1}{2}\in\mathcal{F}$. Since $\mathcal{F}$ has order type $\varepsilon_0$, statements like "For every $x\in\mathcal{F}$ there is a unique smallest $y>x$ and $y\in\mathcal{F}$."

References

  1. Jeff Erickson, Gabriel Nivasch, Juyan Xu (2003): "Fusible numbers and Peano arithmetic" arXiv:2003.14342v2
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Ordinal&oldid=124248"