2
$\begingroup$

The Veblen hierarchy is usually defined with $\varphi_0(x) = \omega^x$. As a result, we can define the Feferman–Schütte ordinal as the first fixed point of the function $\varphi_\alpha(0) = \alpha$.

I am wondering if it is possible to exceed this by looking at fixed points for not just the Veblen function index, but simultaneously for the exponentiation base that the hierarchy is built on, as well as the argument. Let's define the following function:

$\Phi_{\alpha,\beta}(x) = \varphi_{\beta}(x)$ such that $\varphi_0(x) = \alpha^x$

Or, in other words, the function $\Phi_{\alpha,\beta}(x)$ is just the $\beta$'th function of the Veblen hierarchy built on the base $\varphi_0(x) = \alpha^x$.

Given that, here are the questions:

Question 1: does a fixed point for the function $\Phi_{x,x}(0) = x$ exist? If so, what is the first one, and is it larger than $\Gamma_0$?

Question 2: if we let the argument change as well, no fixed points exist for $\Phi_{x,x}(x) = x$ (since none exist for $\Phi_{x,0}(x) = x^x \neq x$). However, is there any value $x < \Gamma_0$ for which $\Phi_{x,x}(x) \geq \Gamma_0$? If so, what is the first such $x$?

$\endgroup$
  • $\begingroup$ This is not an answer but here is an observation that might possibly be helpful. If we look at the function $f(x)=\omega^x$ and try to find its first fixed-point beyond $\epsilon_0$ then we want to calculate the terms $f^n(\epsilon_0+1)$ (where $n \in \mathbb{N}^+$). What we have is $f(\epsilon_0+1)=\epsilon_0 \cdot \omega$, $f^2(\epsilon_0+1)=\epsilon_0^\omega$. I think it is likely that if you continue it you will get a tower of $\epsilon_0$'s (since that's I re-call reading about $\epsilon_1$ somewhere). Ultimately we could prove it by induction and quite a bit of calculation. (cont.) $\endgroup$ – SSequence Mar 1 at 11:40
  • $\begingroup$ Maybe there is an easier way(?) but I don't know about it. On the other hand if we now consider the function $g(x)=(\epsilon_0)^x$ its first fixed point will also be the same. That's significantly easier to see. We have $g(0)=1$, $g^2(0)=\epsilon_0$, $g^3(0)={\epsilon_0}^{\epsilon_0}$ and so on. Meaning the first fixed point of $g$ is same as the first fixed-point of $f$ after $\epsilon_0$. $\endgroup$ – SSequence Mar 1 at 11:41
  • $\begingroup$ Also, one other point. If we consider the function $x \mapsto \varphi_{\varphi_x(0)}(0)$ I think it will be normal because $x \mapsto \varphi_x(0)$ is normal. So it will have a fixed point. My feeling is that (maybe) this function might be related to the function mentioned in (Q1) in some way. $\endgroup$ – SSequence Mar 1 at 13:47
  • 1
    $\begingroup$ Yes, it is true that $\epsilon_1 = \epsilon_0^{\epsilon_0^{\epsilon_0^{...}}}$, and likewise for $\epsilon_2 = \epsilon_1^{\epsilon_1^{\epsilon_1^{...}}}$ and so on; this is shown pretty well here - en.wikipedia.org/wiki/Epsilon_numbers_(mathematics). So yeah, if we change the base of exponentiation from $\omega$ to $\epsilon_0$, we get the same fixed-point sequence, just missing the first entry, and likewise for any epsilon number... $\endgroup$ – Mike Battaglia Mar 2 at 1:09
  • 1
    $\begingroup$ A brief comment: my suggestion basically was to use the values $\varphi_{x}(0)$ as the "base" (for increasing values of $x$) and then checking how the resulting hierarchy "compares" with the original one (the one starting with "base" $\omega$). Anyway.... $\endgroup$ – SSequence Mar 2 at 14:28
1
$\begingroup$

Question 1: If we include finite ordinals, then the only solution is $\Phi_{1,1}(0) = 1$. (and $\Phi_{0,0}(0) = 0$ if one chooses to set $0^0 = 0$) For $\alpha > 1$, the fixed points of $\Phi_{\alpha,0}(x) = \alpha^x$ cannot be $\alpha^0$ or $\alpha^1$, so they must be at least $\alpha^2$. In particular, they will be larger than $\alpha$, and so $\Phi_{\alpha,\alpha}(0)$, being a fixed point of $\alpha^x$, will be larger than $\alpha$ as well.

