Generalization of elementary equivalence between models of some first order theory

Question

Premise: I don't know much about higher (than 1) order logic.

Let me start with an example.

We know that the theory of dense linear orders without endpoints (DLO) is complete; this follows from the Łoś–Vaught test and Fraïssé theorem, using the fact that two DLOs are partially isomorphic.

In first order logic (where the theory of DLOs is formulated), complete theories are exactly those theories that have exacly one model up to elementary equivalences, i.e. their models are indistinguishable from the point of view of first order logic (first order logic formulas that are true in a specific model, are true in every model).

The equivalence relation of being elementary equivalent is, of course, weaker than being isomorphic (isomorphisms preserve and reflect the validity of every formula): an example (in DLO) is given by $\mathbb{R}$ and $\mathbb{R} + \mathbb{Q}$ (the disjoint union of $\mathbb{R}$ and $\mathbb{Q}$, with the extended order for which the elements from the copy of $\mathbb{R}$ are smaller than the elements from the copy of $\mathbb{Q}$). In order to prove that these DLOs are not isomorphic, we need to look at properties that can be written in higher order logic (because in first order logic they are indistinguishable). In particular, one finds out that in $\mathbb{R} + \mathbb{Q}$ there are intervals with countably many elements, while this doesn't happen in $\mathbb{R}$.

My question is: is it possible to generalize this notion of being indistinguishable, while considering every possible order? In this case, would the notion be strictly weaker than being isomorphic (as for elementary equivalence) or not?

Answer 1

You're basically looking for the subject of abstract model theory (sometimes referred to as "soft model theory"). The most comprehensive text on the subject is the epic collection Model-theoretic logics, which is freely and legally available at ProjectEuclid, and the first two chapters give a quite readable introduction to the subject; however, the last chapter(s?) of Ebbinghaus/Flum/Thomas's Mathematical logic is also a good starting point, and I should also recommend Barwise's wonderful paper Axioms for abstract model theory (which is much more accessible than the title might indicate!). Arguably the first result in abstract model theory was Lindstrom's theorem, which characterized first-order logic $\mathsf{FOL}$ as maximal with respect to a couple nice properties:

No regular logic properly stronger than $\mathsf{FOL}$ has both the compactness and downward Lowenheim-Skolem properties.

Roughly speaking, every logic $\mathcal{L}$ gives rise to an equivalence relation $\equiv_\mathcal{L}$ exactly analogously to first-order logic. We can also consider a set $\mathfrak{L}$ of multiple logics at once, by looking at the intersection of the equivalence relations $$\equiv_\mathfrak{L}:=\bigcap_{\mathcal{L}\in\mathfrak{L}}\equiv_\mathcal{L}$$ (which is again an equivalence relation!). As long as $\mathcal{L}$ is "small" (or $\mathfrak{L}$ a "small" set of "small" logics), a simple counting argument shows that $\equiv_\mathcal{L}$ (or $\equiv_\mathfrak{L}$) is strictly coarser than $\cong$. However, concrete examples of coarseness may be hard to come by; already, finding concrete examples of second-order-equivalent structures which are non-isomorphic is pretty much impossible!

You specifically mention higher-order logics, but it's important to note that this isn't the only direction in which we can strengthen $\mathsf{FOL}$. Others include:

• "Longer" formulas (= infinitary logics).

• Generalized quantifiers like "there exist uncountably many."

• Logics defined without any syntax at all (admittedly I really just know of one interesting example here, but it's super important and current: Shelah's so-called "$L_\kappa^1$" for $\kappa=\beth_\kappa$, especially singular such $\kappa$ - see the introduction here).

And so on.

---

Of course there is a ton of interesting material here; at the risk of boring the reader, I'll just mention one line of inquiry I specifically care about which ties deeply into the OP's specific focus on logics' equivalence relations:

Fraisse's theorem shows that $\equiv_\mathsf{FOL}$ is $\mathsf{FOL}$-"detectable" in a precise sense - roughly, given any language $\Sigma$ there is a larger language and a sentence $\eta$ in that language such that $\eta$'s models correspond exactly to the pairs of elementarily equivalent $\Sigma$-structures - and this is the key point behind Lindstrom's theorem. We can bootstrap Fraisse's theorem to get the analogous result for second-order logic (fun exercise). What about infinitary logics such as $\mathcal{L}_{\omega_1,\omega}$ (which is much better behaved than $\mathsf{SOL}$ in general) or $\mathcal{L}_{\omega_2,\omega}$ (which ... isn't quite as good :P)? It turns out that infinitary logics are not very good at detecting their own equivalence relations; as far as I know, this is due to Farmer Schlutzenberg using some pretty high-powered set theory, and in general little about "self-equivalence-detection" is known (see also here).