# How complicated can infinitary satisfiability problems be?

We work in $$\mathsf{ZFC+V=L}$$.

For $$\alpha$$ a possibly uncountable admissible ordinal, let $$Sat_\alpha$$ be the set of $$\mathcal{L}_{\infty,\omega}\cap L_\alpha$$-sentences which have a model (not necessarily in $$L_\alpha$$). I'm curious about the complexity of $$Sat_\alpha$$ relative to $$L_\alpha$$. There are a couple easy cases where we get $$\Pi_1$$ and $$\Sigma_1$$ respectively:

• Suppose $$\alpha$$ is a countable admissible ordinal. By Barwise's completeness theorem, $$\varphi\in Sat_\alpha$$ iff there is no "proof" (in the appropriate sense) of $$\neg\varphi$$ in $$L_\alpha$$; this gives $$Sat_\alpha\in \Pi_1(L_\alpha)$$.

• On the other side of things, suppose $$\kappa$$ is an uncountable cardinal and $$\mathcal{N}\models\varphi\in \mathcal{L}_{\kappa,\omega}$$. Pick a sufficiently large $$\theta$$ and let $$X\prec L_\theta$$ with $$\vert X\vert<\kappa$$, $$tc(\{\varphi\})\subseteq X$$, and $$\mathcal{N}\in X$$. Let $$\mu: X\rightarrow Y$$ be the Mostowski collapse map for $$X$$; then $$Y\subset L_\kappa$$ and $$Y\ni \mu(\mathcal{N})\models\varphi$$. Since checking satisfaction of an $$\mathcal{L}_{\kappa,\omega}$$-sentence in a structure is sufficiently simple, this means that $$Sat_\kappa$$ is $$\Sigma_1(L_\kappa)$$.

I'm curious whether these are the only two possible complexities:

Is there an uncountable admissible ordinal $$\alpha$$ such that $$Sat_\alpha$$ is neither $$\Sigma_1$$ or $$\Pi_1$$ (with parameters) over $$L_\alpha$$?

I suspect that the answer is, or follows trivially from, a well-known fact about uncountable admissible ordinals, but I don't see it at the moment. It's not even clear to me whether $$Sat_\alpha$$ is always first-order definable over $$L_\alpha$$ (I suspect that it isn't).

(We're working in ZFC + $$V=L$$.) Let $$\alpha$$ be the least admissible $$>\omega_1$$. Then $$\mathrm{Sat}_\alpha$$ is not definable from parameters over $$L_\alpha$$.

Lemma: (Assuming ZFC + $$V=L$$.) Let $$\kappa$$ be a cardinal such that $$\mathrm{cof}(\kappa)>\omega$$. Let $$M$$ be a model of "$$V=L$$" with $$\kappa\subseteq$$ the wellfounded part of $$M$$ and $$n<\omega$$ and $$x\in M$$ be such that $$M$$ is the $$\Sigma_n$$-hull (over $$M$$) of elements in $$\kappa\cup\{x\}$$. Suppose there is no strictly decreasing $$\omega$$-sequence of $$M$$-ordinals which is $$\Sigma_n$$-definable from parameters in $$M$$. Then $$M$$ is wellfounded.

Proof: Suppose $$M$$ is illfounded and let $$\left<\alpha_i\right>_{i<\omega}$$ be strictly descending in $$M$$'s ordinals. We can pick a sequence $$\left<\varphi_i,\beta_i\right>_{i<\omega}$$ such that $$\varphi_i$$ is a $$\Sigma_n$$ formula which defines $$\alpha_i$$ from $$(\beta_i,x)$$. But the sequence $$\left<\varphi_i,\beta_i\right>_{i<\omega}\in L_\kappa\subseteq M$$, and therefore $$\left<\alpha_i\right>_{i<\omega}$$ is $$\Sigma_n$$-definable from the parameter $$\left<\varphi_i,\beta_i\right>_{i<\omega}$$ over $$M$$, contradiction.

Now fix $$\alpha$$ the least admissible $$>\omega_1$$. Then $$L_\alpha$$ is the $$\Sigma_1$$-hull of $$\omega_1+1$$. So the full $$L_\alpha$$-theory of parameters in $$\omega_1+1$$ is not definable from parameters over $$L_\alpha$$. Let $$\lambda=\omega_1+1$$. Let $$T$$ be the $$\mathscr{L}_{\infty,\omega}\cap L_\alpha$$-theory, using $$\in$$, $$=$$ and constant symbols $$c$$ for each $$c\in\lambda$$, asserting the conjunction of (i) KP + $$V=L$$, (ii) I am wellfounded through $$\lambda$$ (i.e. "$$0,1,\ldots,\lambda$$ are an initial segment of my ordinals"), (iii) there is no proper segment of me beyond $$\lambda$$ which satisfies KP, (iv) I am the $$\Sigma_1$$-hull of $$\lambda$$, and (v) there is no infinite strictly decreasing sequence through my ordinals which is $$\Sigma_1$$-definable from parameters. Note that by the lemma, $$L_\alpha$$ is the unique model of $$T$$.

But now for each $$\vec{\xi}\in(\omega_1+1)^{<\omega}$$ and formula $$\varphi$$, the theory $$T+\varphi(\vec{\xi})$$ is satisfiable iff $$L_\alpha\models\varphi(\vec{\xi})$$. Therefore $$L_\alpha$$ cannot define satisfiability from parameters.

Taking this a bit further, we get:

Theorem: (Assume ZFC + $$V=L$$.) Let $$\alpha$$ be an infinite ordinal which is not a cardinal, such that $$\mathrm{card}(\alpha)$$ has cofinality $$>\omega$$. Then $$\mathrm{Sat}_\alpha$$ is definable from parameters over $$L_\alpha$$ iff $$L_\alpha$$ is closed under models witnessing its satisfiable formulas, i.e. iff $$$$\mathrm{Sat}_\alpha(T)\iff L_\alpha\models \text{"there is a model of }T\text{"}.$$$$

Proof Sketch: Suppose there is $$T\in L_\alpha$$ which is satisfiable but which has no model in $$L_\alpha$$. Like mentioned in the original question, $$T$$ has a model in $$L_{\alpha^+}$$. Therefore there is $$\beta$$ such that $$\alpha\leq\beta<\alpha^+$$ and $$L_\beta$$ projects to $$\kappa=\mathrm{card}(\alpha)$$ (i.e. there is $$n<\omega$$ and $$x\in L_\beta$$ such that $$L_\beta$$ is the $$\Sigma_n$$-hull of parameters in $$\kappa\cup\{x\}$$) and there is a model of $$T$$ in $$L_\beta$$. But since $$T\in L_\alpha$$, then arguing much as before, we can construct a theory $$T'\in L_\alpha$$ whose unique model is the least such $$L_\beta$$, which implies that $$L_\alpha$$ cannot define satisfiability, much as before. QED.

This leaves the uncountable non-cardinals $$\alpha$$ where $$\mathrm{card}(\alpha)$$ has countable cofinality, which the above obviously doesn't touch.

• Ooh, nice! This is a much better result than I was expecting. I'm definitely interested in the remaining case you mention at the end but this more than answers my question; I'll accept as soon as I've had time to convince myself about the details. Apr 22, 2021 at 2:10
• @NoahSchweber I'd be interested in what happens in the countable cofinality case too... Apr 23, 2021 at 15:50