Confusion about $\omega^{CK}_{\omega_1+1}$

Question

This is a shorter and more to the point version of the question I deleted few hours ago (which was much more complicated than necessary). My feeling is that I might have some basic confusion here, so the question might have a very easy answer (but I will go ahead and ask). Nevertheless, I have been thinking about it since yesterday and having trouble identifying where I am going wrong.

Let's denote $\theta=\omega^{CK}_{\omega_1+1}$. Now $\theta \geq \omega_1 \cdot 2$ should be true. Now consider an (infinite) computational model $Comp$ (just like ORM) but with an added instruction of the form $v:=\omega_1$. Let $S$ be set of all ordinals $X$ (with $\omega_1 \leq X < \omega_1 \cdot 2$) for which there is a program (of $Comp$) that starts from zero input and halts with a certain designated variable exactly equal to $X$. Now clearly, $S$ can't contain all elements between $\omega_1$ and $\omega_1 \cdot 2$, since there are only countably many $Comp$ programs.

Now let's fix a value $\alpha$ such that $\omega_1 \leq \alpha < \omega_1 \cdot 2$ and $\alpha \notin S$. Considering definition-8 in this paper: "An ordinal $\alpha \geq \omega$ is admissible iff there is no total $\Sigma_1(L_{\alpha})$-definable function f that maps an ordinal $\beta<\alpha$ cofinally into $\alpha$." As far as I can guess isn't "total $\Sigma_1(L_{\alpha})$-definable function" supposed to mean $\alpha$-recursive function? [please correct if this is wrong]

The thing that is bothering me here is that if we set $\lambda_0=\alpha$ doesn't the previous definition implies a chain of values $\lambda_n<\lambda_{n-1}<....<\lambda_1<\lambda_0$ such that for each $i$ there is a $\lambda_{i-1}$-recursive function (with cofinality $\lambda_{i-1}$) from $\lambda_i$ to $\lambda_{i-1}$. Furthermore, let's denote $\lambda_n$ as the first point in the chain where $\lambda_n \in S$ (for $0 \leq i < n$ we have $\lambda_i \notin S$). I think the chain will not abruptly drop below $\omega_1$ so the assumption that $\lambda_n \in S$ seems justified. [please correct if this is wrong]

Now let $f_i$ denote the function ($Ord$ to $Ord$) whose restriction corresponds to the $\lambda_{i-1}$-recursive function (with cofinality $\lambda_{i-1}$) from $\lambda_i$ to $\lambda_{i-1}$. What is bothering me here is that for a large enough value $\beta \geq \omega_1 \cdot 2$ we would have $\beta$-recursive functions and $\beta$-computable functions as exactly the same. But that would seems to imply that corresponding to $f_i$ there is an OTM with index $e_i$ that computes this function $f_i$. More specifically, the index for $f_n$ will be $e_n$. Now because we assumed that $\lambda_n \in S$, shouldn't there be a very simple program for the model $Comp$ which halts with the designated variable value equal to $\lambda_{n-1}$ (hence violating $\lambda_{n-1} \notin S$)? For example: $\lambda_{n-1}=sup \{f_n(x)|x<\lambda_n\}$. A similar observation "seems" to hold for all other $\lambda_i$'s with $i \leq n-1$.

I think I might be going wrong with something really simple here (since it can't be that easy), but I can't seem to identify it clearly. Anyway, I hope this question is written more clearly than the one which I deleted.

Answer 1

Counting computations

Below I'm restricting attention to "reasonably closed" ordinals for simplicity.

I think you're conflating programs and computable functions (and this is something I find annoying about Koepke's presentation, FWIW). Briefly: computable functions are programs with parameters.

There are indeed only countably many ORM-programs. However, an $\alpha$-computable function is given, not just by a program, but by a program with some tuple of parameters (see Definitions $1$ and $2$). Specifically, an $\alpha$-computable function is given by a pair $(P,p)$ where $P$ is a program and $p$ is a finite tuple of ordinals $<\alpha$. As a consequence, for any given $\alpha$ there are $\vert\alpha\vert$-many $\alpha$-computable functions.

• Note that the same is true of the $\alpha$-recursive functions: an $\alpha$-recursive function is essentially just a $\Sigma_1$ formula with parameters from $L_\alpha$.

As far as I can tell, this resolves the issue.

Incidentally, the following language may be a bit clearer. For each $n\in\omega$ we have a notion of "$n$-ary ORM program." There are only countably many of these. A $k$-ary $\alpha$-computable function is then a "projection of a program:" a partial function $f:\alpha\rightarrow\alpha$ is $\alpha$-computable iff there is some $(k+m)$-ary program $P$ and some $\rho_1,...,\rho_m<\alpha$ such that for all $\sigma_1,...,\sigma_k<\alpha$ we have $$f(\sigma_1,...,\sigma_k)\simeq P(\sigma_1,...,\sigma_k,\rho_1,...,\rho_m).$$

---

Dropping parameters

Now let me address the "dependence graph" idea you've described in the comments below, clarifying the $\lambda$-stuff. The issue is that the parameters may indeed have to drop below $\omega_1$. They can then of course be admissible, ending the process and killing the argument.

There are two key issues here:

• The first is Fodor's lemma, a kind of sophisticated counting argument which says that we can never keep dropping down in the way we would have to in order to avoid this. Basically, Fodor tells us that if we could avoid dropping parameters, we'd have lots of different $\alpha\in(\omega_1,\omega_1+\omega_1)$ whose inadmissibility is witnessed by the same program and parameter tuple.

• Now we need to argue that that can't happen, and this is the second key issue, which is a consequence of the "uniformly $\Sigma_1$-ness" of recursion: halting and outputting a value is witnessed by a single existential fact, so we can't have the same computation converge in two different ways in different contexts.

