9
$\begingroup$

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.

$\endgroup$

1 Answer 1

12
+200
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Thank you so much again! Out of curiosity, do you know if there is existing literature on this general sort of topic (when $\equiv_\mathcal{L}$ is "nicely $\mathcal{L}$-describable")? $\endgroup$ Jan 24, 2022 at 2:31
  • 1
    $\begingroup$ No problem! I don't know about literature on this specific question... $\endgroup$
    – Farmer S
    Jan 24, 2022 at 22:09
  • 1
    $\begingroup$ Shame, it seems like a natural thing to think about. Oh well! Do you have any idea about how high up this pattern continues? I'm starting to get curious now about the least Fraissean cardinal ... $\endgroup$ Jan 24, 2022 at 23:42

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.