Ordinal notation

From Wikipedia, the free 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: Gaisi Takeuti (called ordinal diagrams), Heinz Bachmann, Oswald Veblen, etc.. Given such a scheme, one should be able to define a recursive well-ordering 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.

1 A simplified example using a pairing function
- 1.1 ξ-notation
2 See also
3 References

[edit] 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, 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).

[edit] ξ-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 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 $\omega^{\omega^{\omega}}.$

In general, ξ(0,β)=β+1. ξ(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 ε₀ 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).

[edit] See also

[edit] References

Larry W. Miller,Normal Functions and Constructive Ordinal Notations,The Journal of Symbolic Logic,volume 41,number 2,June 1976,pages 439 to 459. http://links.jstor.org/sici?sici=0022-4812%28197606%2941%3A2%3C439%3ANFACON%3E2.0.CO%3B2-E