See e.g. the last section of Ebbinghaus/Flum/Thomas for the relevant background on abstract model theory. Below, all languages are finite for simplicity. "$HC$" is the set of hereditarily countable sets.

There's a silly version of Lindstrom's theorem for the infinitary logic $\mathcal{L}_{\omega_1,\omega}$ gotten by replacing compactness with Barwise compactness:

$(*)\quad$ Suppose that $\mathcal{L}=(Sent_\mathcal{L}, \models_\mathcal{L})$ is a regular logic such that:

  • $Sent_\mathcal{L}\subseteq HC$;

  • $Sent_{\mathcal{L}_{\omega_1,\omega}}\subseteq Sent_\mathcal{L}$ and for each $\varphi\in Sent_{\mathcal{L}_{\omega_1,\omega}}$ we have $Mod_{\mathcal{L}_{\omega_1,\omega}}(\varphi)=Mod_\mathcal{L}(\varphi)$;

  • $\mathcal{L}$ has the downward Lowenheim-Skolem property for single sentences: if $\theta\in Sent_\mathcal{L}$ has a model, then it has a countable model; and

  • $\mathcal{L}$ is Barwise compact: for every countable admissible $\mathbb{A}$ and every $\mathbb{A}$-c.e. theory $\mathfrak{T}\subseteq\mathcal{L}\cap\mathbb{A}$, if every $\mathbb{A}$-finite subset of $\mathfrak{T}$ has a model then $\mathfrak{T}$ has a model.

Then $\equiv_\mathcal{L}$ coarsens $\equiv^{EF}_{\omega_1}$: if Duplicator has a winning strategy in the EF-game of length $\omega_1$ between $\mathcal{A}$ and $\mathcal{B}$, then $\mathcal{A}\equiv_\mathcal{L}\mathcal{B}$.

(Note that the above would be trivial if we restricted attention to countable structures, by Scott's isomorphism theorem.)

Now, this is suboptimal in a couple different ways. The most obvious is that we don't get that $\equiv_\mathcal{L}$ and $\equiv_{\omega_1,\omega}$ coincide (since EF-games don't characterize infinitary equivalence nicely). However, the annoyance I want to focus on is the "implementation-specific" aspect: while some focus on implementation (the first bulletpoint) is necessary to make sense of Barwise compactness as a property of an abstract logic, the second bulletpoint in my opinion emphasizes the specific details of $\mathcal{L}$ too much.

Question: Is $(*)$ still true if we replace the second bulletpoint in $(*)$ with "$\mathcal{L}\ge\mathcal{L}_{\omega_1,\omega}$" - that is, if we require merely that for each $\varphi\in Sent_{\mathcal{L}_{\omega_1,\omega}}$ there be some $\psi\in Sent_\mathcal{L}$ with $Mod_{\mathcal{L}_{\omega_1,\omega}}(\varphi)=Mod_\mathcal{L}(\psi)$?

In the next two sections, I sketch the proof of $(*)$ and point out the key obstacle.

Proving $(*)$

Suppose $\mathcal{A}\equiv_{\omega_1}^{EF}\mathcal{B}$ but $\mathcal{A}\models\varphi$ and $\mathcal{B}\models\neg\varphi$ for some $\varphi\in \mathcal{L}$. Let $\varphi^A,\varphi^B$ be the relativizations of $\varphi$ to two new unary predicates, and let $r$ be a real coding these sentences, $\mathcal{A}$, and $\mathcal{B}$. Inside $\mathbb{A}=L_{\omega_1^{CK}(r)}[r]$ - which contains $\varphi^A$, $\varphi^B$, $\mathcal{A}$, and $\mathcal{B}$ since we can build a set in $HC$ from a real coding it using $\Sigma_1$-recursion - we consider the $\mathbb{A}$-c.e. theory $\mathfrak{T}\subseteq\mathcal{L}\cap\mathbb{A}$ describing the following type of structure:

  • The "design" sentence $(D)$, which says that we have sorts $A,B$ which describe structures with $A\models\varphi$ and $B\models\neg\varphi$ and sorts $S$ and $I$ where $I$ is a linear order and $S$ is a back-and-forth system of finite partial isomorphisms between $A$ and $B$ appropriately indexed by $I$.

  • For each $\alpha<\omega_1^{CK}(r)$, the "extension" sentence $(E)_\alpha$: "$\alpha$ embeds as an initial segment of $I$."

  • The "object" sentence $(O)$: "$I$ itself is an $r$-computable relation on $\omega$."

