At the conclusion of the previous post, Γ

_{0}, the first impredicative ordinal, and the first defined with a "second-order" definition, was introduced. The remainder of the Γ-sequence was also defined. To find higher countable ordinals, one precedes in a similar manner to previously, by finding fixed points.

For example, the smallest fixed point of α → Γ

_{α}is also the supremum of the set {Γ

_{0},Γ

_{Γ0},Γ

_{ΓΓ0},...}, and is known as the Ackermann ordinal, named after Wilhelm Ackermann, known for his contributions to computation theory.

Again, it becomes useful to have a standard notation for these ordinals, and a generalized form of the Veblen hierarchy is quite useful. To extend the Veblen notation, first we replace what was previously denoted as φ

_{β}(α) with φ(α,β), namely a function of two arguments, the first being what was before the argument, and the second that which was the subscript. To extend the Veblen functions beyond what was already considered, we add a third argument γ, and consider the ordinals defined by expressions of the form φ(α,β,γ). These expressions are evaluated in the following way:

First, φ(α,β,0) = φ(α,β). Then, φ(0,0,1) is defined as the first ordinal that is inaccessible through the expressions φ(α,β), constructing from 0 upward. Since this definition is identical to the one for the Feferman-Schutte orindal, φ(0,0,1) = Γ

_{0}. To become more familiar with the notation, consider these further examples:

φ(0,1,1) = φ

_{Γ0 + 1}(0), or the first fixed point of the first Veblen function after φ

_{Γ0}, φ(0,0,2) is equal to Γ

_{1}, or the second fixed point of φ

_{α}(0) → α. Every increase here in the second argument of the generalized Veblen function represents listing fixed points. Each increase in the third represents another Γ value. For example, φ(0,0,2) = sup{φ(0,0,1),φ(0,φ(0,0,1),1),φ(0,φ(0,φ(0,0,1),1),1),...}, with the second argument β assuming the value of the previous member in each element of the set, until Γ

_{1}is obtained. It is easy to see this is consistent with the previously cited value of Γ

_{1}. All other φ(0,0,γ) can be defined this way, and, continuing from the discussion of Γ

_{0}, which was defined in a second-order fashion, these ordinals have second-order definitions, and are all impredicative.

The smallest ordinal inaccessible from the standard operations on all the ordinals φ(0,0,1), φ(0,0,2), φ(0,0,3), etc. of finite third argument γ, yields a new γ value: ω, the ordinal being written φ(0,0,ω). Of course other values for α and β are also possible, such as φ(1,5,ω) or φ(ε

_{0},Γ

_{3},ω). But of more concern is the third argument, which can increase through more countable values until reaching nested Veblen functions such as φ(0,0,φ(0,0,1)), defining a sequence in which the γ assumes the value of the previous member of the sequence. Having gone as far as possible with three arguments, a

*fourth*is introduced in the following way:

