7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Commented Jan 12, 2020 at 21:21

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.