Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Ordinal notation
open-in-new
<h2 id="a-simplified-example-using-a-pairing-function">A simplified example using a pairing function</h2> <p>As usual, we must start off with a constant symbol for zero, "0", which we may consider to be a function of <a href="/facts/Arity/zSVuwHvP">arity</a> zero. This is necessary because there are no smaller ordinals in terms of which zero can be described. The most obvious next step would be to define a unary function, "S", which takes an ordinal to the smallest ordinal greater than it; in other words, S is the successor function. In combination with zero, successor allows one to name any natural number. </p><p>The third function might be defined as one that maps each ordinal to the smallest ordinal that cannot yet be described with the above two functions and previous values of this function. This would map β to ω·β except when β is a fixed point of that function plus a finite number in which case one uses ω·(β+1). </p><p>The fourth function would map α to ωω·α except when α is a fixed point of that plus a finite number in which case one uses ωω·(α+1). </p> <h3>ξ-notation</h3> <p>One could continue in this way, but it would give us an infinite number of functions. So instead let us merge the unary functions into a binary function. By <a href="/facts/Transfinite_recursion/XlolgTDl">transfinite recursion</a> on α, we can use transfinite recursion on β to define ξ(α,β) = the smallest ordinal γ such that α < γ and β < γ and γ is not the value of ξ for any smaller α or for the same α with a smaller β. </p><p>Thus, define ξ-notations as follows: </p> <ul><li>"0" is a ξ-notation for zero.</li> <li>If "A" and "B" are replaced by ξ-notations for α and β in "ξAB", then the result is a ξ-notation for ξ(α,β).</li> <li>There are no other ξ-notations.</li></ul> <p>The function ξ is defined for all pairs of ordinals and is one-to-one. It always gives values larger than its arguments and its <a href="/facts/Range_of_a_function/66CeTV6u">range</a> is all ordinals other than 0 and the <a href="/facts/Epsilon_numbers_(mathematics)/t7w8KgA9">epsilon numbers (ε=ωε)</a>. </p><p>One has ξ(α, β) < ξ(γ, δ) if and only if either (α = γ and β < δ) or (α < γ and β < ξ(γ, δ)) or (α > γ and ξ(α, β) ≤ δ). </p><p>With this definition, the first few ξ-notations are: </p> "0" for 0. "ξ00" for 1. "ξ0ξ00" for ξ(0,1)=2. "ξξ000" for ξ(1,0)=ω. "ξ0ξ0ξ00" for 3. "ξ0ξξ000" for ω+1. "ξξ00ξ00" for ω·2. "ξξ0ξ000" for ωω. "ξξξ0000" for ω ω ω . {\displaystyle \omega ^{\omega ^{\omega }}.} <p>In general, ξ(0,β) = β+1. While ξ(1+α,β) = ωωα·(β+k) for k = 0 or 1 or 2 depending on special situations: k = 2 if α is an epsilon number and β is finite. Otherwise, k = 1 if β is a multiple of ωωα+1 plus a finite number. Otherwise, k = 0. </p><p>The ξ-notations can be used to name any ordinal less than ε0 with an alphabet of only two symbols ("0" and "ξ"). If these notations are extended by adding functions that enumerate epsilon numbers, then they will be able to name any ordinal less than the first epsilon number that cannot be named by the added functions. This last property, adding symbols within an initial segment of the ordinals gives names within that segment, is called repleteness (after <a href="/facts/Solomon_Feferman/Bt6DRjuk">Solomon Feferman</a>). </p> <h2 id="list">List</h2> <p>There are many different systems for ordinal notation introduced by various authors. It is often quite hard to convert between the different systems. </p> <h3>Cantor</h3> <p class="note">Main article: <a href="/facts/Cantor_normal_form/satc9FHy">Cantor normal form</a></p> <p>"Exponential polynomials" in 0 and ω gives a system of ordinal notation for ordinals less than <a href="/facts/Epsilon_numbers_(mathematics)/t7w8KgA9">ε0</a>. There are many equivalent ways to write these; instead of exponential polynomials, one can use rooted trees, or nested parentheses, or the system described above. </p> <h3>Veblen</h3> <p class="note">Main article: <a href="/facts/Veblen_function/XzaRJyjr">Veblen function</a></p> <p>The 2-variable Veblen functions (Veblen 1908) can be used to give a system of ordinal notation for ordinals less than the <a href="/facts/Feferman-Schutte_ordinal/dwVhlqz4">Feferman-Schutte ordinal</a>. The Veblen functions in a finite or transfinite number of variables give systems of ordinal notations for ordinals less than the small and large <a href="/facts/Veblen_ordinal_(disambiguation)/R20SlmGj">Veblen ordinals</a>. </p> <h3>Ackermann</h3> <p>Ackermann (1951) described a system of ordinal notation rather weaker than the system described earlier by Veblen. The limit of his system is sometimes called the <a href="/facts/Ackermann_ordinal/QSxRdozk">Ackermann ordinal</a>. </p> <h3>Bachmann</h3> <p>Bachmann (1950) introduced the key idea of using uncountable ordinals to produce new countable ordinals. His original system was rather cumbersome to use as it required choosing a special sequence converging to each ordinal. Later systems of notation introduced by Feferman and others avoided this complication. </p> <h3>Takeuti (ordinal diagrams)</h3> <p>Takeuti (1987) described a system of ordinal notation known as "ordinal diagrams", whose limit is the <a href="/facts/Takeuti%25E2%2580%2593Feferman%25E2%2580%2593Buchholz_ordinal/tsyMFLDB">Takeuti–Feferman–Buchholz ordinal</a>.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> The system was later simplified by Feferman. </p> <h3>Feferman's θ functions</h3> <p>Feferman introduced theta functions, described in Buchholz (1986) as follows. For an ordinal α, θα is a function mapping ordinals to ordinals. Often θα(β) is written as θαβ. The set <i>C</i>(α, β) is defined by induction on α to be the set of ordinals that can be generated from 0, <a href="/facts/First_uncountable_ordinal/Quu6AMEy">ω1</a>, ω2, ..., ωω, together with the ordinals less than β by the operations of ordinal addition and the functions θξ for ξ<α. And the function θγ is defined to be the function enumerating the ordinals δ with δ∉<i>C</i>(γ,δ). The problem with this system is that ordinal notations and collapsing functions are not identical, and therefore this function does not qualify as an ordinal notation. An associated ordinal notation is not known. </p> <h3>Buchholz</h3> <p class="note">Main articles: <a href="/facts/Ordinal_collapsing_function/YEjT7QzV">Ordinal collapsing function</a> and <a href="/facts/Buchholz_psi_functions/yd1UUKyy">Buchholz psi functions § Ordinal notation</a></p> <p>Buchholz (1986) described the following system of ordinal notation as a simplification of Feferman's theta functions. Define: </p> <ul><li>Ωξ = ωξ if ξ > 0, Ω0 = 1</li></ul> <p>The functions ψ<i>v</i>(α) for α an ordinal, <i>v</i> an ordinal at most ω, are defined by induction on α as follows: </p> <ul><li>ψ<i>v</i>(α) is the smallest ordinal not in <i>C</i><i>v</i>(α)</li></ul> <p>where <i>C</i><i>v</i>(α) is the smallest set such that </p> <ul><li><i>C</i><i>v</i>(α) contains all ordinals less than Ω<i>v</i></li> <li><i>C</i><i>v</i>(α) is closed under ordinal addition</li> <li><i>C</i><i>v</i>(α) is closed under the functions ψ<i>u</i> (for <i>u</i>≤ω) applied to arguments less than α.</li></ul> <p>This system has about the same strength as Fefermans system, as θ ε Ω v + 1 0 = ψ 0 ( ε Ω v + 1 ) {\displaystyle \theta \varepsilon _{\Omega _{v}+1}0=\psi _{0}(\varepsilon _{\Omega _{v}+1})} for <i>v</i> ≤ ω. Yet, while this system is powerful, it does not qualify as an ordinal notation. Buchholz did create an associated ordinal notation, yet it is complicated: the definition is in the main article. </p> <h3>Kleene's O</h3> <p class="note">Main article: <a href="/facts/Kleene%2527s_O/Bu8Tlydf">Kleene's O</a></p> <p>Kleene (1938) described a system of notation for all recursive ordinals (those less than the <a href="/facts/Church%25E2%2580%2593Kleene_ordinal/q9l6rzqA">Church–Kleene ordinal</a>). Unfortunately, unlike the other systems described above there is in general no <a href="/facts/Computable_function/dzwBlLGn">effective</a> way to tell whether some natural number represents an ordinal, or whether two numbers represent the same ordinal. However, one can effectively find notations that represent the ordinal sum, product, and power (see <a href="/facts/Ordinal_arithmetic/satc9FHy">ordinal arithmetic</a>) of any two given notations in Kleene's O {\displaystyle {\mathcal {O}}} ; and given any notation for an ordinal, there is a <a href="/facts/Recursively_enumerable_set/lpzr8jHn">recursively enumerable set</a> of notations that contains one element for each smaller ordinal and is effectively ordered. Kleene's O {\displaystyle {\mathcal {O}}} denotes a canonical (and very non-computable) set of notations. It uses a subset of the <a href="/facts/Natural_number/u65og8JE">natural numbers</a> instead of finite strings of symbols, and is not recursive, therefore, once again, not qualifying as an ordinal notation. </p> <h2 id="list-of-limits-of-various-ordinal-notations-and-collapsing-functions">List of limits of various ordinal notations and collapsing functions</h2> Table of limits of various notations and functions<table><tbody><tr><th>Notation</th><th>Supremum of expressible countable ordinals</th></tr><tr><td>Cantor normal form</td><td><a href="/facts/Epsilon_numbers_(mathematics)/t7w8KgA9">Epsilon-naught</a> ε 0 {\displaystyle \varepsilon _{0}} </td></tr><tr><td>Binary Veblen function</td><td><a href="/facts/Feferman%25E2%2580%2593Sch%25C3%25BCtte_ordinal/dwVhlqz4">Feferman-Schütte ordinal</a> Γ 0 {\displaystyle \Gamma _{0}} </td></tr><tr><td>Finitary Veblen function</td><td><a href="/facts/Small_Veblen_ordinal/gEPQRRH4">Small Veblen ordinal</a></td></tr><tr><td>Bird's θ {\displaystyle \theta } function</td><td>Small Veblen ordinal θ ( Ω ω ) {\displaystyle \theta (\Omega ^{\omega })} </td></tr><tr><td>Extended Veblen function</td><td><a href="/facts/Large_Veblen_ordinal/JEr3IrAH">Large Veblen ordinal</a></td></tr><tr><td>Bachmann's ψ {\displaystyle \psi } function</td><td><a href="/facts/Bachmann%25E2%2580%2593Howard_ordinal/JQXh7Mdo">Bachmann–Howard ordinal</a> ψ Ω ( ε Ω + 1 ) {\displaystyle \psi _{\Omega }(\varepsilon _{\Omega +1})} </td></tr><tr><td>Madore's ψ {\displaystyle \psi } function</td><td>Bachmann–Howard ordinal ψ ( ε Ω + 1 ) {\displaystyle \psi (\varepsilon _{\Omega +1})} </td></tr><tr><td>Weiermann's ϑ {\displaystyle \vartheta } function</td><td>Bachmann–Howard ordinal ϑ ( ε Ω + 1 ) {\displaystyle \vartheta (\varepsilon _{\Omega +1})} </td></tr><tr><td>Feferman's θ {\displaystyle \theta } function</td><td><a href="/facts/Takeuti%25E2%2580%2593Feferman%25E2%2580%2593Buchholz_ordinal/tsyMFLDB">Takeuti–Feferman–Buchholz ordinal θ ε Ω ω + 1 ( 0 ) {\displaystyle \theta _{\varepsilon _{\Omega _{\omega }+1}}(0)} </a></td></tr><tr><td>Buchholz's ψ {\displaystyle \psi } function</td><td>Takeuti–Feferman–Buchholz ordinal ψ 0 ( ε Ω ω + 1 ) {\displaystyle \psi _{0}(\varepsilon _{\Omega _{\omega }+1})} </td></tr><tr><td>Rathjen's ψ {\displaystyle \psi } function</td><td> ψ Ω ( χ ε M + 1 ( 0 ) ) {\displaystyle \psi _{\Omega }(\chi _{\varepsilon _{M}+1}(0))} </td></tr><tr><td>Rathjen's Ψ {\displaystyle \Psi } function</td><td>> Ψ ( ε K + 1 ) {\displaystyle \Psi (\varepsilon _{K+1})} </td></tr><tr><td>Stegert's First Ψ {\displaystyle \Psi } function</td><td>> Ψ ( ω + ; P 0 ; ϵ ; ϵ ; 0 ) ε Ξ + 1 {\displaystyle \Psi _{(\omega ^{+};{\mathsf {P}}_{0};\epsilon ;\epsilon ;0)}^{\varepsilon _{\Xi }+1}} <a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a></td></tr><tr><td>Stegert's Second Ψ {\displaystyle \Psi } function</td><td>> Large Stegert ordinal Ψ ( ω + ; P 0 ; ϵ ; ϵ ; 0 ) ε Y + 1 {\displaystyle \Psi _{(\omega ^{+};{\mathsf {P}}_{0};\epsilon ;\epsilon ;0)}^{\varepsilon _{Y}+1}} <a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a></td></tr><tr><td>Taranovsky's C {\displaystyle C} function</td><td>Existence unknown, but recursive and very large</td></tr><tr><td>Kleene's O {\displaystyle {\mathcal {O}}} function</td><td><a href="/facts/Nonrecursive_ordinal/q9l6rzqA">Church-Kleene ordinal</a> ω 1 C K {\displaystyle \omega _{1}^{\mathsf {CK}}} </td></tr><tr><td>Klev's O + {\displaystyle {\mathcal {O}}^{+}} function</td><td>Supremum of writable ordinals λ {\displaystyle \lambda } </td></tr><tr><td>Klev's O + + {\displaystyle {\mathcal {O}}^{++}} function</td><td>Supremum of eventually writable ordinals ζ {\displaystyle \zeta } </td></tr></tbody></table> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Large_countable_ordinals/u0Ea19nd">Large countable ordinals</a></li> <li><a href="/facts/Ordinal_arithmetic/satc9FHy">Ordinal arithmetic</a></li> <li><a href="/facts/Ordinal_analysis/bx5joaVU">Ordinal analysis</a></li></ul> <ul><li>Ackermann, Wilhelm (1951), "Konstruktiver Aufbau eines Abschnitts der zweiten Cantorschen Zahlenklasse", <i>Math. Z.</i>, 53 (5): 403–413, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF01175640">10.1007/BF01175640</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0039669">0039669</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:119687180">119687180</a></li> <li>Bachmann, Heinz (1950), <a href="https://www.ngzh.ch/archiv/1950_95/95_2/95_14.pdf">"Die Normalfunktionen und das Problem der ausgezeichneten Folgen von Ordnungszahlen"</a> (PDF), <i>Vierteljahrsschrift der Naturforschenden Gesellschaft in Zürich</i> (in German), 95: 115–147, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0036806">0036806</a>; English translation by Martin Dowd (2019), <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1903.04609">1903.04609</a></li> <li>Buchholz, W. (1986), "A new system of proof-theoretic ordinal functions", <i>Ann. Pure Appl. Logic</i>, 32 (3): 195–207, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0168-0072%2886%2990052-7">10.1016/0168-0072(86)90052-7</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0865989">0865989</a></li> <li>"Constructive Ordinal Notation Systems" by Fredrick Gass</li> <li>Kleene, S. C. (1938), "On Notation for Ordinal Numbers", <i>The Journal of Symbolic Logic</i>, 3 (4): 150–155, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2267778">10.2307/2267778</a>, <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2267778">2267778</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:34314018">34314018</a></li> <li>"Hyperarithmetical Index Sets In Recursion Theory" by Steffen Lempp</li> <li>Hilbert Levitz, <i><a href="http://www.cs.fsu.edu/~levitz/ords.ps">Transfinite Ordinals and Their Notations: For The Uninitiated</a></i>, expository article, 1999 (8 pages, in <a href="/facts/PostScript/h2XwbcmC">PostScript</a>)</li> <li>Miller, Larry W. (1976), "Normal Functions and Constructive Ordinal Notations", <i>The Journal of Symbolic Logic</i>, 41 (2): 439–459, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2272243">10.2307/2272243</a>, <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2272243">2272243</a></li> <li>Pohlers, Wolfram (1989), <a href="https://archive.org/details/prooftheoryintro0000pohl"><i>Proof theory</i></a>, Lecture Notes in Mathematics, vol. 1407, Berlin: Springer-Verlag, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-540-46825-7">10.1007/978-3-540-46825-7</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-51842-6, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1026933">1026933</a></li> <li>Rogers, Hartley (1987) [1967], <i>The Theory of Recursive Functions and Effective Computability</i>, First MIT press paperback edition, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-262-68052-3</li> <li>Schütte, Kurt (1977), <i>Proof theory</i>, Grundlehren der Mathematischen Wissenschaften, vol. 225, Berlin-New York: Springer-Verlag, pp. xii+299, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-07911-8, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0505313">0505313</a></li> <li>Takeuti, Gaisi (1987), <i>Proof theory</i>, Studies in Logic and the Foundations of Mathematics, vol. 81 (Second ed.), Amsterdam: North-Holland Publishing Co., <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-444-87943-1, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0882549">0882549</a></li> <li>Veblen, Oswald (1908), "Continuous Increasing Functions of Finite and Transfinite Ordinals", <i>Transactions of the American Mathematical Society</i>, 9 (3): 280–292, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F1988605">10.2307/1988605</a>, <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/1988605">1988605</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Rathjen, Michael (1 August 2023). "The Art of Measuring the Strength of Theories". Notices of the American Mathematical Society. 70 (7): 1071–1079 – via White Rose. <a href="https://eprints.whiterose.ac.uk/203713/" target="_blank">https://eprints.whiterose.ac.uk/203713/</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>D. Madore, A Zoo of Ordinals (p.2). Accessed 25 October 2021. <a href="https://www.madore.org/~david/math/ordinal-zoo.pdf" target="_blank">https://www.madore.org/~david/math/ordinal-zoo.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>D. Madore, A Zoo of Ordinals (p.2). Accessed 25 October 2021. <a href="https://www.madore.org/~david/math/ordinal-zoo.pdf" target="_blank">https://www.madore.org/~david/math/ordinal-zoo.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> </ol>