↑ arvau

Wikipedia / Ordinal notation

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 an injective 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:

  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 conflict with each other.

A simplified example using a pairing function

", 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" that 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.

.

.

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

-notations as follows:

  • -notation for zero.

  • .

  • -notations.

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.

when either

  • , or

  • , or

  • .

With this definition, the first few -notations are:

  1. "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 ωω

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

That is:

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 can be used to give a system of ordinal notation for ordinals less than the Feferman–Schütte 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 ordinalss.

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 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 system of ordinal notation known as "ordinal diagrams", whose limit is the Takeuti–Feferman–Buchholz ordinal. The system was later simplified by Feferman.

Feferman's θ functions

Feferman introduced theta functions, described in 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

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 .

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

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; and given any notation for an ordinal, there is a recursively enumerable set 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 a recursive ordinal notation.

List of limits of various ordinal notations and collapsing functions

See also

References