User:JRSpriggs/Ordinal notation

From Wikipedia, the free encyclopedia

The following is a write-up of my system of ordinal notations. See also Large countable ordinal, Ordinal notation, and Ordinal collapsing function.

As I said at Talk:Ordinal notation, "An ordinal notation is something which denotes an ordinal, that is, it is a way of naming an ordinal so that we can communicate about them with others and with ourselves.". To this end, I tried to provide a unique notation for as many ordinals as possible. Each ordinal to be described in terms of smaller ordinals, except that a quantifier-like functional is used whose bound variable ranges over larger ordinals.

As described at Ordinal notation#ξ-notation, I begin with a zero-ary function for zero, 0, and a binary pairing function, ξ (α, β), that takes care of all non-zero ordinals except the epsinums (epsilon numbers, i.e. those α for which α = ω^α).

Contents 1 The full system 2 Interpretation of Lambda zero 2.1 Relationship to the Veblen hierarchy 2.2 Relationship to special large countable ordinals 3 Interpretation of Lambda one 4 Inductive hypothesis

[edit] The full system

The full system (which may be inconsistent) is defined here.

The terms are:

• "0" is a term with no free variables.
• If "A" and "B" are replaced by terms, then "ξ (A, B)" is a term. Its set of free variables is the union of the sets of free variables in "A" and "B".
• If "I" is replaced by a term with no free variables, then "Κ_I" is a term whose set of free variables is its own singleton. For example, "Κ₀" is a term whose set of free variables is {Κ₀}. Such a Κ_I is called a "key"; and, in this context, I is called its "index".
• If "I" and "A" are replaced by terms and "I" has no free variables and every "Κ_J" which is free in "A" satisfies "I ≤ J", then "Λ_I (A)" is a term whose set of free variables is the same as that of "A" except that "Κ_I" is excluded. In this context, I is called the "index" of Λ_I (A); and A is called its "code".

There is a (hopefully) total ordering on the terms given by:

• terms have equal value only when they are identical.
• 0 < A unless A is 0.
• ξ (A, B) < ξ (C, D) iff ( A < C and B < ξ (C, D) ) or ( A = C and B < D ) or ( A > C and ξ (A, B) ≤ D ).
• ξ (A, B) < Κ_I iff ( A < Κ_I ) and ( B < Κ_I ).
• ξ (A, B) < Λ_I (C) iff ( A < Λ_I (C) ) and ( B < Λ_I (C) ).
• Κ_I < Κ_J iff J < I. Notice the reversed ordering of these "keys" which is why this cannot be a well-ordering.
• Κ_I < Λ_J (A) iff some Κ_L occurs free in Λ_J (A) for L ≤ I.
• Λ_I (A) < Λ_J (B) iff ( I < J and every I-part of A is < Λ_J (B) ) or ( I = J and A < B and every I-part of A is < Λ_J (B) ) or ( I = J and A > B and Λ_I (A) ≤ some J-part of B ) or ( I > J and Λ_I (A) ≤ some J-part of B ).

where:

• If Κ_I is not free in A, then the I-parts of A are { A }. In particular, the I-parts of Κ_J for I ≠ J are { Κ_J }.
• Otherwise, the I-parts of ξ (A, B) are the union of the I-parts of A and the I-parts of B.
• The I-parts of Κ_I are the empty set { }.
• The I-parts of Λ_J (A) [for J < I, of course] are the I-parts of the J-parts of A.

The (hopefully) well-ordered ordinal notations are those terms which have no free variables.

[edit] Interpretation of Lambda zero

Let the variable Κ₀ range over uncountable regular ordinals.

Define D₀(α) for ordinals α less than (the least epsinum greater than Κ₀) by:

• D₀(α) = α for α less than Κ₀;
• D₀(Κ₀) = 0; and
• D₀(ξ(α,β)) = max(D₀(α),D₀(β)) otherwise.

Let Λ₀(α) be the least ordinal β such that β is an epsinum (neither 0 nor in the range of ξ) and D₀(α) < β and for any γ < α.

Notice that D₀(α) is the maximum of the 0-parts of A when A is a term for the ordinal α.

[edit] Relationship to the Veblen hierarchy

See Veblen function. For α < Κ₀, either or . Remember that ξ (0, α) = α + 1.

More generally, either or for α,β < Κ₀.

[edit] Relationship to special large countable ordinals

v • d • e countable ordinals ω · ε0 · Feferman–Schütte ordinal Γ0 · Ackermann ordinal · small Veblen ordinal · large Veblen ordinal · Bachmann–Howard ordinal · Church–Kleene ordinal ω1CK

ω = ξ(ξ(0,0),0). ε₀ = Λ₀(0).

The Feferman–Schütte ordinal is .

The Ackermann ordinal might be .

The small Veblen ordinal might be .

The large Veblen ordinal might be .

[edit] Interpretation of Lambda one

Let the variable Κ₁ range over uncountable regular ordinals; and let Κ₀ be a larger uncountable regular ordinal (perhaps its successor cardinal).

Define D₁(α) for ordinals α less than the supremum as n goes to ω of Λ₀(Λ₀(...Λ₀(Κ₁)...)) where the function Λ₀ has been applied n times (together with some larger ordinals near Κ₀) by:

• D₁(α) = α for α less than Κ₁;
• D₁(Κ₁) = 0; and
• D₁(Κ₀) = 0; and
• D₁(ξ(α,β)) = max(D₁(α),D₁(β)); and
• D₁(Λ₀(α)) = D₁(α) otherwise.

Let Λ₁(α) be the least ordinal β such that β is an epsinum which is not in the range of Λ₀ and D₁(α) < β and for any γ < α.

Notice that D₁(α) is the maximum of the 1-parts of A when A is a term for the ordinal α.

The Bachmann-Howard ordinal might be Λ₁(0).

[edit] Inductive hypothesis

I seek to show by transfinite induction on ι that the terms for which the value of the indexes are less than ι and the free variables are a subset of some given finite set are well-ordered and that the notations among them have values which constitute a transitive set of ordinals. This will be shown by extending any order-preserving mapping of keys to uncountable regular ordinals to a mapping of said terms to ordinals in an order-preserving way.

The induction is done in an omega-sequence of phases. Phase 0 covers all indexes which can be described with 0 and ξ alone, i.e. those which are less than ε₀. For each natural number n, phase n + 1 uses those new indexes which are values of ordinal notations which use indexes from phase n and earlier phases.