Ordinal notation

Last updated • 7 min readFrom Wikipedia, The Free Encyclopedia

In mathematical logic and set theory, an ordinal notation is a partial function mapping the set of all finite sequences of symbols, themselves members of a finite alphabet, to a countable set of ordinals. A Gödel numbering is a function mapping the set of well-formed formulae (a finite sequence of symbols on which the ordinal notation function is defined) of some formal language to the natural numbers. This associates each well-formed formula with a unique natural number, called its Gödel number. If a Gödel numbering is fixed, then the subset relation on the ordinals induces an ordering on well-formed formulae which in turn induces a well-ordering on the subset of natural numbers. A recursive ordinal notation must satisfy the following two additional properties:

Contents

  1. the subset of natural numbers is a recursive set
  2. the induced well-ordering on the subset of natural numbers is a recursive relation

There are many such schemes of ordinal notations, including schemes by Wilhelm Ackermann, Heinz Bachmann, Wilfried Buchholz, Georg Cantor, Solomon Feferman, Gerhard Jäger, Isles, Pfeiffer, Wolfram Pohlers, Kurt Schütte, Gaisi Takeuti (called ordinal diagrams), Oswald Veblen. Stephen Cole Kleene has a system of notations, called Kleene's O, which includes ordinal notations but it is not as well behaved as the other systems described here.

Usually one proceeds by defining several functions from ordinals to ordinals and representing each such function by a symbol. In many systems, such as Veblen's well known system, the functions are normal functions, that is, they are strictly increasing and continuous in at least one of their arguments, and increasing in other arguments. Another desirable property for such functions is that the value of the function is greater than each of its arguments, so that an ordinal is always being described in terms of smaller ordinals. There are several such desirable properties. Unfortunately, no one system can have all of them since they contradict each other.

A simplified example using a pairing function

As usual, we must start off with a constant symbol for zero, "0", which we may consider to be a function of arity 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.

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

The fourth function would map α to ωω·α except when α is a fixed point of that plus a finite number in which case one uses ωω·(α+1).

ξ-notation

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 transfinite recursion 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 β.

Thus, define ξ-notations as follows:

The function ξ is defined for all pairs of ordinals and is one-to-one. It always gives values larger than its arguments and its range is all ordinals other than 0 and the epsilon numbers (ε=ωε).

One has ξ(α, β) < ξ(γ, δ) if and only if either (α = γ and β < δ) or (α < γ and β < ξ(γ, δ)) or (α > γ and ξ(α, β) ≤ δ).

With this definition, the first few ξ-notations are:

"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

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.

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 Solomon Feferman).

List

There are many different systems for ordinal notation introduced by various authors. It is often quite hard to convert between the different systems.

Cantor

"Exponential polynomials" in 0 and ω gives a system of ordinal notation for ordinals less than ε0. 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.

Veblen

The 2-variable Veblen functions ( Veblen 1908 ) can be used to give a system of ordinal notation for ordinals less than the Feferman-Schutte ordinal. The Veblen functions in a finite or transfinite number of variables give systems of ordinal notations for ordinals less than the small and large Veblen ordinals.

Ackermann

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 Ackermann ordinal.

Bachmann

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.

Takeuti (ordinal diagrams)

Takeuti (1987) described a system of ordinal notation known as "ordinal diagrams", whose limit is the Takeuti–Feferman–Buchholz ordinal. [1] The system was later simplified by Feferman.

Feferman's θ functions

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 C(α, β) is defined by induction on α to be the set of ordinals that can be generated from 0, ω1, ω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 δC(γ,δ). 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.

Buchholz

Buchholz (1986) described the following system of ordinal notation as a simplification of Feferman's theta functions. Define:

The functions ψv(α) for α an ordinal, v an ordinal at most ω, are defined by induction on α as follows:

where Cv(α) is the smallest set such that

This system has about the same strength as Fefermans system, as for vω. 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.

Kleene's O

