7
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$
    – Farmer S
    Jan 15 at 22:25
  • $\begingroup$ @FarmerS I think that's right - fixed! $\endgroup$ Jan 15 at 22:26
  • $\begingroup$ In the question, is the $\Sigma_1$/$\Pi_1$ definition allowed to use parameters? $\endgroup$
    – Farmer S
    Jan 15 at 23:17
  • $\begingroup$ @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. $\endgroup$ Jan 15 at 23:26

1 Answer 1

6
$\begingroup$

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.

$\endgroup$

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.