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, http://www.ams.org/journals/tran/1908-009-03/S0002-9947-1908-1500814-9/S0002-9947-1908-1500814-9.pdf

Wednesday, March 21, 2012

Infinity: Impredicative Ordinals

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

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 φ(ε03,ω). 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 εα = α), C0) 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 C0), since if this were not the case, εζ0 + 1 would not be the smallest ordinal not in C0). 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 C0) 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

Tuesday, March 13, 2012

Infinity: Larger Countable Ordinals

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

Over the course of the previous post, a plethora of infinite ordinals were introduced, all of which were, somewhat surprisingly, countable. We concluded with the epsilon sequence, a series of ordinals α for which ωα = α, where ω is the set of all finite ordinals, and therefore the smallest infinite ordinal.

It was also discussed that any epsilon sequence member of countable index was itself countable. Therefore, εε0, εε1, εεω, and so on, are countable.

Since εε0 is countable, the epsilon ordinal with this index, namely εεε0, is also countable, and one can continue this recursive process indefinitely. By doing this, one can construct the set {ε0ε0εε0,...}, with each member of the set having a finite number of "ε's". Since there is one and only one member of this set for every positive natural number, it is countable, and again has a countable supremum. This ordinal is sometimes called ζ0 (zeta-naught), and is also defined as the smallest fixed point of the function on ordinals which carries each ordinal α to εα. Hence εζ0 = ζ0.

Ordinals accessed in this way, such as ε0 and ζ0 are values of what are called the Veblen functions, which are functions that generate fixed points of given other functions. In this case, ε0 is a value of the Veblen function on α → ωα and ζ0 a value of the Veblen function on α → εα.

Of course, ζ0 is only the smallest fixed point of the second Veblen function, and is certainly not the end of countable ordinals. ζ0 + 1, ζ0 + 2, ζ0*2, ζ0ω and other normal operations on ζ0 can be defined, eventually leading one to the ordinal εζ0 + 1, which, by the definition of the epsilon sequence is the limit of the sequence εζ0, εζ0εζ0, and so on. However, εζ0 is simply equal to ζ0, so

εζ0 + 1 = sup{ζ00ζ00ζ0ζ0,...,ζ0↑↑n,...}.

Hence this latest ordinal is countable, as are εζ0 + 2, εζ00, and others, eventually leading up to εεζ0 + 1. Being countable, the epsilon ordinal of this index is as well, in addition to any subsequent iterations.

Thus, one can define the countable ordinal sup{ζ0 + 1,εζ0 + 1εζ0 + 1εεζ0 + 1,...}. In the limit, this is clearly another fixed point of the second Veblen function, but it is greater than ζ0, as it incorporates ζ0 + 1 into its definition. It is then the second fixed point of α → εα, and is denoted ζ1. Continuing in this manner, ζ2 = sup{ζ1 + 1,εζ1 + 1εζ1 + 1,...}, where ζ2 is again a fixed point of the above function, i.e. εζ2 = ζ2. Repeating this process, one obtains ζα for any finite α, and, in the limit of these, ζω. For the same reasons as the epsilons, any zeta ordinal of countable index is countable. We then have the countable ordinals ζζ0, ζζζ0, etc., culminating in a new ordinal, namely the smallest fixed point of the function α → ζα, and the smallest value of the Veblen function on this mapping.

Although this ordinal could be written η0 (eta-naught), it becomes useful to have a more standard notation for Veblen functions. To do this, first denote the function α → ωα as φ0. Then, for example, φ0(1) = ω1 = ω, and φ0(3) = ω3. Moving on, the function φ1 is defined as the Veblen function on φ0, and therefore "lists" its fixed points. φ1(0) then means "the first fixed point of α → ωα", which we know to be equal to ε0. φ1(1) is the second fixed point of φ0, which is ε1. It is clear from the definition of the epsilon sequence that φ1(α) = εα. To find subsequent Veblen functions, one uses the recursive scheme φβ' (The Veblen function indexed by the successor of β) = "the function that lists the fixed points of φβ". This series of functions is known as the Veblen hierarchy. Therefore, φ2 lists the fixed points of φ1, and is equivalent to the function α → ζα. Similarly, φ3(0) is the first fixed point of φ2, namely what we briefly referred to as η0.

Any function of the Veblen hierarchy has a domain of the ordinal numbers, with countable arguments generating countable outputs. Using the recursive formula above, the functions φ4, φ5, etc., can be constructed. Another important fact about Veblen functions is that each value taken by one of these functions is taken by all previous functions. In formula form, where α, β, γ, and δ and ordinals,

For all ordinals φβ(α), there exists an ordinal γ for all δ < β such that φβ(α) = φδ(γ)

In other words, each value taken by a function in the Veblen hierarchy is also a fixed point of all previous ones. For example, ζ0 is also a fixed point of α → ωα, as well as of α → εα. Using this fact, φβ(α) can be defined in the case that β is a limit ordinal:

