10
$\begingroup$

I am trying to understand the Veblen hierarchy but I still find it confusing. The Feferman–Schütte ordinal, $\Gamma_0$, can be described as the set of all ordinals that can be written as finite expressions, starting from zero, using only the Veblen hierarchy and addition. The Veblen hierarchy starts with the function $\omega^\alpha$ and uses recursion to generate larger and larger functions. But I am not sure why we start with $f(\alpha)=\omega^\alpha$, or why we restrict the definition of $\Gamma_0$ to Veblen hierarchy and addition. Would we obtain recursive ordinals larger than $\Gamma_0$ if we start the hierarchy with some faster growing function? For instance we can use hyperoperators to define $f(\alpha)=(\alpha\uparrow ^\alpha \alpha)^{(\alpha)}$ (where the upperscript $(\alpha)$ means $\alpha$-times composition) which is immensely huge. We could also include this new hierarchy plus addition and any hyperoperator to define the limit $\Gamma_0$. But it is not clear to me if doing it this way results in the same $\Gamma_0$, or in a larger (but still predicative?) one.

$\endgroup$
  • 2
    $\begingroup$ $\Gamma_0$ has the property that whenever you pick ordinals $\alpha < \Gamma_0$ and $\beta < \Gamma_{0},$ then the hyper-operation of $\alpha$'th order applied to $\beta$ will be less than $\Gamma_{0}.$ That is, to reach $\Gamma_0$ by applying a hyper-operation of some transfinite order to a transfinite ordinal, you need to have at least one of these transfinite's reach $\Gamma_{0}.$ To make this precise we would have to define these hyper-operations, including those having limit ordinal orders (an Ackermann function type of double recursion of the lower orders handles a limit ordinal order). $\endgroup$ – Dave L. Renfro May 10 '13 at 21:02
  • $\begingroup$ @DaveL.Renfro Thanks, you should put this as an answer! Do you have any textbook or reference where I can see a detailed proof of this? $\endgroup$ – Wolphram jonny May 11 '13 at 6:37
9
$\begingroup$

This is mostly a more extended version of my comment. As for a book or published paper where $\Gamma_0$ is carefully and rigorously obtained, probably the best I know of is:

Wolfram Pohlers, Proof Theory. The First Step into Impredicativity, 2008.

However, the audience and goals of Pohlers' book are quite distant (in my opinion) from the basic ideas behind normal functions on ordinals and fixed-points of normal functions, which I think have not had enough exposition about in the mathematical literature. For example, pick up any of the dozens of introductory set theory books and many more related books (in real analysis, topology, etc.) in which ordinals are discussed, and you'll see nearly identical discussions of how the countable ordinals include $\epsilon_0$ and beyond (but no author seems to vary on this and indicate, even if briefly, some of the interesting things that lie in the "and beyond" realm), and if you pick up any of the more advanced books and papers in set theory and in proof theory where large countable ordinals are discussed, you're in for a whirlwind ride in which $\epsilon_0$ and $\Gamma_0$ are barely mentioned as bacteria on a microscope slide in the quest to reach the distant quasars of ever more exotic recursive ordinal notations, which are cryptically pitched to an audience of a few specialists. There seem to be no middle-ground expositions of this topic.

Maybe A short introduction to Ordinal Notations by Harold Simmons comes close to being a middle-ground exposition.

However, I think much better is the following, which is not written with applications of large ordinals to proof theory as its end goal. Instead, the focus is on the ride up through the ordinals.

John Baez, This Week's Finds in Mathematical Physics (Week 236; 26 July 2006)

Also, look up diagonal intersection. I believe this is the operation that takes you from ordinals defined via the $\alpha$'th order hyper-operation (applied to $\beta$) to $\Gamma_{0}.$

Finally, below are some things I've posted elsewhere that may be of use. Incidentally, I never continued the treatment of ordinal numbers I began in the first post below, as I wound up getting busy at work. I also started to think that it wasn't such a good idea to spend so much time preparing ASCII expositions of things that I had planned to write up more formally in LaTeX and distribute in some manner (publication, math arXiv site, or perhaps just toss out like I did with this).

Renfro, ORDINAL NUMBERS #1, sci.math, 29 October 2006. [Last version of this essay. See the discussion at the end concerning ${\omega}^{\omega}$ being simultaneously the ${\omega}^{\omega}$'th ordinal and the ${\omega}^{\omega}$'th limit ordinal.]

Renfro, Transfinite Aleph and Beth ordinal sequences, sci.math, 23 November 2003.

Renfro, fixed points with ordinal maps, sci.math, 30 November 2008. [See also the follow-up on 2 December 2008.]

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Another excellent reference on $\Gamma_0$ is the survey paper: Jean H. Gallier. What's so special about Kruskal's theorem and the ordinal $\Gamma_0$? A survey of some results in proof theory, Ann. Pure Appl. Logic 53 (3), (1991), 199-260. Also, Erratum, Ann. Pure Appl. Logic 89 (2-3), (1997), 275. $\endgroup$ – Andrés E. Caicedo May 12 '13 at 4:54
  • 1
    $\begingroup$ For those who might be interested, sometime in the next few days or so (certainly within two weeks from now) I'll step up to the plate so to speak and post some results I worked out back in 1990 or 1991 that fit the middle-ground exposition I complained is most absent. Specifically, I'll post (mostly without proofs) the things I brought up in this post. $\endgroup$ – Dave L. Renfro May 12 '13 at 17:19
  • $\begingroup$ Dave, I am very interested! Would you please add a link here once the post is available? $\endgroup$ – Andrés E. Caicedo May 13 '13 at 19:18
  • $\begingroup$ @Andres Caicedo: I'll be posting this in math StackExchange. One of the reasons I never got around to writing it up in sci.math (besides those I mentioned in the post I cited in my earlier comment) is that ASCII was so tedious and provided such limited readability for others that I just didn't feel the effort was worth it. However, the situation here is different. I've already spent a couple of hours today (early morning hours before work) beginning it, and it looks nice so far. I'll give an example in another comment, as I don't have room left in this one. $\endgroup$ – Dave L. Renfro May 13 '13 at 19:49
  • $\begingroup$ ordinal tetration (base case) $\;\; \sideset{_{}^0}{}\alpha = 1$ (successor case) $\;\; \sideset{_{}^{\beta + 1}}{}\alpha \; = \; \left(\sideset{_{}^{\beta}}{}\alpha \right)^{\alpha}\;$ if $\beta \geq 1$ (limit case) $\;\; \sideset{_{}^{\lambda}}{}\alpha \; = \; \sup \left\{\sideset{_{}^{\beta}}{}{\alpha}: \; \beta < \lambda \right\}\;$ if $\lambda$ is a nonzero limit ordinal Reader Exercise $\;\; \sideset{_{}^{\epsilon_0}}{}{\epsilon_0} \; = \; {\omega}^{{\omega}^{{\omega}^{{\epsilon}_0 \cdot 2}}} $ (Not the same as usual tetration when finite ordinals are used, however.) $\endgroup$ – Dave L. Renfro May 13 '13 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.