Complexity of infinitary satisfiability, part 2

Question

This question is a follow-up to this one, which was almost entirely answered by Farmer S. Throughout, we work in $\mathsf{ZFC+V=L}$.

---

Given a "pre-admissible" (= admissible or limit of admissibles) ordinal $\kappa$, let $\mathsf{Sat}_\kappa$ be the set of $\mathcal{L}_{\infty,\omega}\cap L_\kappa$-sentences which are satisfiable - that is, which have a model, but not necessarily a model in or nicely-definable-over $L_\kappa$. The two easy cases are:

• If $\kappa$ is countable, then by the Barwise completeness theorem we get $\mathsf{Sat}_\kappa$ is $\Pi_1(L_\kappa)$.

• If $\kappa$ is an uncountable cardinal, then $\mathsf{Sat}_\kappa$ is $\Sigma_1(L_\kappa)$ by a downward Lowenheim-Skolem + Mostowski collapse argument: $\varphi\in\mathcal{L}_{\infty,\omega}\cap L_\kappa$ is satisfiable iff $L_\kappa\models$ "$\varphi$ is satisfiable."

At the above-linked question, Farmer S. handled most of the remaining cases:

• If $\kappa$ is a non-cardinal of uncountable cofinality and $L_\kappa$ does not correctly compute $\mathsf{Sat}_\kappa$ (this is the $\Sigma_1(L_\kappa)$-case), then $\mathsf{Sat}_\kappa$ is not definable with parameters over $L_\kappa$ at all.

This leaves open the situation of $\kappa$ satisfying $\omega=\mathit{cf}(\vert\kappa\vert)<\vert\kappa\vert<\kappa$, that is, the non-cardinals of countable cofinality cardinality. I suspect that this will be a bit tricky to analyze in full, so instead let me ask a more limited question:

Is there a pre-admissible $\kappa$ such that $\mathsf{Sat}_\kappa$ is definable-with-parameters over $L_\kappa$ but not in a $\Sigma_1$ or $\Pi_1$ way?

Answer 1

Here is a partial answer; it deals with those admissibles $\kappa$ large enough to see that $\mathrm{cof}(|\kappa|)=\omega$ and such that $L_\kappa$ has largest cardinal $\theta$.

That is, let $\kappa$ be as in the question, be admissible, and let $\theta=|\kappa|$, so $\mathrm{cof}(\theta)=\omega$. Suppose that $L_\kappa\models$"$\mathrm{cof}(\theta)=\omega$ and every set has cardinality $\leq\theta$" (of course this is true for club many $\kappa<\theta^+$).

Then I claim that $\mathrm{Sat}_\kappa$ is $\Pi_1^{L_\kappa}(\{\theta\})$.

For let $f:\omega\to\theta$ be the $L$-least cofinal, strictly increasing function with $\mathrm{range}(f)$ a set of cardinals; so by hypothesis, $f\in L_\kappa$. Note that $\{f\}$ is $\Sigma_1^{L_\kappa}(\{\theta\})$. So our $\Pi_1^{L_\kappa}(\{\theta\})$ definition can refer to $f$.

Working in $L_\kappa$, let $T$ be some $\mathcal{L}_{\infty\omega}$ theory. We want to determine whether $T$ is satisfiable. Since $L_\kappa\models$"every set has cardinality $\leq\theta$", and we can in a $\Sigma_1(\{T,\theta\})$ manner find the $L$-least surjection $g:\kappa\to T$, we may in fact assume that $T$ is (coded by) a subset of $\theta$. Let $\mathscr{T}_T$ be the tree of attempts to build a sequence $\left<N_n,M_n,T_n,f_n,\theta_n,\pi_n\right>$ such that:

• $N_n$ is a structure in the language of set theory with $N_n\models$"ZF$^-$+$V=L$", and $\mathrm{card}(N_n)=f(n)$,
• $f(n)+1\subseteq\mathrm{Ord}^{N_n}$ and $f(n)+1$ is an initial segment of $\mathrm{Ord}^{N_n}$,
• $f_n,M_n,T_n,\theta_n\in N_n$ and $N_n\models$"$\theta_n$ is a cardinal, $f_n:\omega\to\theta_n$ is cofinal, $T_n$ is a theory of $\mathcal{L}_{\infty\omega}$ and $M_n$ is a model such that $M_n\models T_n$",
• $f_n\upharpoonright (n+1)=f\upharpoonright(n+1)$,
• $\pi_n:N_n\to N_{n+1}$ is elementary, with $\pi_n(f_n,M_n,T_n,\theta_n)=(f_{n+1},M_{n+1},T_{n+1},\theta_{n+1})$ and $\mathrm{crit}(\pi_n)>f(n)$.

(The nodes of $\mathscr{T}_T$ should specify say $(\left<N_n,M_n,T_n,f_n,\theta_n,\right>_{n<k},\left<\pi_n\right>_{n+1<k})$ for some $k<\omega$.) Note that $\mathscr{T}_T\in L_\kappa$.

Working in $L$, I claim that $T$ is satisfiable iff $\mathscr{T}_T$ has an infinite branch. For if $M\models T$ then let $\gamma$ be large enough with $M\in N=L_\gamma\models$ZF$^-$, and then form a sequence of elementary hulls $X_n$ of $N$ of cardinalities $f(n)$ etc, and use their transitive collapses $N_n$ etc to get an infinite branch. Conversely, if there is an infinite branch $\left<N_n,\ldots\right>_{n<\omega}$, then we can let $(N,f',M',T',\theta')$ be the natural direct limit, and then note that $f'=f$, $\theta'=\theta$, $T'=T$ (as $T\subseteq\theta$ in the codes), and $N\models$ ZF$^-$ + "$M\models T$", but because $T\in N$ and $T$ encodes the relevant ordinals into its own structure, $N$ must be sufficiently wellfounded that it is correct about the truth computation, so $M\models T$, so $T$ is satisfiable.

So since $L_\kappa\models$KP, the existence of a branch through $\mathscr{T}_T$ is $\Pi_1^{L_\kappa}(\{\theta,T\})$, uniformly in $T$, so $\mathrm{Sat}^{L_\kappa}$ is $\Pi_1^{L_\kappa}(\{\theta\})$.

Remark: Suppose $\kappa$ is also a successor admissible. Then $L_\kappa$ is not correct about satisfiability. For let $\gamma<\kappa$ be above all admissibles $<\kappa$ and such that $L_\gamma$ projects to $\theta$. Then consider the theory $T$ whose models $M$ must satisfy KP + $V=L$, and must have $\gamma+1\subseteq\mathrm{wfp}(M)$, and which satisfy "I have no proper segment of height $>\gamma$ modelling KP". There is no such $M\in L_\kappa$.

Remark 2: On the other hand, suppose $\kappa$ is a limit of admissibles, and the other hypotheses above hold. Then by the arguments above and considering the left-most branch through $\mathscr{T}_T$, $L_\kappa$ is correct about satisfiability.

So it remains to handle those pre-admissibles $\kappa$ such that either $L_\kappa\models$"$\mathrm{cof}(\theta)>\kappa$" (and therefore $L_\kappa\models$"$\theta$ is inaccessible"), or $L_\kappa\models$"$\theta^+$ exists". It also remains to determine whether the parameter $\theta$ can be eliminated above.