If β is a limit ordinal, then φβ lists the common fixed points of all the functions φδ for all δ < β. For example, φω(0) is the smallest ordinal that is a fixed point of all the functions φ0, φ1, φ2, etc. One can further define the ordinals φε0(0), φζ0(0), and even

φφω(0)(0), φφφω(0)(0)(0), and so on.

All ordinals accessible through the operations of addition, multiplication, exponentiation and the Veblen hierarchy have now been described. Next, we define the ordinal that is the limit of the above ordinals, i.e. the smallest ordinal such that φα(0) = α. It is also described as the first fixed point of
α → φα(0). This ordinal transcends the entire Veblen hierarchy, and it is sometimes called the Feferman-Schutte ordinal. It is written Γ0.

Γ0 has many interesting properties. First and foremost, it is countable, being constructed using Veblen ordinals of countable argument. Also, it is considered by many to be what is called "impredicative", essentially meaning here that it cannot be defined without reference to the totality of the system of ordinals. This is because, unlike all previous ordinals, it depends on a "second-order" definition, namely it is dependent on the Veblen hierarchy, each member of which is a function. In this way, it is constructed through a sort of "meta"-function, i.e. a function on functions. Since functions such as those of the Veblen hierarchy have domains encompassing the system of ordinal numbers, Γ0 makes use of this entire system in its construction, and references all ordinal numbers, including itself. The fundamental point is that the definition that led to Γ0 was of a different nature than all those previously, and is the first of a different class of ordinals, the impredicative ordinals.

Also, by definition of its construction, it is a fixed point of all Veblen functions φβ, where β < Γ0. Hence ωΓ0, εΓ0, ζΓ0, etc. are all equal to Γ0. We use this fact to confirm that

sup(Γ0 + 1,ωΓ0 + 1ωΓ0 + 1,..} = εΓ0 + 1 > Γ0.

Similarly, sup(Γ0 + 1,εΓ0 + 1εΓ0 + 1,...} = ζΓ0 + 1 > Γ0.

Further, φβ0 + 1) can be defined for higher ordinals, eventually leading to φφΓ0 + 1(0)(0). The limit of

φΓ0 + 1(0), φφΓ0 + 1(0)(0),...

is then the second fixed point of φα = α, and, being greater than Γ0, it is denoted Γ1. In the same way, Γ2, Γω, ΓΓ0 can be defined. Being limits involving Veblen functions, these ordinals are also countable. However, these still does not constitute all of the countable ordinals. The trek forward is continued in the next post.

Sources: http://folk.uio.no/herman/incompleteness.pdf, Large Countable Ordinals-Wikipedia

Monday, March 5, 2012

Infinity: Countable Ordinals

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

In the previous posts (here and here), ordinal numbers and basic operations concerning them were introduced. Now, using exponentiation, the ordinal ω2 can be defined. By the definition of exponentiation,

ω2 = ω*ω,

which is greater than any ordinal ω*n, for all natural numbers n, and is therefore greater than ω. ω2 as a set is written {0,1,2,...,ω,ω + 1,...,ω*2,ω*2 + 1,...,ω*3,...,ω*n,...}.

In contrast, consider 2ω, which is the limit of 2n over natural numbers. Clearly, this is just the limit of a sequence of increasing natural numbers, namely ω. Therefore, 2ω = ω. In the same way, one can define further ordinals of the form ωn, and confirm that nω = ω for all natural numbers n.

To prove that ordinals such as ωn are countable, one must use the following theorem:

The union of countably many countable sets is countable. (1)

Besides being a mouthful, this theorem is invaluable in confirming the countability of sets. To see how the theorem works, consider a countable set of countable sets {A,B,C...} (each of A, B, C, etc. is a countable set). Since this set is countable, the sets in this set can be labeled with natural numbers. Each set can then be identified with, and written, as a number, (for clarity, the numbers will be in boldface), with A = 1, B = 2, C = 3, and so on. Since each of these sets individually is countable, the elements of each one can be labeled 1, 2, 3 and so on. For example, the element labeled "1" in set A will be denoted 11. We now construct the following function for labeling the elements of all of the above sets (the first ten values, corresponding to the natural numbers 1-10, are shown)

1→ 11, 2→ 12, 3→ 21, 4→ 13, 5→ 22, 6→ 31, 7→ 14, 8→ 23, 9→ 32, 10→ 41,...

It is easily calculated that the general member m of any set n can be found by the following formula:

((m + n)(m + n - 1))/2 - n + 1→ nm

This formula may seem rather complicated, but the important fact is that for any element of any set in {A,B,C...}, there is exactly one natural number that serves as its "label", and the above sequence is a one-to-one correspondence.

We first observe that ω2 is countable, as it is a union of all sets of the form {ω*n + 0, ω*n + 1,...} for natural n. Each of these is countable, as every set of the above form can be put into a one-to-one correspondence with the natural numbers simply by dropping the ω term from each member, and the set of all these sets is also countable, as there is one for each natural number n. (1) is therefore applicable, and ω2 is countable.

