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

No comments: