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,...}, 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 ζ₀ (zeta-naught), and is also defined as the smallest fixed point of the function on ordinals which carries each ordinal α to ε_α. Hence ε_ζ0 = ζ₀.

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

Of course, ζ₀ is only the smallest fixed point of the second Veblen function, and is certainly not the end of countable ordinals. ζ₀ + 1, ζ₀ + 2, ζ₀*2, ζ₀^ω and other normal operations on ζ₀ 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 ζ₀, so

ε_{ζ0 + 1} = sup{ζ₀,ζ₀^ζ₀,ζ₀^ζ₀ζ₀,...,ζ₀↑↑n,...}.

Hence this latest ordinal is countable, as are ε_{ζ0 + 2}, ε_ζ0*ε0, 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{ζ₀ + 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 ζ₀, as it incorporates ζ₀ + 1 into its definition. It is then the second fixed point of α → ε_α, and is denoted ζ₁. Continuing in this manner, ζ₂ = sup{ζ₁ + 1,ε_{ζ1 + 1},ε_{εζ1 + 1},...}, where ζ₂ is again a fixed point of the above function, i.e. ε_ζ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 η₀ (eta-naught), it becomes useful to have a more standard notation for Veblen functions. To do this, first denote the function α → ω^α as φ₀. Then, for example, φ₀(1) = ω¹ = ω, and φ₀(3) = ω³. Moving on, the function φ₁ is defined as the Veblen function on φ₀, and therefore "lists" its fixed points. φ₁(0) then means "the first fixed point of α → ω^α", which we know to be equal to ε₀. φ₁(1) is the second fixed point of φ₀, which is ε₁. It is clear from the definition of the epsilon sequence that φ₁(α) = ε_α. 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, φ₂ lists the fixed points of φ₁, and is equivalent to the function α → ζ_α. Similarly, φ₃(0) is the first fixed point of φ₂, namely what we briefly referred to as η₀.

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 φ₄, φ₅, 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, ζ₀ 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 φ₀, φ₁, φ₂, 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 Γ₀.

Γ₀ 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, Γ₀ 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 Γ₀ 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 β < Γ₀. Hence ω^Γ₀, ε_Γ0, ζ_Γ0, etc. are all equal to Γ₀. We use this fact to confirm that

sup(Γ₀ + 1,ω^{Γ₀ + 1},ω^{ωΓ₀ + 1},..} = ε_{Γ0 + 1} > Γ₀.

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

Further, φ_β(Γ₀ + 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 Γ₀, it is denoted Γ₁. In the same way, Γ₂, Γ_ω, Γ_Γ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