Question 2: Suppose $\alpha > 1$, and $\beta$ is a fixed point of the function $f(x) = \alpha^x$. As above, we see that $\beta > \alpha$. Also, $\beta = \alpha^\beta \ge 2^\beta \ge \beta$, so $\beta = 2^\beta$. Clearly $\beta$ cannot be finite, and if $\beta \ge \omega+1$ then $\beta \ge \sup \{\omega+1, 2^{\omega+1}, 2^{2^{\omega+1}}, 2^{2^{2^{\omega+1}}},\cdots\} = \sup \{\omega+1, \omega \cdot 2, \omega^2, \omega^\omega, \omega^{\omega^\omega},\cdots\} = \varepsilon_0$. Similarly, if $\beta \ge \varepsilon_{\gamma}+1$, then $\beta \ge \varepsilon_{\gamma+1}$. So $\beta$ must belong to the class $\{\omega\} \bigcup \{\varepsilon_\beta\}_{\beta \in \text{Ord}}$. Going the other direction, if $\beta$ is a member of $\{\omega\} \bigcup \{\varepsilon_\beta\}_{\beta \in \text{Ord}}$, and is larger than $\alpha$, then $\alpha \beta = \beta$, so $\beta \le \alpha^\beta \le (2^\alpha)^\beta = 2^{(\alpha \beta)} = 2^\beta = \beta$, so $\alpha^\beta = \beta$. Hence the members of the class $\{\Phi_{\alpha,1}(x) | x \in \text{Ord}\}$ are the members of the class $\{\omega\} \bigcup \{\varepsilon_\beta\}_{\beta \in \text{Ord}}$ that are larger than $\alpha$. So for $\alpha$ infinite, $\Phi_{\alpha,1}(x) = \varphi_1 (\gamma + x)$ for some ordinal $\gamma$ with $\gamma \le \alpha+1$. (We need $\alpha+1$, since, for instance, $\Phi_{\varphi_2(0),1}(0) = \varphi_1(\varphi_2(0) + 1)$.)

We can now use induction: Given that $\Phi_{\alpha,\beta}(x) = \varphi_\beta(\gamma+x)$ for some $\gamma \le \alpha+1$, we see that for any $\zeta$, $\Phi_{\alpha,\beta+1}(\zeta)$ satisfies $x = \varphi_\beta(\gamma+x)$, and hence is larger than $\gamma$. Also, $x = \varphi_\beta(\gamma+x) \ge \varphi_\beta(x) \ge x$, so $x$ is a fixed point of $\varphi_\beta$. Going the other direction, if $x$ is larger than $\gamma$ and is a fixed point of $\varphi_\beta$, then $x$, being an $\varepsilon$-number, satisfies $\gamma+x = x$, so $x = \varphi_\beta(x) = \varphi_\beta(\gamma+x)$. So the fixed points of $\varphi_\beta(\gamma+x)$ are precisely the fixed points of $\varphi_\beta(x)$ that are greater than $\gamma$, and so $\Phi_{\alpha,\beta+1}(x) = \varphi_{\beta+1}(\gamma' + x)$, for some $\gamma' \le \gamma+1$, with strict inequality when $\gamma = \alpha+1$; hence $\gamma' \le \alpha+1$.

Furthermore, suppose $\beta$ is a limit ordinal, and suppose, for all $\delta < \beta$, we have $\Phi_{\alpha,\delta}(x) = \varphi_\delta(\gamma_\delta + x)$ for some ordinals $\gamma_\delta \le \alpha+1$. We see that $\Phi_{\alpha,\beta}(x)$ must be greater than $\alpha$, and also, since it is a fixed point of $\varphi_\delta$ for all $\delta < \beta$, must be of the form $\varphi_\beta(\chi)$. Going the other direction, if $x$ is greater than $\alpha$ and of the form $\varphi_\beta(\chi)$, then $x$, being an $\varepsilon$-number, satisfies $\gamma_\delta + x = x$ for all $\delta < \beta$. So for any $\delta < \beta$, $\varphi_\delta(\gamma_\delta + x) = \varphi_\delta(x) = x$, and so $x$ is of the form $\Phi_{\alpha,\beta}(\chi')$. So $\Phi_{\alpha,\beta}(x) = \varphi_\beta(\gamma_\beta + x)$ for some $\gamma_\beta \le \alpha+1$.

So, by transfinite induction, there exists ordinals $\gamma_{\alpha,\beta} \le \alpha+1$ such that, for all $\alpha, \beta, x,$ with $\alpha$ infinite, we have $\Phi_{\alpha,\beta}(x) = \varphi_\beta (\gamma_{\alpha,\beta}+x)$. If $\alpha, \beta, x < \Gamma_0$, then $\gamma_{\alpha,\beta} + x < \Gamma_0$, so $\varphi_\beta(\gamma_\beta+x) < \Gamma_0$.

$\endgroup$

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.