Thursday, March 29, 2012

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 ψ1, the value of ψ1(α) being the smallest ordinal that cannot be finitely constructed using addition, multiplication, exponentiation, the original ψ function and ψ1|α, or the ψ1 function restricted to α, these operations beginning from the set T1 = {0,1,...,ω,...,Ω,Ω2}, where Ω2 is an ordinal higher than any of those that will be constructed with the ψ1 function, and consequently, higher than Ω (again, it is not necessary for the definitions of Ω and Ω2 to be in any way precise). Also, T1 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.

ψ1(0) is clearly just εΩ + 1, as ψ1|0 is degenerate and has no values. But since all the ordinals less than Ω are in T1, none of these can be equal to ψ1(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(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 S1 = {0,1,ω,Ω,Ω2} using the operations addition, multiplication, exponentiation, ψ|α, and ψ1.

Note no restriction is necessary on ψ1 in this definition, as ψ1 only produces values strictly greater than Ω, which is in turn greater than any ordinal produced by the ψ function. The outputs of ψ1 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 ψ(ψ1(0) + 2), ψ(ψ1(0) + Ω), and so on, on up to
ψ(ψ1(1)) = ψ(εΩ + 2). Returning to ψ1, ψ1(2) = εΩ + 3, and in general
ψ1(α) = εΩ + 1 + α, for all α up through Ω (with ψ1(Ω) = εΩ*2) and beyond. Each of these can be plugged into the ψ function to yield yet another large countable ordinal, some of which are ψ(ψ11(0))), ψ(ψ111(0)))), and so on. Since each nested ψ1 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 ψ1(α) = α. This ordinal is ζΩ + 1, hence ψ1Ω + 1) = ζΩ + 1.

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

ψ12*2) = ζΩ + 2,
ψ122) = ηΩ + 1, and
ψ1Ω2 + 1),

with the last being the highest value attainable by the ψ1, as the function is constant afterward, in the same fashion as ψ is after εΩ + 1. Therefore,
ψ(ψ1Ω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 ψ2, with ψ2(α) the smallest ordinal not constructible from the set T2 = {0,1,...,ω,...,Ω,...Ω23}, in other words the set that contains all ordinals up to and including Ω2, as well as an additional ordinal Ω3, which is an arbitrary ordinal higher than any value that ψ2 will attain.

ψ2(0) is then equal to ψ(ψ1Ω2 + 1)). The definition of subsequent values of ψ2 is as follows

ψ2(α) is the smallest ordinal inaccessible from the operations of addition, multiplication, exponentiation, ψ, ψ1, and ψ2|α from the set T2.

One then alters the definitions of ψ1, and finally, ψ, analogously in order to admit values such as ψ(ψ12(Ω))), which is far greater than any ψ ordinal yet discussed, but of course considerably less than Ω. One can continue to generalize these functions, defining ψ3, ψ4, 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 ji, is written as ψij. The general definition below is true for all functions ψij (with the original ψ replaced by ψ0 for clarity):

ψij(α) is the smallest ordinal not constructible through a finite series of the operations addition, multiplication, exponentiation, ψ0, ψ1,..., ψi|α, ψi + 1,..., ψj on any elements of the set {0,1,...,ω,...,Ω,...Ω2,...,Ωii + 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 ψ (ψ0) versus its "upgraded" definition incorporating ψ1. 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,

1 comment:

bunga said...

hard to understand :)