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 14: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, . 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
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