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{ζ

_{0},ζ

_{0}

^{ζ0},ζ

_{0}

^{ζ0ζ0},...,ζ

_{0}↑↑

*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{ζ

_{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:

Post a Comment