Similarly, one can define a set of sets of the form {(ω2)*n,(ω2)*n + 1,...,(ω2)*n + ω,(ω2)*n + ω + 1,...,(ω2)*n + ω*2,...,(ω2)*n + ω*3,...,(ω2)*n + ω*m,...}. If n = 0, then the set above reduces to ω2. For all other values of n, the set can be put into a one-to-one correspondence with ω2 by dropping the first term. The union of all these sets, with the set of sets being, of course, countable, is ω3.

The above outlines a recursive scheme that confirms that all ωn are countable. The countability of each power of ω allows one to apply (1) to the next power. Therefore, if one repeats this process indefinitely over all natural numbers, the limit is the ordinal ωω, which is again countable, being a limit of countably many countable sets. The property of such a limit being countable is very important to ordinal numbers and will be used often. It is a consequence of the theorem proved above, and will be referred to by (2).

This fact seems at odds with what was previously discussed about cardinal numbers, with 20 being equal to the cardinality of the continuum, which describes a property of uncountable sets. It seems much "easier" in a sense to access uncountable cardinals than it is to describe uncountable ordinals, and it will soon be described just how difficult the latter is.

Continuing from ωω, one can use a similar recursive scheme to show that ωω2, ωω3, and so on, are countable. Remarkably, under the same limiting process, combined with recursion, ωωω, ωωωω, and any larger finite power towers of ω are countable.

At this point, no larger ordinals can be described through the operations of addition, multiplication, and exponentiation directly in terms of ω. We therefore define the ordinal ε0 (epsilon-nought) as the limit of the sequence ω, ωω, ωωω, ωωωω,..., or, more formally, as the smallest ordinal α such that ωα = α. In other words, this ordinal is so large that the two quantities ωε0 and ε0 are indistinguishable. Mathematically, ε0 is also the smallest fixed point of the map α → ωα, i.e. is left unchanged when it is applied.

Remarkably, ε0, despite being extremely large, is still countable! It is the limit of the set {ω, ωω, ωωω, ωωωω,...,ω↑↑n,...}, where ↑↑ represents the hyper4 operator, or iterated exponentiation, which in this case a shorthand for writing "n ω's in the power tower". Since, in this set, n takes only natural number values, the set itself is countable, and ε0 is the limit of countably many countable ordinals, and, by (2), is itself countable.

Of course, ordinals do not end here. One can go on to define ε0 + 1, ε0*2, ε0ω and others. For the same reasons as the corresponding expressions involving ω, these are all countable. One can go to on to define the limit of the set {ε00ε00ε0ε0,...,ε0↑↑n,...} as a new ordinal, ε1. Reviewing the process through which this ordinal was created, one can see that it is a limit of a set of limit ordinals, each of which was itself a limit of a sequence of ordinals! Despite being so far removed from our original ω, it is again countable, by the same logic used for ε0. Also, this is the second fixed point of the map mentioned above, as all ordinals between ε0 and ε1 are not equal to themselves under
α→ ωα, e.g. ωε0 + 1 = ωε0*ω = ε0*ω ≠ ε0 + 1.

Continuing even further, one can define εα for any natural number α. The formula below shows how this is done, with the symbol "sup{}", representing the supremum, or least ordinal greater than or equal to every member, of a set. Essentially, the notation "supremum of a set" is interchangeable with "limit of a sequence", but the former is easier to write. The formula for εα is recursive, using succession to define each member of the epsilon sequence.

εα' = sup{εααεααεαεα,...,εα↑↑n,...}

Since each set in the above equation is countable, and each ordinal involved is countable, the members of the epsilon sequence for finite α are countable. Of course, one can then construct a set of all epsilon ordinals of natural number index α, i.e. {ε012,...,εα,...}. This set is countable, as well as all of its members, and it therefore has a countable supremum, which can be defined as εω. Subsequently,
εω + 1, εω + 2,...,εω*2, and others can be defined. Each of these ordinals, if the subscript of ε is limit ordinal, is simply the supremum of all previous members of the epsilon sequence. Otherwise, the subscript is the successor to some other ordinal, and the formula that was used for ε ordinals of finite indices can be applied.

An important property of the epsilon sequence is that any ordinal in the sequence with a countable index is also countable. This is because, for such an ordinal, the set of all previous members of the epsilon sequence is countable. The reason for this is that they can be easily put into a one-to-one correspondence with a countable set, simply by dropping the "ε", and considering only their indices. For example, εω*2 is the supremum of the set
A = {ε012,...,εωω + 1,...}. A bijection can be constructed from this set to ω*2, namely the one assigning ε0→0, ε1→1, etc., confirming the countability of A and the applicability of (2).

Among the epsilon ordinals of countable index are εωω, εωωω, and even εε0. But where can one go from here? This is still just the beginning of infinite ordinals. More are explored in the next post.

Sources: Axiomatic Set Theory by Patrick Suppes, http://en.wikipedia.org/wiki/Epsilon_nought, Large Numbers at MROB