Different definition of Veblen functions

267 Views Asked by At

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$.

1

There are 1 best solutions below

9
On BEST ANSWER

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)$.