# "Robinson arithmetic" for (some) levels of $L$?

I'll write "$$\mathcal{L}_\alpha$$" for the fragment $$\mathcal{L}_{\infty,\omega}\cap L_\alpha$$.

Say that a countable admissible $$\alpha$$ is Robinsonian if there is some sentence $$\varphi\in\mathcal{L}_\alpha$$ such that $$L_\alpha\models\varphi$$ and there is no $$T\subseteq\mathcal{L}_\alpha$$ which is consistent, complete with respect to $$\mathcal{L}_\alpha$$, and $$\Delta_1$$ over $$L_\alpha$$. Intuitively, such a $$\varphi$$ is the "$$L_\alpha$$-analogue" of Robinson arithmetic.

By Barwise completeness, if $$\alpha$$ is a limit of admissibles then the set of satisfiable $$\mathcal{L}_\alpha$$-sentences is $$\Delta_1$$ over $$L_\alpha$$. Hence via a Henkinization argument we have that limits of admissibles are not Robinsonian. On the other hand, $$\omega$$ is clearly Robinsonian and it's not hard to show that $$\omega_1^{CK}$$ is Robinsonian as well.

My question is:

What are the Robinsonian ordinals?

I'd love it if the answer were exactly the successor admissibles, but I suspect it isn't; the stumbling point seems to be the non-Gandy ordinals (at a glance I think we do get that every successor admissible of a Gandy ordinal is Robinsonian by generalizing the argument for $$\omega_1^{CK}$$, but I haven't checked the details).

Note that it's not hard to show that for every $$\alpha$$ which is either admissible or a limit of admissibles, an analogue of Godel's first incompleteness theorem does hold: there is a $$\Sigma_1$$-over-$$L_\alpha$$ theory $$T\subseteq\mathcal{L}_\alpha$$ such that $$L_\alpha\models T$$ but $$T$$ has no $$\Delta_1$$-over-$$L_\alpha$$ consistent completion with respect to $$\mathcal{L}_\alpha$$. Moreover, there is a single $$\Sigma_1$$ formula which describes such a $$T$$ in every $$L_\alpha$$ with $$\alpha$$ pre-admissible. So it's plausible that there are lots of Robinsonian ordinals.

• This question came up in the course of thinking about what the analogue of provability logic for appropriate $\mathcal{L}_\alpha$-theories of $L_\alpha$ might be; separately, I'd love to be pointed towards any sources about that. Also, the OP can be generalized to countable admissible sets or countable "limit-admissible" sets (= countable transitive sets satisfying Pairing + "Every set is an element of an admissible set"), but that seems infeasibly general; that said, note that for general admissible sets we don't have a good well-ordering - and so the Henkinization argument above breaks down. Jan 12, 2020 at 21:21

EDIT: to my chagrin, the notion of "$$n$$-admissibility" is not what I thought it was! What I wanted was $$\Sigma_n$$-admissibility. You can find the definition of $$n$$-admissibles here; they are vastly smaller than their $$\Sigma_n$$ counterparts, and indeed for each $$n$$ the least $$n$$-admissible is less than the least $$\Sigma_2$$-admissible. Now $$n$$-admissibility is a rare notion these days and I've seen "$$n$$-admissible" used for "$$\Sigma_n$$-admissible" before, but given the relevance of older papers to this topic it's probably a good idea for me to not butcher this distinction.

Embarrassingly, I think I was overthinking this: I believe that the Robinsonian admissibles are exactly the successor admissibles.

The idea is to lift the following argument for the essential undecidability of $$Q$$ in the FOL-context to $$\mathcal{L}_\alpha$$: "If $$T\supseteq Q$$ is recursive then there is some $$\psi$$ such that $$\psi^N\cap\mathbb{N}=T$$ for all $$N\models Q$$, and if $$T\supseteq Q$$ is complete and consistent there is some $$M\models T$$; putting this together we get an $$M\models Q$$ with $$Th(M)$$ the standard part of a parameter-freely-definable set in $$M$$, contradicting (a version of) Tarski's theorem."

So suppose $$\alpha$$ is the next admissible above some admissible $$\beta$$ ...

Below, by "definable$$_\eta$$" I mean "definable by a parameter-free $$\mathcal{L}_\eta$$-formula," and "$$Th_\eta(K)$$" is the parameter-free $$\mathcal{L}_\eta$$-theory of $$K$$ - thought of as a subset of $$L_\eta$$. Note that it does make sense to ask whether a structure satisfies an $$\mathcal{L}_\eta$$-sentence even when that structure is not in $$L_\eta$$: $$\mathcal{L}_\eta$$ is just a sublogic of $$\mathcal{L}_{\infty,\omega}$$. Also, I'll conflate transitive sets with the corresponding $$\{\in\}$$-structures and conflate $$\mathcal{L}_\alpha$$-formulas with sets in $$L_\alpha$$ in some appropriate way.

First, define by recursion a formula $$\sigma_s$$ assigned to each set $$s$$ as follows: $$\sigma_s(x): \forall y(y\in x\leftrightarrow\bigvee_{t\in s}\sigma_t(s)).$$ Intuitively, $$\sigma_s$$ defines $$s$$ in a parameter-free way.

For $$s$$ a set, let $$\theta_s$$ be the sentence $$\bigwedge_{t\in s\cup\{s\}}\exists!y(\sigma_t(y))$$. The point of all this is that if $$M\models$$ Extensionality + $$\theta_s$$, then there is a unique embedding of $$tc(\{s\})$$ as an initial segment of $$M$$.

Now consider the $$\mathcal{L}_\alpha$$-sentence $$(*)$$ = "KP + Inf + V=L + $$\theta_\beta$$." I claim that $$(*)$$ witnesses the Robinsonian-ness of $$L_\alpha$$.

We observe the following: for every $$M\models(*)$$ there is a unique end-embedding $$l_M: L_\alpha\subseteq_{end}M$$, and every element of $$im(l_M)$$ is definable$$_\alpha$$ in $$M$$. The second half of this is trivial given the first half, and the first half combines the initial segment observation from the previous section with the fact that the well-founded part of an admissible set is admissible.

That last bit is what I was missing when I was worrying about non-Gandy-ness. I think it's worth elaborating on:

• First, note that it fails for $$\Sigma_2$$-admissibility, since by the Gandy Basis Theorem there is a model of $$KP2$$ with wellfounded part having height $$\omega_1^{CK}$$.

• The reason it works for ($$\Sigma_1$$-)admissibility is the upwards absoluteness of $$\Sigma_1$$ formulas. Let $$M\models KP$$ and $$N$$ be the wellfounded part of $$M$$. Let $$a,\varphi$$ be a $$\Sigma_1$$-Replacement instance in $$N$$: that is, $$\varphi$$ is $$\Sigma_1$$ and for each $$b\in a$$ there is exactly one $$c\in N$$ such that $$N\models\varphi(b,c)$$. Then in $$M$$ we can apply absoluteness to argue that $$a,\hat{\varphi}$$ is also a $$\Sigma_1$$-Replacement instance with the same solution class, where $$\hat{\varphi}(x,y)$$ is the formula "$$\varphi(x,y)$$ and no $$z$$ of rank $$ has $$\varphi(x,z)$$."

For $$M\models (*)$$ and $$X\subseteq M$$, let $$st_M(X)=X\cap im(l_M)$$.

The next key point is an analogue of Tarski's undefinability theorem:

Suppose $$M\models (*)$$. Then there is no definable$$_\alpha$$ $$D\subseteq M$$ such that $$st_M(D)=Th_\alpha(M).$$

In the interest of length I'll omit the proof; it's just the usual argument, though.

We put all this together as follows. Recapitulating the usual arguments for arithmetic, every $$\Delta_1$$-over-$$L_\alpha$$ set $$X$$ has an invariant definition (a la Kreisel, see also Moschovakis): there is a parameter-free $$\Sigma_1$$-formula $$\varphi\in\mathcal{L}_\alpha$$ such that whenever $$M\models (*)$$ we have $$st_M(\varphi^M)=X$$.

The "parameter-free" bit may seem like cheating; the point is that we can essentially fold the parameter into the structure of the formula itself via the $$\sigma_s$$-construction above.

Now if $$T$$ were a consistent complete $$\Sigma_1$$-over-$$L_\alpha$$ extension of $$(*)$$ in the sense of $$\mathcal{L}_\alpha$$, by fixing a $$\varphi$$ as above and an $$M\models T$$ we would have $$T=Th_\alpha(M)=st_M(\varphi^M)$$, contradicting the Tarskian result above.