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](https://mathoverflow.net/a/277345/8133) *(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.



"Robinson arithmetic" for (some) levels of $L$?
*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](https://link.springer.com/chapter/10.1007/BFb0059534); 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](https://mathoverflow.net/a/353900/8133) 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 $<rk(y)$ 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](https://www.worldscientific.com/doi/10.1142/9789812564894_0009), see also [Moschovakis](https://www.jstor.org/stable/2270854))*: 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.


