Roughly speaking, say that a logic $\mathcal{L}$ is self-equivalence-defining (SED) iff for each finite signature $\Sigma$ there is a larger signature $\Sigma'\supseteq\Sigma\sqcup\{A,B\}$ with $A,B$ unary relation symbols and an $\mathcal{L}[\Sigma']$-sentence $\eta$ such that the following are equivalent for all $\Sigma$-structures $\mathfrak{A},\mathfrak{B}$:

  • $\mathfrak{A}\equiv_\mathcal{L}\mathfrak{B}$.

  • There is a $\Sigma'$-structure $\mathfrak{S}$ such that $\mathfrak{S}\models \eta$, $A^\mathfrak{S}\upharpoonright\Sigma\cong\mathfrak{A}$, and $B^\mathfrak{S}\upharpoonright\Sigma\cong\mathfrak{B}$.

For example, Fraisse showed that $\mathsf{FOL}$ is SED (this is used crucially in the proof of Lindstrom's theorem - it's a very happy construction). That same argument gives as a corollary that $\mathsf{SOL}$ is also SED, roughly because $(i)$ "$X$ is the powerset of $Y$" is second-order expressible and $(ii)$ $\mathsf{SOL}$-elementary equivalence between two structures amounts to $\mathsf{FOL}$-elementary equivalence between their "power-structures."

The nicest logic whose SED status I don't know is $\mathcal{L}_{\omega_1,\omega}$. On the one hand, this logic isn't powerful enough to perform the same sort of "cheat" as $\mathsf{SOL}$. On the other hand, the direct game-theoretic attack analogizing the situation for $\mathsf{FOL}$ results in a game which is a bit too complicated for $\mathcal{L}_{\omega_1,\omega}$ to handle appropriately; see Vaananen/Wang, An Ehrenfeucht-Fraisse game for $\mathcal{L}_{\omega_1,\omega}$, and note that this was also an issue in this earlier question of mine. So my question is:

Is $\mathcal{L}_{\omega_1,\omega}$ SED?

I'm separately interested in the general situation of which infinitary logics are SED. It's not hard to show that for $\kappa$ satisfying appropriate large cardinal properties we have that $\mathcal{L}_{\kappa,\omega}$ is SED, but I don't see how to extract large cardinal strength from SEDness.

Note that looking at a single sentence $\eta$, as opposed to a theory $E$, is needed to avoid every (regular) logic being trivially SED; I messed this up in the original version of this question, and this was pointed out by Peter LeFanu Lumsdaine. Separately, I've added the forcing tag since, despite not being part of the question, general principles about forcing turn out to form a key component of the answer.


1 Answer 1


(Working in ZFC.)

No (re $\mathcal{L}_{\omega_1,\omega}$). Suppose it is. Consider the signature $\Sigma$ with just one binary relation symbol $<$. Let $\Sigma',\eta$ witness SED-ness for $\Sigma$.

Let $\pi:M\to V_\theta$ be elementary,with $\theta$ some sufficiently large limit ordinal, $M$ transitive, $M$ of cardinality $\kappa=2^{\aleph_0}$, with $\mathbb{R},2^{\aleph_0}\subseteq M$. So $\mathrm{crit}(\pi)=\kappa^{+M}<\kappa^+$ and $\pi(\kappa^{+M})=\kappa^+$. Let $\mathfrak{A}=(\kappa^{+M},{\in}\upharpoonright\kappa^{+M})$ and $\mathfrak{B}=(\kappa^+,{\in}\upharpoonright\kappa^+)$. Note that $\mathfrak{A}\equiv_{\omega_1,\omega}\mathfrak{B}$, since $\pi$ is elementary and all the sentences in $\mathcal{L}_{\omega_1,\omega}$ are in $M$, since $\mathbb{R}\subseteq M$. So by hypothesis, there is some $\Sigma'$-structure $\mathfrak{G}$ such that $\mathfrak{G}\models\eta$, $A^{\mathfrak{G}}\upharpoonright\Sigma\cong\mathfrak{A}$ and $B^{\mathfrak{G}}\upharpoonright\Sigma\cong\mathfrak{B}$.

Now let $G$ be $V$-generic for $\mathrm{Coll}(\omega,\max(\kappa^{+},|\mathfrak{G}|))$. In $V[G]$, there is an $\mathcal{L}_{\omega_1,\omega}$ sentence $\varphi$ in the signature $\Sigma$ asserting that the model is (isomorphic to) $\kappa^{+M}$. So in $V[G]$, $\mathfrak{A}\models\varphi$ but $\mathfrak{B}\models\neg\varphi$. So $V[G]$ models the statement "there are countable structures $\mathfrak{A}_0,\mathfrak{B}_0$ in the signature $\Sigma$ and an $\mathcal{L}_{\omega_1,\omega}$-sentence $\varphi_0$ such that $\mathfrak{A}_0\models\varphi_0$ and $\mathfrak{B}_0\models\neg\varphi_0$ and there is a countable structure $\mathfrak{G}_0$ in the signature $\Sigma'$ such that $\mathfrak{G}_0\models\eta$ and $A^{\mathfrak{G}}\upharpoonright\Sigma\cong\mathfrak{A}_0$ and $B^{\mathfrak{G}}\upharpoonright\Sigma\cong\mathfrak{B}_0$". But this statement is $\Sigma^1_2$ in a real coding $\eta$. (I don't see that it is $\Sigma^1_1$ in such a real, because to assert that $\varphi_0$ is really a sentence of $\mathcal{L}_{\omega_1,\omega}$ involves saying that it is built along a real ordinal.) Since $\eta\in V$ and by Shoenfield absoluteness, $V$ models the same statement. But this contradicts our assumptions.

  • 2
    $\begingroup$ Beautiful, thanks! (I'm separately curious: is the picture for other $\mathcal{L}_{\kappa,\omega}$s obvious? I don't think the same argument works even for $\kappa=\omega_2$ without some more care, unless I'm missing something.) $\endgroup$ Commented Jan 19, 2022 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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