Kleene (1938) described a system of notation for all recursive ordinals (those less than the Church–Kleene ordinal). Unfortunately, unlike the other systems described above there is in general no effective 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 ordinal arithmetic) of any two given notations in Kleene's ; and given any notation for an ordinal, there is a recursively enumerable set of notations that contains one element for each smaller ordinal and is effectively ordered. Kleene's denotes a canonical (and very non-computable) set of notations. It uses a subset of the natural numbers instead of finite strings of symbols, and is not recursive, therefore, once again, not qualifying as an ordinal notation.

List of limits of various ordinal notations and collapsing functions

Table of limits of various notations and functions
NotationSupremum of expressible countable ordinals
Cantor normal form Epsilon-naught
Binary Veblen function Feferman-Schütte ordinal
Finitary Veblen function Small Veblen ordinal
Bird's functionSmall Veblen ordinal
Extended Veblen function Large Veblen ordinal
Bachmann's function Bachmann–Howard ordinal
Madore's functionBachmann–Howard ordinal
Weiermann's functionBachmann–Howard ordinal
Feferman's function Takeuti–Feferman–Buchholz ordinal
Buchholz's functionTakeuti–Feferman–Buchholz ordinal
Rathjen's function
Rathjen's function>
Stegert's First function> [2]
Stegert's Second function> Large Stegert ordinal [2]
Taranovsky's functionExistence unknown, but recursive and very large
Kleene's function Church-Kleene ordinal
Klev's functionSupremum of writable ordinals
Klev's functionSupremum of eventually writable ordinals

See also

Related Research Articles

<span class="mw-page-title-main">Limit ordinal</span> Infinite ordinal number class

In set theory, a limit ordinal is an ordinal number that is neither zero nor a successor ordinal. Alternatively, an ordinal λ is a limit ordinal if there is an ordinal less than λ, and whenever β is an ordinal less than λ, then there exists an ordinal γ such that β < γ < λ. Every ordinal number is either zero, or a successor ordinal, or a limit ordinal.

In the mathematical field of set theory, ordinal arithmetic describes the three usual operations on ordinal numbers: addition, multiplication, and exponentiation. Each can be defined in essentially two different ways: either by constructing an explicit well-ordered set that represents the result of the operation or by using transfinite recursion. Cantor normal form provides a standardized way of writing ordinals. In addition to these usual ordinal operations, there are also the "natural" arithmetic of ordinals and the nimber operations.

In mathematics, the epsilon numbers are a collection of transfinite numbers whose defining property is that they are fixed points of an exponential map. Consequently, they are not reachable from 0 via a finite series of applications of the chosen exponential map and of "weaker" operations like addition and multiplication. The original epsilon numbers were introduced by Georg Cantor in the context of ordinal arithmetic; they are the ordinal numbers ε that satisfy the equation

Gentzen's consistency proof is a result of proof theory in mathematical logic, published by Gerhard Gentzen in 1936. It shows that the Peano axioms of first-order arithmetic do not contain a contradiction, as long as a certain other system used in the proof does not contain any contradictions either. This other system, today called "primitive recursive arithmetic with the additional principle of quantifier-free transfinite induction up to the ordinal ε0", is neither weaker nor stronger than the system of Peano axioms. Gentzen argued that it avoids the questionable modes of inference contained in Peano arithmetic and that its consistency is therefore less controversial.

In the mathematical discipline of set theory, there are many ways of describing specific countable ordinals. The smallest ones can be usefully and non-circularly expressed in terms of their Cantor normal forms. Beyond that, many ordinals of relevance to proof theory still have computable ordinal notations. However, it is not possible to decide effectively whether a given putative ordinal notation is a notation or not ; various more-concrete ways of defining ordinals that definitely have notations are available.

In proof theory, ordinal analysis assigns ordinals to mathematical theories as a measure of their strength. If theories have the same proof-theoretic ordinal they are often equiconsistent, and if one theory has a larger proof-theoretic ordinal than another it can often prove the consistency of the second theory.