The point is that $\mathcal{A}$ and $\mathcal{B}$ generate in the obvious way a model $\mathcal{M}$ of $\{(D)\}\cup\{(E)_\alpha:\alpha<\omega_1^{CK}(r)\}$. This doesn't satisfy $(O)$ of course, but fixing $\alpha<\omega_1^{CK}$ we can "cut off" the $I$-part of $\mathcal{M}$ to get a structure $\mathcal{M}_\alpha$ which only captures $\mathcal{A}\equiv^{EF}_\alpha\mathcal{B}$ but which is an element of $\mathbb{A}$ - that is, $\mathcal{M}_\alpha\models\{(D),(O)\}\cup\{(E)_\beta:\beta<\alpha\}$.

Barwise compactness then gives us a model of the whole theory $\mathfrak{T}$. From this in turn we get a structure with an $A$-piece satisfying $\varphi$, a $B$-piece satisfying $\neg\varphi$, and an $\omega^*$-indexed back-and-forth system of finite partial isomorphisms between them. That whole situation is described by a single $\mathcal{L}$-sentence $\theta$, and so we get a countable model of $\theta$; but then the $A$- and $B$-pieces of that model are isomorphic, contradicting their $\mathcal{L}$-inequivalence.

The obstacle

So what breaks down if we try to run the argument above to prove the hoped-for stronger result?

Well, ignoring $(D)$ and the "one-and-done" requirements that a real coding $\varphi^A,\varphi^B,\mathcal{A},\mathcal{B}$ be in $\mathbb{A}$, the first thing we needed was for $\mathbb{A}$ to contain the sentences $(E)_\alpha$ for each $\alpha<\mathbb{A}\cap Ord$. When the $\mathcal{L}_{\omega_1,\omega}$-sentences is contained in $\mathcal{L}$ a la the undesired second bulletpoint above, this is trivial; but if the embedding $\mathcal{L}_{\omega_1,\omega}\le \mathcal{L}$ is sufficiently weird we might need to build this $\mathbb{A}$ as a big union of admissible sets to "catch our tail." That's doable ...

... But it ruins the second requirement, which is that we need to be able to get something like $(O)$. Basically, we need an $\mathcal{L}$-sentence (or at least an $\mathbb{A}$-c.e. $\mathcal{L}$-theory) which only describes things in $\mathbb{A}$ but does describe well-orderings of arbitrarily large ordertype $<\mathbb{A}\cap Ord$. This is a sense in which $\mathbb{A}$ would have to be "similar to" $L_{\omega_1^{CK}}$" ... which we'd have no reason to expect here.

That is, the only admissible sets big enough to have their fragments of $\mathcal{L}$ talk about all ordinals smaller than their height might be too big to do anything like the $(O)$-trick above. But $(O)$ was crucial: it was the only way we could conclude that after applying Barwise compactness we would get something whose back-and-forth-indexer was ill-founded.

  • $\begingroup$ Actually, the second bulletpoint I'm annoyed at here can be phrased in a much more palatable way by shifting from arbitrary to effective reductions of logics - e.g. if the translation from $\mathcal{L}_{\omega_1,\omega}$ into $\mathcal{L}$ is $E$-recursive in some parameter $p\in HC$ then dLS + BC gives $\equiv_\mathcal{L}\supseteq\equiv^{EF}_{\omega_1}$ because we can still trap things in good admissibles. So arguably it's the "boldface" comparison between logics which isn't appropriate in this setting. But, I'm still interested in whether the stronger implication hoped for above is true. $\endgroup$ Jan 20, 2020 at 5:04


Your Answer

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