Set Theory – Logics Detecting Their Own Equivalence Notions: L_{?2,?}

lo.logicmodel-theoryset-theory

This question is a follow-up to another question of mine, with different language – see the link below.

Say that an infinite regular cardinal $\kappa$ is Fraissean iff the logic $\mathcal{L}_{\kappa,\omega}$ has the following property (called "SED" in the below-linked question):

For every finite signature $\Sigma$ there is a larger signature $\Sigma'$ containing $\Sigma$ and two new unary predicate symbols $A,B$ – and possibly more symbols besides – and an $\mathcal{L}_{\kappa,\omega}[\Sigma]$-sentence $\eta$ such that, for every pair of $\Sigma$-structures $\mathfrak{A},\mathfrak{B}$, we have $\mathfrak{A}\equiv_{\kappa,\omega}\mathfrak{B}$ iff there is an $\mathfrak{M}\models\eta$ with $A^\mathfrak{M}\upharpoonright\Sigma\cong\mathfrak{A}$ and $B^\mathfrak{M}\upharpoonright\Sigma\cong\mathfrak{B}$.

(That $\omega$ is Fraissean is an immediate consequence of Fraisse's characterization of elementary equivalence in terms of Ehrenfeucht-Fraisse games, hence the name.)

Farmer S showed that $\omega_1$ is not Fraissean; that argument, however, does not seem to immediately generalize to higher cardinals, the issue being that $\mathcal{L}_{\kappa,\omega}$-sentences are not generally coded by reals and so even in the presence of large cardinals we lose a necessary absoluteness result.

My question is: what can we say, in $\mathsf{ZFC}$ alone, about the situation re: $\omega_2$? Neither possibility has an obvious consistency proof to me; I would tentatively hazard a guess that $L$ thinks $\omega_2$ is not Fraissean and that the tree property at $\omega_2$ implies that $\omega_2$ is Fraissean, but both of these are essentially just free association.

Best Answer

(Working in ZFC.)

$\omega_2$ is not Fraissean. In fact, it is not Fraissean with respect to $\Sigma$, where $\Sigma$ is the signature with a single binary relation $<$. To see this we use a variant of the argument you linked in the question. Suppose otherwise, and let $\Sigma'$ and $\eta$ witness this. Let $\gamma$ be a large enough ordinal and let $\pi:M\to V_\eta$ be elementary, with $M$ transitive and $M^{\omega_1}\subseteq M$ and $\mathrm{crit}(\pi)=\kappa$ exists. Let $\mathfrak{A}=(\kappa,{{\in}\upharpoonright\kappa})$ and $\mathfrak{B}=(\pi(\kappa),{{\in}\upharpoonright\pi(\kappa)})$. Since $M^{\omega_1}\subseteq M$, $M$ is correct about $\mathcal{L}_{\omega_2,\omega}$-truth, and also by elementarity of $\pi$, therefore $\mathfrak{A}\equiv_{\mathcal{L}_{\omega_2,\omega}}\mathfrak{B}$. So let $\mathfrak{M}$ witness the choice of $\Sigma',\eta$ with respect to $\mathfrak{A},\mathfrak{B}$.

Let $G$ be $V$-generic for $\mathbb{P}=\mathrm{Coll}(\omega_1,\theta)$ where $\theta=\max(\pi(\kappa),\mathrm{card}(\mathfrak{M}))$ (collapsing $\theta$ to size $\aleph_1$ with countable conditions). Then $V[G]\models$"There are structures $\mathfrak{A}',\mathfrak{B}',\mathfrak{M}'$, each having universe $\omega_1$, such that $\mathfrak{A}',\mathfrak{B}'$ are in signature $\Sigma$, and $\mathfrak{M}'$ in signature $\Sigma'$, and $A^{\mathfrak{M}}\upharpoonright\Sigma\approx\mathfrak{A}'$ and $B^{\mathfrak{M}}\upharpoonright\Sigma\approx\mathfrak{B}'$, as witnessed by isomorphisms $\sigma,\tau$, and $\mathfrak{M}'\models\eta$ and there is a sentence $\varphi$ of $\mathcal{L}_{\omega_2^{V[G]},\omega}$, coded by a set $X\subseteq\omega_1$, such that $\mathfrak{A}'\models\varphi$ but $\mathfrak{B}'\models\neg\varphi$" (consider the natural sentence specifying the ordertype of $\kappa$). Fix names $\dot{\mathfrak{A}}',\dot{\mathfrak{B}}',\dot{\mathfrak{M}}',\dot{\sigma},\dot{\tau},\dot{X}$ for such objects (we may assume the empty condition forces the above things to hold for these names). So these are all basically names for subsets of $\omega_1$.

Now working in $V$, given an $\aleph_1$-sized family $\mathscr{F}$ of dense subsets $D\subseteq\mathbb{P}$, we can build an $\mathscr{F}$-generic filter $G$, because $\mathbb{P}$ is countably closed. We claim that by picking $\mathscr{F}$ appropriately, and $G$ be $\mathscr{F}$-generic, then letting $\mathfrak{A}'$, etc, be the interpretations $\dot{\mathfrak{A}}'_G$, and $\varphi$ the sentence in $\mathcal{L}_{\omega_2,\omega}$ the sentence coded by $X'$, then the sentence of the previous paragraph which held in the generic extension, holds in $V$ about these objects, which contradicts our assumptions.

To arrange $\mathscr{F}$: First, it is straightforward to arrange $\aleph_1$-many dense sets which arrange that $\dot{\sigma}_G$ and $\dot{\tau}_G$ will truly be isomorphisms; the main thing is to arrange the that the domain and codomain are the right sets. To arrange that $\mathfrak{M}'\models\eta$, consider not just $\eta$, but the set $S$ of all subformulas thereof. Now here that all formulas in $S$ have only finitely many distinct free variables (if $\psi$ has infinitely many distinct free variables, proceed by induction on the rank of formulas which have it as a subformula, to see that none of them are sentences). Since $\eta$ is in $\mathcal{H}_{\omega_2}$, we can fix a surjection $\pi:\omega_1\to S^+$, where $S^+$ is the set of pairs $(\psi,\vec{\alpha})$, where $\psi\in S$ and $\vec{\alpha}$ is an assignment of the (finitely many) free variables of $\psi$ to ordinals ${<\omega_1}$.

Now the basic point is that if $(\psi,\vec{\alpha})\in S^+$ and $\psi$ is a disjunction $\bigvee_{\gamma<\omega_1}\psi_\gamma$, and $p\in\mathbb{P}$ forces $\dot{\mathfrak{M}}'\models\psi(\vec{\alpha})$, then for each $q\leq p$ we can pick some $\gamma<\omega_1$ and $r\leq p$ such that $r$ forces that $\dot{\mathfrak{M}}'\models\psi_\gamma(\vec{\alpha})$. Thus, we can include a dense set $D_{\psi,\vec{\alpha}}$ consisting of those conditions $p$ such that either $p$ forces that $\dot{\mathfrak{M}}'\models\neg\psi(\vec{\alpha})$ or there is $\gamma<\omega_1$ such that $p$ forces that $\dot{\mathfrak{M}}'\models\psi_\gamma(\vec{\alpha})$. Similarly, if $\psi$ is of form $\exists x\varrho$, then we can include the dense set of conditions $p$ either forcing that $\dot{\mathfrak{M}}'\models\neg\psi(\vec{\alpha})$, or such that there is $\alpha<\omega_1$ such that $p$ forces $\dot{\mathfrak{M}}'\models\varrho(\alpha,\vec{\alpha})$. And naturally, for each $(\psi,\vec{\alpha})\in S^+$, we include the dense set of $p$ deciding whether $\dot{\mathfrak{M}}'\models\psi(\vec{\alpha})$. There are also natural dense sets forcing the atomic formulas the correspond to the structure of $\dot{\mathfrak{M}}'$.

For $X'$ and $\varphi'$ it is similar, but we no longer have $\varphi$ fixed in advance. But we can fix a name $\dot{S}_{\dot{\varphi}}^+$ for the set of all pairs $(\psi,\vec{\alpha})$ such that $\psi$ is a subformula of $\varphi$ (note in an actual forcing extension, we could have $\psi\notin V$), and $\vec{\alpha}$ an assignment of the free variables of $\psi$ to elements ${\in\omega_1}$. Fix a name for a surjection $\dot{f}:\omega_1\to \dot{S}^+_{\dot{\varphi}}$. Write $\dot{\psi}_\gamma$ for the name for the first component of $\dot{f}(\gamma)$, and $\vec{\alpha}_\gamma$ for the name for the second. Then for each $\gamma<\omega_1$, we can use the dense set deciding what sort of formula $\dot{\psi}_\gamma$ is (in particular, whether it is a disjunction, and whether it is existential), and the dense set of all conditions $p$ such that (i) there is $\vec{\alpha}$ such that $p$ forces "$\dot{\vec{\alpha}}_\gamma=\vec{\alpha}$", (ii) for some $\beta<\omega_1$, either

  • $p$ forces that $\dot{\psi}_\gamma$ is not a disjunction, or
  • $p$ forces that $\dot{\mathfrak{A}}'\models\neg{\dot{\psi}}_\gamma(\vec{\alpha})$, or
  • $p$ forces "$\dot{\psi}_\gamma$ is a disjunction, $\dot{\psi}_\beta$ is one of the disjuncts of $\dot{\psi}_\gamma$, $\dot{\vec{\alpha}}_\beta=\vec{\alpha}$ and $\dot{\mathfrak{A}}'\models\dot{\psi}_\beta(\vec{\alpha})$",

and (iii) there are $\alpha,\beta<\omega_1$ such that either

  • $p$ forces that $\dot{\psi}_\gamma$ is not existential, or
  • $p$ forces that $\dot{\mathfrak{A}}'\models\neg\dot{\psi}_\gamma$, or
  • $p$ forces "letting $\varrho=\dot{\psi}_\beta$, then $\dot{\psi}_\gamma$ is the formula $\exists x\ \varrho$, and $\vec{\alpha}_\beta=\vec{\alpha}\frown(\alpha)$, and $\dot{\mathfrak{A}}'\models\varrho(\vec{\alpha},\alpha)$".

Also include dense sets deciding whether $\dot{\mathfrak{A}}'\models\dot{\psi}_\gamma(\dot{\vec{\alpha}}_\gamma)$ holds, for each $\gamma$.

Likewise for $\dot{\mathfrak{B}}'$.

Also for each pair of ordinals $\alpha,\beta<\omega_1$, include the dense set of conditions $p$ such that either

  • $p$ forces that $\dot{\psi}_\alpha$ is not a disjunction/conjunction, or
  • $p$ forces that $\dot{\psi}_\alpha$ is a disjunction/conjunction, and $\dot{\psi}_\beta$ is one of the disjuncts/conjuncts, or
  • $p$ forces that $\dot{\psi}_\alpha$ is a disjunction/conjunction, and $\dot{\psi}_\beta$ is not one of the disjuncts/conjuncts.

Also for each $\alpha<\omega_1$, the dense set of conditions deciding the number (finitely many) of free variables of $\dot{\psi}_\alpha$, and arranging that $\dot{f}_G$ truly enumerates all of the relevant pairs $(\psi,\vec{\alpha})$.

(I think this is now about enough dense sets.)

Now let $G$ be $\mathscr{F}$-generic. Let $X'=\dot{X}'_G$, etc. It is straightforward to see that $\mathfrak{M}'\models\eta$ and $\mathfrak{A}'\approx A^{\mathfrak{M}'}\upharpoonright\Sigma$ (as witnessed by $\sigma'$) and likewise for $\mathfrak{B}'$. So by our assumptions, $\mathfrak{A}'\equiv_{\mathcal{L}_{\omega_2,\omega}}\mathfrak{B}'$. But $X'$ does really code a sentence $\varphi'$ of $\mathcal{L}_{\omega_2,\omega}$, because the ordertype along which it is built is wellfounded, because by the $\sigma$-closure of $\mathbb{P}$, otherwise we can find a condition $p$ which forces something to be an illfounded ordinal. And $\dot{S}^+{\dot{\varphi}}_G$ is the set of pairs $(\psi,\vec{\alpha})$ such that $\psi$ is a subformula of $\varphi'$, and $\vec{\alpha}$ an assignment of its free variables, and this set is enumerated by $\dot{f}_G$. And note that the names for the satisfaction relations amongst these formulas evaluate to the correct satisfaction relation. Thus, $\mathfrak{A}'\models\varphi'$ but $\mathfrak{B}'\models\neg\varphi'$, a contradiction.

Related Question