 Ordinal notation

In mathematical logic and set theory, an ordinal notation is a finite sequence of symbols from a finite alphabet which names an ordinal number according to some scheme which gives meaning to the language.
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. Given such a scheme, one should be able to define a recursive wellordering of a subset of the natural numbers by associating a natural number with each finite sequence of symbols via a Gödel numbering. 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.
Contents
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 zeroary function. 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 which maps each ordinal to the smallest ordinal which 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 together 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:
 "0" is a ξnotation for zero.
 If "A" and "B" are replaced by ξnotations for α and β in "ξAB", then the result is a ξnotation for ξ(α,β).
 There are no other ξnotations.
ξ is defined for all pairs of ordinals and is onetoone. It always gives values larger than its arguments and its range is all ordinals other than 0 and the epsilon numbers (ε=ω^{ε}).
ξ(α,β)<ξ(γ,δ) 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 which enumerate epsilon numbers, then they will be able to name any ordinal less than the first epsilon number which 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).
Systems of ordinal notation
There are many different systems for ordinal notation introduced by various authors. It is often quite hard to convert between the different systems.
Cantor
Main article: Cantor normal form"Exponential polynomials" in 0 and ω gives a system of ordinal notation for ordinals less than epsilon zero. 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
Main article: Veblen functionThe 2variable Veblen functions (Veblen 1908) can be used to give a system of ordinal notation for ordinals less than the FefermanSchutte 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 very powerful system of ordinal notation called "ordinal diagrams", which is hard to understand but was later simplified by Feferman.
Feferman's θ functions
Feferman introduced theta functions, described in Buchholz (1986) as follows. The function for an ordinal α, θ_{α} is a function from 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(γ,δ).
Buchholz
Main article: Ordinal collapsing functionBuchholz (1986) described the following system of ordinal notation as a simplification of Feferman's theta functions. Define:
 Ω_{ξ} = ℵ_{ξ} if ξ > 0, Ω_{0} = 1
The functions ψ_{v}(α) for α an ordinal, v an ordinal at most ω, are defined by induction on α as follows:
 ψ_{v}(α) is the smallest ordinal not in C_{v}(α)
where C_{v}(α) is the smallest set such that
 C_{v}(α) contains all ordinals less than Ω_{v}
 C_{v}(α) is closed under ordinal addition
 C_{v}(α) is closed under the functions ψ_{u} (for u≤ω) applied to arguments less than α.
This system has about the same strength as Fefermans system, as for v ≤ ω.
Kleene's
Main article: Kleene's OKleene (1938) described a system of notation for all recursive ordinals (those less than the Church–Kleene ordinal). It uses a subset of the natural numbers instead of finite strings of symbols. 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 which 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 which contains one element for each smaller ordinal and is effectively ordered. Kleene's denotes a canonical (and very noncomputable) set of notations.
See also
 Large countable ordinals
 Ordinal arithmetic
 Ordinal analysis
References
 Ackermann, Wilhelm (1951), "Konstruktiver Aufbau eines Abschnitts der zweiten Cantorschen Zahlenklasse", Math. Z. 53 (5): 403–413, doi:10.1007/BF01175640, MR0039669
 Buchholz, W. (1986), "A new system of prooftheoretic ordinal functions", Ann. Pure Appl. Logic 32 (3): 195–207, doi:10.1016/01680072(86)900527, MR0865989
 "Constructive Ordinal Notation Systems" by Fredrick Gass
 Kleene, S. C. (1938), "On Notation for Ordinal Numbers", The Journal of Symbolic Logic (The Journal of Symbolic Logic, Vol. 3, No. 4) 3 (4): 150–155, doi:10.2307/2267778, JSTOR 2267778
 "Hyperarithmetical Index Sets In Recursion Theory" by Stephen Lempp
 Hilbert Levitz, Transfinite Ordinals and Their Notations: For The Uninitiated, expository article (8 pages, in PostScript)
 Miller, Larry W. (1976), "Normal Functions and Constructive Ordinal Notations", The Journal of Symbolic Logic (The Journal of Symbolic Logic, Vol. 41, No. 2) 41 (2): 439 to 459, doi:10.2307/2272243, JSTOR 2272243
 Pohlers, Wolfram (1989), Proof theory, Lecture Notes in Mathematics, 1407, Berlin: SpringerVerlag, ISBN 3540518428, MR1026933
 Rogers, Hartley (1987) [1967], The Theory of Recursive Functions and Effective Computability, First MIT press paperback edition, ISBN 9780262680523
 Schütte, Kurt (1977), Proof theory, Grundlehren der Mathematischen Wissenschaften, 225, BerlinNew York: SpringerVerlag, pp. xii+299, ISBN 3540079114, MR0505313
 Takeuti, Gaisi (1987), Proof theory, Studies in Logic and the Foundations of Mathematics, 81 (Second ed.), Amsterdam: NorthHolland Publishing Co., ISBN 0444879439, MR0882549
 Veblen, Oswald (1908), "Continuous Increasing Functions of Finite and Transfinite Ordinals", Transactions of the American Mathematical Society (Transactions of the American Mathematical Society, Vol. 9, No. 3) 9 (3): 280–292, doi:10.2307/1988605, JSTOR 1988605
Categories: Ordinal numbers
 Proof theory
 Mathematical notation
Wikimedia Foundation. 2010.
Look at other dictionaries:
Ordinal collapsing function — In mathematical logic and set theory, an ordinal collapsing function (or projection function) is a technique for defining (notations for) certain recursive large countable ordinals, whose principle is to give names to certain ordinals much larger … Wikipedia
Ordinal analysis — In proof theory, ordinal analysis assigns ordinals (often large countable ordinals) to mathematical theories as a measure of their strength. The field was formed when Gerhard Gentzen in 1934 used cut elimination to prove, in modern terms, that… … Wikipedia
Ordinal number — This article is about the mathematical concept. For number words denoting a position in a sequence ( first , second , third , etc.), see Ordinal number (linguistics). Representation of the ordinal numbers up to ωω. Each turn of the spiral… … Wikipedia
Notation — The term notation can refer to: Contents 1 Written communication 1.1 Biology and Medicine 1.2 Chemistry 1.3 Dance and movement … Wikipedia
Ordinal — Nombre ordinal En linguistique, les mots premier, deuxième, troisième, quatrième, etc. s appellent des adjectifs numéraux ordinaux qui servent à préciser le rang d un objet dans une collection ou l ordre d un événement dans une succession. Cette… … Wikipédia en Français
Ordinal arithmetic — 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… … Wikipedia
Notation complexe — Nombre complexe Pour les articles homonymes, voir complexe. Les nombres complexes forment une extension de l ensemble des nombres réels. Ils permettent notamment de définir des solutions à toutes les équations polynomiales à coefficients réels.… … Wikipédia en Français
Large countable ordinal — 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… … Wikipedia
Recursive ordinal — In mathematics, specifically set theory, an ordinal α is said to be recursive if there is a recursive binary relation R that well orders a subset of the natural numbers and the order type of that ordering is α. It is trivial to check that ω is… … Wikipedia
Set notation — Sets are fundamental objects in mathematics. Intuitively, a set is merely a collection of elements or members . There are various conventions for textually denoting sets. In any particular situation, an author typically chooses from among these… … Wikipedia