sup(φ(0,0,1),φ(0,0,φ(0,0,1)),φ(0,0,(φ(0,0,φ(0,0,1))),...} = φ(0,0,0,1)

Since φ(0,0,1) = Γ

_{0}, the above equation is exactly the same as sup{Γ

_{0},Γ

_{Γ0},Γ

_{ΓΓ0},...} = φ(0,0,0,1). Additionally, φ(0,0,0,1) is the first fixed point of Γ

_{α}→ α, and, as said above, is also known as the Ackermann ordinal. This ordinal has a "third-order" definition, and is also impredicative by most definitions.

One can go on to define φ(α,β,γ,...,δ) for any finite number of arguments, all of which are limits similar to the example above, and although inaccessible from previous operations, are countable for all countable α,β,γ,...,δ. It becomes inconvenient to deal with so many arguments however, so there is an alternate method to create large countable ordinals with a function of only one argument.

As stated above, it is possible to go still further, by the use of a new kind of function, called an

**ordinal collapsing function**. These functions again use the idea of inaccessibility in their definition, but there is a crucial difference between these and Veblen functions: ordinal collapsing functions assume the existence of an ordinal Ω that is beyond any ordinals that can be constructed with ordinal collapsing functions. This ordinal does not have to be defined in any precise way, but simply is assumed to exist as an upper limit to any ordinal constructed. However, since ordinals generated by ordinal collapsing functions make use of Ω, this definition is impredicative, as it assumes the existence of a larger ordinal to define a smaller.

To construct this function, first consider the set of ordinals

*S*= {0,1,ω,Ω}. The set

*C*(0) is then defined as containing all ordinals that can be constructed through a finite process from 0,1,ω, and Ω using addition, multiplication and exponentiation, including 1, 2, 3, ω, ω

^{ω}, and ω

^{ωω}.

*C*(0) also includes Ω, Ω + 1, Ω

^{Ω}, and others of this type, but these are not as important for the time being.

Now, we denote the smallest ordinal that is not in

*C*(0) as ψ(0) (with the symbol psi, rather than phi for Veblen functions). ψ(0) is then equal to ε

_{0}, the first ordinal that requires infinite steps from ω to construct. Next,

*C*(1) is the set of ordinals constructible from

*S*with addition, multiplication, and exponentiation, and the function ψ|

_{1}, or the ψ function restricted to 1. Such a function can only take as an argument values that are members of 1, namely, only 0 (all ordinals are sets of all previous ordinals). Hence the ordinal ψ(0) = ε

_{0}is a member of

*C*(1), as well as sequences of the normal three operations on it, such as ε

_{0}+ 1, ε

_{0}

^{ε0}, and so on.

The smallest ordinal not in

*C*(1) is written ψ(1), and is equal to ε

_{1}, as no finite sequence of operations from ε

_{0}yields this value. Similarly,

*C*(2) is the set of ordinals accessible from members of

*S*through the normal operations plus ψ|

_{2}. Since 1 is a member of 2, ψ(1) = ε

_{1}is a member of

*C*(2), as is ε

_{0}and any operations on these two ordinals with the other members of

*S*. Preceding recursively,

*C*(α) has as a member all ordinals defined through the three normal operations, and ψ|

_{α}, which has a domain of all ordinals less than α.

ψ(α) is defined as before, and is seen to equal ε

_{α}for all finite α.

But what about when α = ω?

*C*(ω) includes all values taken by ψ|

_{ω}, namely ε

_{0}, ε

_{1}, ε

_{2},..., ε

_{α}, and so on for all finite α, as well as operations upon them. The corresponding ψ(ω) is the clearly ε

_{ω}as this transcends all previous epsilon values and operations on them. Thus the equivalence of ψ(α) and ε

_{α}continues for some infinite values of α. In fact, this equality holds true as long as α is less then or equal to ε

_{α}.

However, in the case of α = ζ

_{0}(for which ε

_{α}= α),

*C*(ζ

_{0}) includes all of the epsilon sequence below ζ

_{0}, but does not contain the ordinal itself, as even applying the function ψ|

_{ζ0}to 0 any finite number of times (producing the sequence ε

_{0}, ε

_{ε0},...) cannot yield ζ

_{0}, and ψ(ζ

_{0}) = ζ

_{0}. α = ζ

_{0}+ 1 presents an interesting case. One would think that the pattern would continue, generating ε

_{ζ0 + 1}as the value for ψ(ζ

_{0}+ 1). However, for this to happen, ζ

_{0}would have to be a member of

*C*(ζ

_{0}), since if this were not the case, ε

_{ζ0 + 1}would not be the smallest ordinal not in

*C*(ζ

_{0}). But, beginning with the set

*S*, it is impossible to construct ζ

_{0}with a finite number of operations. Even though one of the operations available for

*C*(ζ

_{0}) is ψ|

_{ζ0 + 1}, which has ζ

_{0}in its domain and would produce ζ

_{0}, no number of steps from

*S*can produce this value in the first place to plug it into the function! There is therefore no way to obtain ζ

_{0}, and

ψ(ζ

_{0}+ 1) = ζ

_{0}.

By the same logic, ψ(ζ

_{0}+ 2), ψ(ζ

_{0}+ ω), and others are still equal to ζ

_{0}. It may seem that the function is "stuck" at ζ

_{0}, and can produce no higher value. This is where Ω comes in. Consider the set

*C*(Ω). This set is no different from previous ordinals in that it ψ(Ω) = ζ

_{0}. The difference appears when considering

*C*(Ω + 1), as ordinals in this set can be constructed from

*S*using ψ|

_{Ω + 1}along with the other three operations. Since Ω is in

*S*and in the domain of ψ|

_{Ω + 1}, ψ(Ω), that is, ζ

_{0}, is in

*C*(Ω + 1). If not for the addition of Ω to

*S*, this function would cease to increase, and this is the importance of Ω. It also explains the name "ordinal collapsing function", as it takes large ordinals such as Ω, and using a function, "collapses" them into smaller ordinals, in this case ζ

_{0}.

It has been established that ψ(Ω + 1) is larger than ζ

_{0}, but what is it?

*C*(Ω + 1) also includes the usual operations on ζ

_{0}, including iterated exponents such as ζ

_{0}

^{ζ0ζ0}. Clearly the smallest ordinal that cannot be accessed in this way is ε

_{ζ0 + 1}, and this is equal to ψ(Ω + 1). The correlation between the ε and ψ functions continues from there, with ψ(Ω + α) = ε

_{ζ0 + α}for all finite and some infinite values of α, including cases greater than ζ

_{0}. For example, ψ(Ω + ζ

_{0}*2) =

ε

_{ζ0 + ζ0*2}= ε

_{ζ0*3}.

The above trend occurs up to ψ(Ω + ζ

_{1}), but the function ψ|

_{Ω + ζ1}cannot equal ζ

_{1}for any ordinal in its domain, nor can iterated exponentiation generate this value. Thus, ψ(Ω + ζ

_{1}) = ζ

_{1}. The next problem occurs when one reaches ψ(Ω + ζ

_{1}), as the set

*C*(Ω + ζ

_{1}) has the operation ψ|

_{Ω + ζ1 + 1}, which gives ζ

_{1}, but only for the input Ω + ζ

_{1}, and this input cannot be constructed with other operations to plug into the function. Thus, ψ(Ω + ζ

_{1}) = ζ

_{1}. Hence the function is stuck once again, with ψ(Ω + α) being equal to ζ

_{1}for α greater than or equal to ζ

_{1}, but only up to a certain point.

Again, Ω bails us out, or, more precisely, Ω*2. Though ψ(Ω*2) still is ζ

_{1}, Ω*2 can be constructed easily from

*S*, and the set

*C*(Ω*2 + 1) has available the operation ψ|

_{Ω*2 + 1}, which has Ω*2 in its domain, and can produce ζ

_{1}. Through similar logic as above, ψ(Ω*2 + 1) = ε

_{ζ1 + 1}. The general idea continues, with each ψ(Ω*(1 + α) + 1) transcending another ζ ordinal, and yielding ε

_{ζα + 1}(if this formula is unclear, try substituting 0 and 1 for α, which give known values, and serve as examples).

As it turns out, this repetition of multiples of Ω "unsticking" the function continues all the way up to ψ(Ω*η

_{0}), with η

_{0}being the first fixed point of

α → ζ

_{α}. ψ(Ω*η

_{0}) is equal to η

_{0}, as finite iterations of α → ζ

_{α}from 0 give ordinals strictly less then this value. However, ψ(Ω*η

_{0}+ 1) is also η

_{0}, and the function is stuck again, this time all the way until ψ(Ω

^{2}), with ψ(Ω

^{2}+ 1) equal to ε

_{η0 + 1}, the first epsilon ordinal greater than η

_{0}. In fact, further powers of Ω have ψ values corresponding roughly to Veblen functions of two arguments, up to

ψ(Ω

^{Γ0}) = ψ(Ω

^{Ω}) = Γ

_{0}, with the function stuck at Γ

_{0}for all ψ(Ω

^{α}) for Γ

_{0}≤ α ≤ Ω. ψ(Ω

^{Ω}) is then the same as φ(0,0,1) = Γ

_{0}. Multiplying by Ω corresponds to raising the second argument of the Veblen function, and multiplying the exponent of Ω by Ω raises the third argument. For example, ψ(Ω

^{Ω + 1}) is

φ(0,0,2), or Γ

_{1}. More values include:

ψ(Ω

^{Ω2}) = φ(0,0,0,1), or the Ackermann ordinal, ψ(Ω

^{Ω3}) = φ(0,0,0,0,1), and so on, with each ψ(Ω

^{Ωα}) equal to the smallest ordinal requiring α + 2 arguments to represent. Alternatively, each of these is the supremum of all ordinals requiring at most α + 1 arguments to represent. However, the ordinal collapsing function has only yielded ordinals expressible as Veblen functions of finite arguments. Even higher countable ordinals accessible through this function are discussed in the next post.

Sources: http://www.ams.org/journals/tran/1908-009-03/S0002-9947-1908-1500814-9/S0002-9947-1908-1500814-9.pdf, Ordinal Collapsing Function - Wikipedia

## 1 comment:

You did a good job giving accessible explanations up to this point, but I got totally lost somewhere in the ordinal collapsing function. And the following pages only get harder... Guess this is all I'll ever be able to understand without a formal background. :)

Post a Comment