Ordinal notation
Encyclopedia
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
well-order
ing 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.
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).
Thus, define ξ-notations as follows:
ξ 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 (ε=ωε).
ξ(α,β)<ξ(γ,δ) if and only if either (α=γ and β<δ) or (α<γ and β<ξ(γ,δ)) or (α>γ and ξ(α,β)≤δ).
With this definition, the first few ξ-notations are:
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
).
s.
.
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(γ,δ).
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 ≤ ω.
Kleene's
described a system of notation for all recursive ordinals (those less than the Church–Kleene ordinal). It uses a subset of the natural number
s 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 non-computable) set of notations.
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
and set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
, an ordinal notation is a finite sequence of symbols from a finite alphabet which names an ordinal number
Ordinal number
In set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...
according to some scheme which gives meaning to the language.
There are many such schemes of ordinal notations, including schemes by Wilhelm Ackermann
Wilhelm Ackermann
Wilhelm Friedrich Ackermann was a German mathematician best known for the Ackermann function, an important example in the theory of computation....
, Heinz Bachmann, Wilfried Buchholz, Georg Cantor
Georg Cantor
Georg Ferdinand Ludwig Philipp Cantor was a German mathematician, best known as the inventor of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence between the members of two sets, defined infinite and well-ordered sets,...
, Solomon Feferman
Solomon Feferman
Solomon Feferman is an American philosopher and mathematician with major works in mathematical logic.He was born in New York City, New York, and received his Ph.D. in 1957 from the University of California, Berkeley under Alfred Tarski...
, Gerhard Jäger, Isles, Pfeiffer, Wolfram Pohlers, Kurt Schütte
Kurt Schütte
Kurt Schütte was a German mathematician who worked on proof theory and ordinal analysis. The Feferman-Schütte ordinal, which he showed to be the precise ordinal bound for predicativity, is named after him.-References:...
, Gaisi Takeuti
Gaisi Takeuti
is a Japanese mathematician, known for his work in proof theory.After graduating from Tokyo University, he went to Princeton to study under Kurt Gödel.He later became a professor at the University of Illinois at Urbana-Champaign...
(called ordinal diagrams), Oswald Veblen
Oswald Veblen
Oswald Veblen was an American mathematician, geometer and topologist, whose work found application in atomic physics and the theory of relativity. He proved the Jordan curve theorem in 1905.-Life:...
. Given such a scheme, one should be able to define a recursive
Recursive set
In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a given number belongs to the set....
well-order
Well-order
In mathematics, a well-order relation on a set S is a strict total order on S with the property that every non-empty subset of S has a least element in this ordering. Equivalently, a well-ordering is a well-founded strict total order...
ing 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
Stephen Cole Kleene
Stephen Cole Kleene was an American mathematician who helped lay the foundations for theoretical computer science...
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 zero-ary 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 one-to-one. It always gives values larger than its arguments and its range
Range (mathematics)
In mathematics, the range of a function refers to either the codomain or the image of the function, depending upon usage. This ambiguity is illustrated by the function f that maps real numbers to real numbers with f = x^2. Some books say that range of this function is its codomain, the set of all...
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
Solomon Feferman
Solomon Feferman is an American philosopher and mathematician with major works in mathematical logic.He was born in New York City, New York, and received his Ph.D. in 1957 from the University of California, Berkeley under Alfred Tarski...
).
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
"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
The 2-variable Veblen functions 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 ordinalVeblen ordinal
In mathematics, the Veblen ordinal is either of two large countable ordinals:*The small Veblen ordinal*The large Veblen ordinal...
s.
Ackermann
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 ordinalAckermann ordinal
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....
.
Bachmann
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)
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 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
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 Cv(α)
where Cv(α) is the smallest set such that
- Cv(α) contains all ordinals less than Ωv
- Cv(α) is closed under ordinal addition
- Cv(α) 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 
described a system of notation for all recursive ordinals (those less than the Church–Kleene ordinal). It uses a subset of the natural numberNatural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s instead of finite strings of symbols. Unfortunately, unlike the other systems described above there is in general no effective
Computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...
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
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 explicit well-ordered set which represents the...
) of any two given notations in Kleene's
; and given any notation for an ordinal, there is a recursively enumerable setRecursively enumerable set
In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if:...
of notations which contains one element for each smaller ordinal and is effectively ordered. Kleene's
denotes a canonical (and very non-computable) set of notations.