Infinity: Extended Collapsing Functions

This is the eleventh post of the Infinity Series. For the first, see here. For all posts, see the Infinity Series Portal.

In the previous post, an ordinal collapsing function was used to access high ordinals. However, all the outputs of the function discussed so far are alternatively expressible as Veblen functions with finite numbers of arguments. It was also seen that ψ(Ω^Ωα) is equal to the supremum of all ordinals that can be represented by an α + 1-argument Veblen function. This continues up to
ψ(Ω^Ωω), the first ordinal requiring infinite arguments to represent in Veblen notation. Being the supremum of countably many countable ordinals, it is countable, and is known as the small Veblen ordinal, though this ordinal is of course nothing near small.

In fact, it is small only when compared to even larger ordinals, such as the large Veblen ordinal, which is equal to ψ(Ω^ΩΩ). Alternatively, this ordinal represents the supremum of all others writable in Veblen notation of infinitely many, but only predicatively many, arguments. In short, since Veblen functions of high numbers of arguments are built off of those with lower numbers of arguments, only predicative ordinals, or those can be defined using lower ordinals alone, can serve as the number of arguments for such a function. Since Ω is clearly larger than any predicative ordinal, ψ(Ω^ΩΩ) is the supremum of the entire system of Veblen notation.

However, the ordinal collapsing function goes still further, defining ψ(Ω^ΩΩΩ), and in general ψ(Ω↑↑n) for finite n. Eventually one reaches the value ψ(ε_{Ω + 1}). The function is finally permanently stuck here, as ε_{Ω + 1} is not constructible from the original set S, and cannot be generated to plug to the ψ function. It is therefore never a member of the set C(α) no matter the value of α. ψ(ε_{Ω + 1}) is known as the Bachmann-Howard ordinal.

To go further using ordinal collapsing functions, we define a second function ψ₁, the value of ψ₁(α) being the smallest ordinal that cannot be finitely constructed using addition, multiplication, exponentiation, the original ψ function and ψ₁|_α, or the ψ₁ function restricted to α, these operations beginning from the set T₁ = {0,1,...,ω,...,Ω,Ω₂}, where Ω₂ is an ordinal higher than any of those that will be constructed with the ψ₁ function, and consequently, higher than Ω (again, it is not necessary for the definitions of Ω and Ω₂ to be in any way precise). Also, T₁ is assumed to contain all ordinals up to and including Ω, although we have no way yet of characterizing these ordinals, and so the definition is once again impredicative.

ψ₁(0) is clearly just ε_{Ω + 1}, as ψ₁|₀ is degenerate and has no values. But since all the ordinals less than Ω are in T₁, none of these can be equal to ψ₁(0), and since the ψ function only produces ordinals less than Ω, the first ordinal that is inaccessible is simply the limit of normal operations on Ω, namely ε_{Ω + 1}. Note that this is not the Bachmann-Howard ordinal, but a much larger indefinite quantity, the Bachmann-Howard ordinal being the ψ function at this value,
ψ(ε_{Ω + 1}). In fact, we cannot even be assured of the countability of ε_{Ω + 1}, due to the vagueness with which Ω was defined. Next,

ψ₁(1) = ε_{Ω + 2},

with the last term being the upper limit of iterated exponentiation on ε_{Ω + 1}. Now we return to the original collapsing function ψ, and modify its definition as follows:

ψ(α) is the first ordinal that cannot be constructed from the set S₁ = {0,1,ω,Ω,Ω₂} using the operations addition, multiplication, exponentiation, ψ|_α, and ψ₁.

Note no restriction is necessary on ψ₁ in this definition, as ψ₁ only produces values strictly greater than Ω, which is in turn greater than any ordinal produced by the ψ function. The outputs of ψ₁ therefore cannot affect which ordinal assumes the value of ψ(α), no matter its domain. This new definition produces values identical to those produced by the old for all ψ(α) such that α ≤ ε_{Ω + 1}, and using the same notation therefore produces no ambiguity. However, ψ(ε_{Ω + 1} + 1) is not equal to the Bachmann-Howard ordinal for this definition, since ε_{Ω + 1} is in C(ε_{Ω + 1} + 1). ψ(ε_{Ω + 1} + 1) is then equal to the next epsilon number after the Bachmann-Howard ordinal, namely

ε_{ψ(ψ1(0)) + 1} = ε_{ψ(εΩ + 1)) + 1}

