6
$\begingroup$

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).

$\endgroup$
0

1 Answer 1

3
+200
$\begingroup$

(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 \begin{equation} \mathrm{Sat}_\alpha(T)\iff L_\alpha\models \text{"there is a model of }T\text{"}.\end{equation}

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Apr 22, 2021 at 2:10
  • $\begingroup$ @NoahSchweber I'd be interested in what happens in the countable cofinality case too... $\endgroup$
    – Farmer S
    Apr 23, 2021 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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