1
$\begingroup$

If I define: $$ φ'_0(x)=1+x $$ Enumerating the fixed points of $φ'_0(x)$, one would get: $$ φ_1'(0)=ω φ_1'(1)=ω+1 \cdots φ_1'(ω)=ω+ω \cdots $$ Which is identical to: $$ φ_1'(x)=ω+x $$ The next several levels seem to give us: $$ φ'_2(x)=ω⋅x φ'_3(x)=\mathbf{φ_0(x)=ω^x} φ_4'(x)=ε_x \cdots $$ So basically, $φ'_3(x) = φ_0(x)$.

Is this version of the Veblen hierarchy correct? If so, why does the Veblen hierarchy start with $ω^x$? It seems that starting it with $1+x$ is a lot more meaningful.

$\endgroup$
  • $\begingroup$ Why would starting with $1+x$ be more meaningful? $\endgroup$ – Noah Schweber Dec 15 '18 at 18:12
  • $\begingroup$ @NoahSchweber Well, it's arguably the simplest normal function. You can't get it by iterating over the fixed points of any normal function. It also generates the natural numbers. $\endgroup$ – GregRos Dec 15 '18 at 19:08
  • 1
    $\begingroup$ Sure, but I don't really see how that makes it more natural. Remember that the role of the Veblen hierarchy is primarily to analyze fast- and slow-growing hierarchies, proof-theoretic ordinals, and similar objects, and these don't tend to be interesting below the level of powers of $\omega$; it's also frequently useful to restrict attention to the indecomposable ordinals, and these are exactly the ordinals of the form $\omega^\alpha$. $\endgroup$ – Noah Schweber Dec 15 '18 at 19:26
4
$\begingroup$

This is essentially a longer comment. Main reason for posting it here is that posting anything even slightly complicated becomes just too confusing in comments (usually a minor error just carries along without anyway to edit it).

There is typo-issue with what you have written ..... just taking it as it is. Suppose we set $\varphi_{0}(x)=1+x$ as you stated. Then we get $\varphi_{1}(x)=\omega+x$.

However $\varphi_{2}(x)$ won't be equal to $\omega \cdot x$. We will have $\varphi_{2}(x)=\omega^2+x$. Continuing this we should get $\varphi_{3}(x)=\omega^3+x$. And for any $n<\omega$, $\varphi_{n}(x)=\omega^n+x$.

Similarly for $\varphi_{\omega}(x)$ we get $\varphi_{\omega}(x)=\omega^\omega+x$. This simply enumerates the elements that are common to every $\varphi_{n}(x)$ (for $n<\omega$), in the image-set of these functions. Continuing this, it seems we would get $\varphi_{\omega+1}(x)=\omega^{\omega+1}+x$.

The previous values are highly suggestive for the function $x \mapsto \varphi_{x}(0)$ being equal to $\omega^x$. And the fixed point of this will be $\epsilon_0$ as we already know (roughly speaking, this is analogous to $\Gamma_0$ in the original hierarchy).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think this is definitely an answer, not a comment :). I was wrong, and I missed it. However, what you point out is itself intriguing. Just as $\Gamma_0$ requires a hyper level of comprehension than afforded by $\omega^x$ to describe, perhaps $\epsilon$ requires a higher level of comprehension than $1 + x$ can describe. $\endgroup$ – GregRos Dec 18 '18 at 16:27
  • $\begingroup$ There are many aspects to this. I think that many of them can't simply be covered here due to shortage of space. But nevertheless, I think I might write a fairly detailed exposition regarding this topic at "some point" (but maybe not, it's just a thought ..... really depends on motivation). I also want to include proofs for a good percentage of the points that would be covered in such an essay (and this is part of the reason it would be long). But that would just based on my own limited perspective (cont.) $\endgroup$ – SSequence Dec 18 '18 at 18:46
  • $\begingroup$ which doesn't include understanding of many related topics such as collapsing, specifically developed notations and proof-theoretic stuff etc. If I really got down to it, it will probably take three or four months. But due to diversions, if I start writing, I expect around three or four years. My intention is to cover at least till SVO (or possibly LVO). Beyond this, the naive approach, such as the one that I describe simply gets far too tedious to work-out in a smaller time window. (cont.) $\endgroup$ – SSequence Dec 18 '18 at 18:46
  • $\begingroup$ Though ofc, I believe one can find papers which use elegant approaches (which I don't know anything about) and get quite far beyond it. But I think at least the kind of exposition that I am thinking would get the job done in a very limited context, by covering some basic elements of this topic in a self-contained, detailed and easily approachable manner. $\endgroup$ – SSequence Dec 18 '18 at 18:46
  • $\begingroup$ @GregRos But anyway, very briefly, one might note that if one starts with a "reasonable" normal function $x \mapsto \varphi_0(x)$, then the first fixed point of $x \mapsto \varphi_x(0)$ will always be less than $\omega_{CK}$. Even though its "intuitively obvious", I don't know how to prove it without an "explicit construction", which would be very long (and not very clever). By a "reasonable" (just arbitrary phrase I am using) normal function, I mean one where there is fixed computable way (cont.) $\endgroup$ – SSequence Dec 18 '18 at 18:54

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.