In mathematics, particularly set theory, non-recursive ordinals are large countable ordinals greater than all the recursive ordinals, and therefore can not be expressed using recursive ordinal notations.

In mathematics, the Feferman–Schütte ordinal (Γ0) is a large countable ordinal. It is the proof-theoretic ordinal of several mathematical theories, such as arithmetical transfinite recursion. It is named after Solomon Feferman and Kurt Schütte, the former of whom suggested the name Γ0.

In set theory and computability theory, Kleene's is a canonical subset of the natural numbers when regarded as ordinal notations. It contains ordinal notations for every computable ordinal, that is, ordinals below Church–Kleene ordinal, . Since is the first ordinal not representable in a computable system of ordinal notations the elements of can be regarded as the canonical ordinal notations.

In mathematics, the small Veblen ordinal is a certain large countable ordinal, named after Oswald Veblen. It is occasionally called the Ackermann ordinal, though the Ackermann ordinal described by Ackermann (1951) is somewhat smaller than the small Veblen ordinal.

In mathematics, the large Veblen ordinal is a certain large countable ordinal, named after Oswald Veblen.

In mathematics, the Veblen functions are a hierarchy of normal functions, introduced by Oswald Veblen in Veblen (1908). If φ0 is any normal function, then for any non-zero ordinal α, φα is the function enumerating the common fixed points of φβ for β<α. These functions are all normal.

In mathematics, the Ackermann ordinal is a certain large countable ordinal, named after Wilhelm Ackermann. The term "Ackermann ordinal" is also occasionally used for the small Veblen ordinal, a somewhat larger ordinal.

In mathematical logic and set theory, an ordinal collapsing function is a technique for defining certain recursive large countable ordinals, whose principle is to give names to certain ordinals much larger than the one being defined, perhaps even large cardinals, and then "collapse" them down to a system of notations for the sought-after ordinal. For this reason, ordinal collapsing functions are described as an impredicative manner of naming ordinals.

In computability theory, computational complexity theory and proof theory, a fast-growing hierarchy is an ordinal-indexed family of rapidly increasing functions fα: NN. A primary example is the Wainer hierarchy, or Löb–Wainer hierarchy, which is an extension to all α < ε0. Such hierarchies provide a natural way to classify computable functions according to rate-of-growth and computational complexity.

<span class="mw-page-title-main">Ordinal number</span> Generalization of "n-th" to infinite cases

In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals aimed to extend enumeration to infinite sets.

This is a glossary of terms and definitions related to the topic of set theory.

Buchholz's psi-functions are a hierarchy of single-argument ordinal functions introduced by German mathematician Wilfried Buchholz in 1986. These functions are a simplified version of the -functions, but nevertheless have the same strength as those. Later on this approach was extended by Jäger and Schütte.

In the mathematical fields of set theory and proof theory, the Takeuti–Feferman–Buchholz ordinal (TFBO) is a large countable ordinal, which acts as the limit of the range of Buchholz's psi function and Feferman's theta function. It was named by David Madore, after Gaisi Takeuti, Solomon Feferman and Wilfried Buchholz. It is written as using Buchholz's psi function, an ordinal collapsing function invented by Wilfried Buchholz, and in Feferman's theta function, an ordinal collapsing function invented by Solomon Feferman. It is the proof-theoretic ordinal of several formal theories:

In set theory, a mathematical discipline, a fundamental sequence is a cofinal sequence of ordinals all below a given limit ordinal. Depending on author, fundamental sequences may be restricted to ω-sequences only or permit fundamental sequences of length . The element of the fundamental sequence of is commonly denoted , although it may be denoted or . Additionally, some authors may allow fundamental sequences to be defined on successor ordinals. The term dates back to Veblen's construction of normal functions , while the concept dates back to Hardy's 1904 attempt to construct a set of cardinality .

References

  1. 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.
  2. 1 2 D. Madore, A Zoo of Ordinals (p.2). Accessed 25 October 2021.