One can go on through ψ(ψ₁(0) + 2), ψ(ψ₁(0) + Ω), and so on, on up to
ψ(ψ₁(1)) = ψ(ε_{Ω + 2}). Returning to ψ₁, ψ₁(2) = ε_{Ω + 3}, and in general
ψ₁(α) = ε_{Ω + 1 + α}, for all α up through Ω (with ψ₁(Ω) = ε_Ω*2) and beyond. Each of these can be plugged into the ψ function to yield yet another large countable ordinal, some of which are ψ(ψ₁(ψ₁(0))), ψ(ψ₁(ψ₁(ψ₁(0)))), and so on. Since each nested ψ₁ essentially iterates the ε function on Ω + 1, the limit of these expressions yields the first fixed point of such iteration, in other words the first α such that ψ₁(α) = α. This ordinal is ζ_{Ω + 1}, hence ψ₁(ζ_{Ω + 1}) = ζ_{Ω + 1}.

In a situation analogous to the original ψ function, ψ₁ is temporarily stuck at ζ_{Ω + 1}, as ζ_{Ω + 1} requires infinite steps to produce from T₁. ψ₁(α) is then fixed from ζ_{Ω + 1} on up to Ω₂, with ψ₁(Ω₂) still equal to ζ_{Ω + 1}, but ψ₁(Ω₂ + 1) is larger, as the domain of the restricted function ψ₁|_{Ω2 + 1} includes Ω₂, which is in T₁. ψ₁ is developed further in a similar way, a few notable values being

ψ₁(Ω₂*2) = ζ_{Ω + 2},
ψ₁(Ω₂²) = η_{Ω + 1}, and
ψ₁(ε_{Ω2 + 1}),

with the last being the highest value attainable by the ψ₁, as the function is constant afterward, in the same fashion as ψ is after ε_{Ω + 1}. Therefore,
ψ(ψ₁(ε_{Ω2 + 1})) is the highest ordinal accessible by the current definition of ψ, but is still much less than Ω.

Of course, there is no need to stop here. One can introduce a third function ψ₂, with ψ₂(α) the smallest ordinal not constructible from the set T₂ = {0,1,...,ω,...,Ω,...Ω₂,Ω₃}, in other words the set that contains all ordinals up to and including Ω₂, as well as an additional ordinal Ω₃, which is an arbitrary ordinal higher than any value that ψ₂ will attain.

ψ₂(0) is then equal to ψ(ψ₁(ε_{Ω2 + 1})). The definition of subsequent values of ψ₂ is as follows

ψ₂(α) is the smallest ordinal inaccessible from the operations of addition, multiplication, exponentiation, ψ, ψ₁, and ψ₂|_α from the set T₂.

One then alters the definitions of ψ₁, and finally, ψ, analogously in order to admit values such as ψ(ψ₁(ψ₂(Ω))), which is far greater than any ψ ordinal yet discussed, but of course considerably less than Ω. One can continue to generalize these functions, defining ψ₃, ψ₄, and so on, and each time altering all previous definitions accordingly. For natural numbers i and j, the function ψ_i adjusted for all ψ functions up to j, with j ≥ i, is written as ψ_ij. The general definition below is true for all functions ψ_ij (with the original ψ replaced by ψ₀ for clarity):

ψ_ij(α) is the smallest ordinal not constructible through a finite series of the operations addition, multiplication, exponentiation, ψ₀, ψ₁,..., ψ_i|_α, ψ_{i + 1},..., ψ_j on any elements of the set {0,1,...,ω,...,Ω,...Ω₂,...,Ω_i,Ω_{i + 1},...,Ω_j}, where each Ω_k is an arbitrary ordinal larger than any constructible with the function ψ_{k - 1}.

To understand this general definition, a few observations must be made. First, due to the definition of Ω_k, it is higher than any ordinal constructible with the previous ψ function. Therefore, the only restricted function in the definition is the one that is being defined, namely ψ_i, which produces ordinals strictly below Ω_i. Since the other ψ functions stay within their respective ranges also, they cannot (by themselves) produce a value in this range, and cannot directly affect ψ_i(α). Also, the purpose of the value j is simply to identify how "upgraded" each ψ function is, e.g., the difference between the initial definition of ψ (ψ₀) versus its "upgraded" definition incorporating ψ₁. Moreover, the set from which the ordinals are being constructed includes all ordinals up through Ω_i, but afterwards only the Ω ordinals between i and j.

Finally, the purpose of this multitude of functions is merely to plug them back in to ψ in order to generate further values, all of which are still far less than Ω. The limit of these functions is still less than Ω, and is sometimes denoted ψ_ω(0). By the use of fixed points, many more ordinals can be defined in this matter, but the processes involved are identical to those discussed. However, there are still higher countable ordinals, some of which are even beyond the principle of recursion (see the next post).

Sources: Large Countable Ordinals- Wikipedia, http://www.ams.org/journals/tran/1908-009-03/S0002-9947-1908-1500814-9/S0002-9947-1908-1500814-9.pdf