# Complexity of infinitary satisfiability, part 2

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?

• Looking back at the older question you linked, I think the answer there dealt with the case that $\mathrm{cof}(|\kappa|)>\omega$, as opposed to $\mathrm{cof}(\kappa)>\omega$. Jan 15 at 22:25
• @FarmerS I think that's right - fixed! Jan 15 at 22:26
• In the question, is the $\Sigma_1$/$\Pi_1$ definition allowed to use parameters? Jan 15 at 23:17
• @FarmerS Initially I had "no parameters allowed" in mind, but both versions are interesting. Since I have no idea how hard this is, I'll accept an answer for either version. Jan 15 at 23:26

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$$ 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+1 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<\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.