As the above suggests, a much more general fact holds: any "reasonable" computability theory gives rise to a notion of admissibility for which this same "parameter-dropping" has to happen (see the theorem below). This is a bit technical, but it's very much worth understanding.

---

Generalized computability theories

Definition. A good computation notion is a partial class function $$F: Ord\times \omega\times Ord^{<\omega}\times Ord\rightarrow Ord$$ satisfying the following two properties:

• Domain/range are good: $F(\alpha,e,{\bf p},\zeta)=\eta$ implies ${\bf p},\zeta,\eta<\alpha$ and $\alpha$ is closed under exponentation.

• Absoluteness of computations: whenever $F(\alpha_0,e,{\bf p},\zeta)$ and $F(\alpha_1,e,{\bf p},\zeta)$ are each defined, they are equal.

For simplicity, write "$F^\alpha_{e,{\bf p}}$" for the partial map $$\alpha\rightarrow\alpha: \zeta\mapsto F(\alpha,e,{\bf p},\zeta).$$ We read "$F_{e,{\bf p}}^\alpha(\zeta)=\eta$" as "in the context of $\alpha$, program $e$ with parameter tuple ${\bf p}$ on input $\zeta$ halts and equals $\eta$."

That's it! This is a really broad notion. In particular, it's easy to check that both recursion and computability in the senses above are good computation notions (once we tweak things slightly to allow programs to take arbitrary finite tuples of ordinals as parameters), the key point being that absoluteness follows from uniform $\Sigma_1$-definability over the relevant levels of the $L$-hierarchy.

Every good computation notion has an associated notion of admissibility:

If $F$ is a good computation notion, an ordinal $\alpha$ is $F$-admissible iff $\alpha$ is exponentially closed and there are no $e\in\omega$ and $\beta,{\bf p}<\alpha$ such that $\beta\subseteq dom(F_{e,{\bf p}}^\alpha)$ and $F_{e,{\bf p}}^\alpha[\beta]=\alpha$.

On the other hand, if there are such $e,\beta,{\bf p}$, we say that $(F^\alpha_{e,{\bf p}},\beta)$ witnesses the $F$-inadmissibility of $\alpha$.

For example - fixing a good computation notion $F$ - every uncountable regular cardinal is trivially $F$-admissible, while every $\alpha\in(\omega_1,\omega_1+\omega_1)$ is $F$-inadmissible via the addition clause. Finally - and this will be used implicitly below - if $(F^\alpha_{e,{\bf p}},\beta)$ witnesses the $F$-inadmissibility of $\alpha$ then $\vert\beta\vert=\vert\alpha\vert$.

• NOTE: This admissibility notion appears to differ from the usual notion, since we've demanded totality restricted to $\beta$ instead of genuine totality and we've demanded onto-ness instead of cofinality. However, it's a good exercise to check that they coincide (HINT: add $\beta$ as another parameter and use an "if-then-else" construction.)

Finally, I'll need a version of Fodor's lemma:

Modified Fodor: Let $S$ be a stationary set of countable ordinals. Suppose $G: S\rightarrow\omega_1{}^{<\omega}$ is regressive in the sense that $G(\sigma)\in\sigma^{<\omega}$. Then $G$ is constant on a stationary set.

Deducing this from the usual Fodor's lemma is a good exercise.

Here, then, is my claim:

Theorem: Suppose $F$ is a good computation notion. Then there is a statioary set of countable ordinals $S$ such that for every $\alpha\in S$, whenever $(F^\alpha_{e,{\bf p}},\beta)$ witnesses the $F$-inadmissibility of $\omega_1+\alpha$ there is some element of ${\bf p}$ which is $<\omega_1$.

That is, "parameters sometimes have to drop."

Proof. Suppose otherwise. Let $S$ be the set of countable ordinals $\alpha$ such that $\omega_1+\alpha$ is exponentiatially closed. Let $G:S\rightarrow\omega_1{}^{<\omega}$ be any function sending each $\alpha\in S$ to some tuple $\langle e,\delta_1,...,\delta_n,\beta\rangle$ such that $$(F^{\omega_1+\alpha}_{e,\langle \omega_1+\delta_1,...,\omega_1+\delta_n\rangle},\omega_1+\beta)$$ witnesses the $F$-inadmissibility of $\omega_1+\alpha$.

The function $G$ is regressive in the sense of the Fodor theorem above, and $S$ is stationary (indeed, club). So there is some stationary $T\subseteq S$ such that $G$ is constant - with value $\langle e,\delta_1,...,\delta_n,\beta\rangle$ - on $T$. For brevity let $${\bf p}=\langle \omega_1+\delta_1,...,\omega_1+\delta_n\rangle.$$

Now pick ordinals $\alpha_0<\alpha_1$ in $T$. Note that $\delta_1,...,\delta_n,\beta$ must all be $<\alpha_0,\alpha_1$ by definition of $T$. Now since $$(F^{\alpha_1}_{e,{\bf p}},\beta)$$ witnesses the $F$-inadmissibility of $\alpha_1$, there must be some $\zeta<\omega_1+\beta$ such that $$F(\alpha_1,e,{\bf p},\zeta)=\alpha_0+1.$$ But since $$F^{\alpha_0}_{e,{\bf p}}$$ witnesses the $F$-inadmissibility of $\alpha_0$ we must have some $\eta<\alpha_0$ such that $$F(\alpha_0,e,{\bf p}, \zeta)=\eta.$$ By absoluteness of $F$ this implies $\alpha_0+1=\eta<\alpha_0$, a contradiction. $\quad\Box$