Consider the Veblen hierarchy, where $\psi_0(x) = \omega^x$ and $\psi_1(x)$ is the x'th fixed point of $\psi_0$, $\psi_2(x)$ is the x'th fixed point of $\psi_1(x)$, and so on.

We eventually get to $\psi_\omega(x)$, which is defined as the x'th ordinal in the intersection of all $\psi_n(x)$ for $n < \omega$ - or the x'th "common fixed point" of all previous Veblen functions.

My question is, do we get the same definition if we simply define it as the supremum? i.e.

$\psi_\omega(x) = \sup \{ \psi_n(x): n < \omega\}$

So we get $\psi_\omega(0)$ is the supremum of all previous "0th" fixed points, $\psi_\omega(1)$ is the supremum of all previous "1st" fixed points, and so on.

If it isn't the same for all $\psi_\omega(x)$, is it at least the same for $\psi_\omega(0)$?

Likewise, I am curious about the equivalence of the above definitions for larger limit ordinals than just $\omega$.


What you have written as $\psi_\omega(x)$, I will write it as $F_\omega(x)$. So your question is that whether $\psi_\omega$ and $F_\omega$ are equal or not? The answer is no, but they are closely related. More specifically, define: $F_\omega(x) = \sup \{ \psi_n(x): n < \omega\}$ while define $\psi_\omega$ as enumeration of common fixed points of $\psi_0$, $\psi_1$, $\psi_2$, $\psi_3$,... etc.

I think that the range of both functions $\psi_\omega$ and $F_\omega$ should be equal. More specifically, if you modify the function $F_\omega$ to remove "repetitions" from it, I think you will exactly get the function $\psi_\omega$. And basically yes, $F_\omega(0)$ and $\psi_\omega(0)$ are both going to be equal.

At least that's what I remember when I was thinking about this topic. But honestly, I would be lying if I said I tried to write the proof. The equality of $F_\omega(0)$ and $\psi_\omega(0)$ should be fairly short I think. But giving the general proof might be fairly longer. I will try to write it fully in case you are interested (I will edit the answer into a longer one in that case).

Another thing is that if we define $\psi_\alpha$ and $F_\alpha$ more generally for limit $\alpha$ (analogous to the case for $\omega$), the same relation between them will carry-over I think. Meaning, once again if you remove the repetitions from $F_\alpha$ you will exactly get the function $\psi_\alpha$.

EDIT: I might probably make a more detailed edit later on, but just to address the specific point you raised in the comments. As I understood, you are saying that how do we know that $range(F_\omega) \subseteq range(\psi_\omega)$ is true.

Well first of all we can observe that $range(\psi_m) \supseteq range(\psi_n)$, whenever we have $m,n \in \omega$ and $m \leq n$. Now consider the definition $F_\omega(a) = \sup \{ \psi_n(a): n < \omega\}$. The $n$-th element $\psi_n(a) \in range(\psi_n)$ obviously. But what is interesting is that for all $n \in \omega$ and $n \geq 0$, we have $\psi_n(a) \in range(\psi_0)$. This is due to the fact that $range(\psi_0) \supseteq range(\psi_n)$ for all $n \in \omega$ and $n \geq 0$.

But now consider $\sup \{ \psi_n(a): n < \omega\}$. Because each individual term $\psi_n(a)$ belongs to $range(\psi_0)$, the supremum of these terms will also belong to $range(\psi_0)$ .... because $\psi_0$ is continuous. Hence we conclude that $F_\omega(a) \in range(\psi_0)$.

Hopefully the above two paragraphs make sense. Because now with fairly similar logic we can conclude that $F_\omega(a) \in range(\psi_1)$ ...... just consider the set $\sup \{ \psi_n(a): n < \omega \,\, and \,\, n \geq 1\}$ [excluding the first term here shouldn't make a difference because the terms $\psi_n(a)$ for given $a$ and variable $n$ are non-decreasing and we are considering the supremum]. Anyway, generalizing this we will get $F_\omega(a) \in range(\psi_i)$ (for all $i \in \omega$). But if we look carefully, we have just shown that some value $F_\omega(a)$ belongs to the range of all the functions $range(\psi_i)$ (where $i<\omega$). Clearly $F_\omega(a)$ is a fixed point of $\psi_0$ (because $F_\omega(a) \in range(\psi_1$)). By similar logic, $F_\omega(a)$ is a fixed point of all $\psi_i$'s where $i<\omega$. Hence we conclude that $F_\omega(a) \in range(\psi_\omega)$. Since the choice of value $a$ was arbitrary, we conclude that $range(F_\omega) \subseteq range(\psi_\omega)$.

  • $\begingroup$ I am somewhat interested - I can see how the range of $F_\omega(x)$ will be at least a superset of $\psi_\omega(x)$. I don't understand how to prove that there is no $x$ such that the set $\{\psi_n(x): n<\omega\}$ has no supremum below the next fixed point though. $\endgroup$ – Mike Battaglia Feb 14 at 2:37
  • $\begingroup$ @MikeBattaglia I will try to add some details some time later (though I would be happy if someone else did it), but intuitively, here is how it goes. Excluding a few exceptional cases, the function $F_{\omega}(x)$ will be non-decreasing but will stay constant for large stretches. However, it will be continuous and its range will equal range of $\psi_\omega(x)$. So when we remove the repetitions from the function $F_{\omega}$ we recover the function $\psi_\omega$. To be more concrete, for $0 \leq x \leq \psi_\omega(0)$, we have $F_{\omega}(x)=\psi_\omega(0)$. (continued) $\endgroup$ – SSequence Feb 14 at 4:27
  • $\begingroup$ For $\psi_\omega(0)+1 \leq x \leq \psi_\omega(1)$, we have $F_{\omega}(x)=\psi_\omega(1)$ and so on. Similarly, for limit, we have $F_{\omega}(\psi_\omega(\omega))=\psi_\omega(\omega)$ (and $F_\omega$ takes this output value on just one input). And once again for $\psi_\omega(\omega)+1 \leq x \leq \psi_\omega(\omega+1)$ we have $F_{\omega}(x)=\psi_\omega(\omega+1)$. And so on... Something similar should occur when replacing $F_{\omega}$ and $\psi_\omega$ with $F_{\alpha}$ and $\psi_\alpha$ respectively (for limit $\alpha$). $\endgroup$ – SSequence Feb 14 at 4:29
  • $\begingroup$ Also, probably a relevant link/exposition cs.man.ac.uk/~hsimmons/TEMP/OrdNotes.pdf. I haven't read it but, at a glance, I suppose it would probably cover all the points made above (and much more ofc). $\endgroup$ – SSequence Feb 14 at 4:47
  • $\begingroup$ Well, my question is, how do we know that $F_\omega(x)$ doesn't take on extra values than the common fixed points? The F(x) function is defined as the supremum of all lower Veblen functions at x. Clearly if x is a fixed point of all lower Veblen functions, the supremum there will be x, and then the function will suddenly become something else at x+1. But how do we know there isn't some x for which the supremum is larger than all lower Veblen functions at x, but not large enough to be the next fixed point? Just some supremum of intermediate size between the last fixed point and the next one. $\endgroup$ – Mike Battaglia Feb 14 at 5:26

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.