Equivalence of models in infinitary logic

Question

In finite model theory we work a lot with a notion weaker than isomorphism, the k-equivalence. Given two structures of the same signature $M$ and $N$, we say that $M =_k N$ if they satisfy the same first order sentences of quantifier rank up to k.

With infinitary logic (where you allow infinite disjuntions and conjuctions) it makes sense to generalize the notion of quantifier rank to countable ordinals, by setting $qr(\bigwedge\phi_i) = \sup_i(qr(\phi_i))$. Therefore, we can generalize the notion of equivalence to $\alpha$-equivalence, for any countable ordinal $\alpha$.

Here is an interesting example: let $M$ be the countable graph consisting of the disjoint union of cycles of length $k$ for every integer $k$, and let $N$ be the same as $M$ plus a countable chain (an "infinite cycle"). It can be shown (via the Ehrenfeucht-Fraisse games) that $M$ and $N$ satisfy the same first order sentences, thus $M=_wN$. However, $M\neq_{w+1}N$. To see that let $\phi_i(x)$ be the first order sentence expressing "x is not in an $i-$cycle"and let $\psi=\exists x \ \bigwedge_i \phi_i$. By definition,$\ qr(\psi)=\omega+1$ and $N \models \psi$ but $M \not\models \psi$.

My questions are:

i) Is it true that for every non-limit ordinal $\alpha$, there exist structures $M$ and $N$ such that $M\neq_{\alpha}N$ but $M=_{\gamma}N$ for every $\gamma<\alpha$? I can’t come up with an example for $\alpha=\omega+2$.
ii) Can every countable structure be described up to isomorphism with sentences of quantifier rank bounded by some countable ordinal?

Noah Schweber · Accepted Answer · 2025-08-07 01:58:15Z

The answer to (i) is yes. Otherwise, for some countable ordinal $\alpha$ we would have $=_\alpha\implies=_{\omega_1}$, and this is false. One way to see that is to use Scott's isomorphism theorem (see below) and the fact that isomorphism on countable structures is not Borel. Of course this takes a bit of work; with some care, you can also whip up concrete examples (certain pairs of ordinals together with additional labelled points; I believe Rosenstein's book Linear orderings, which is sadly out-of-print, has details).

The answer to (ii) is also yes. This is Scott's isomorphism theorem: for every countable structure $\mathfrak{A}$ there is an $\mathcal{L}_{\omega_1,\omega}$-sentence (= countable rank) $\varphi$, called a Scott sentence, such that the countable models of $\varphi$ are exactly the structures isomorphic to $\mathfrak{A}$.

Neither appearance of countability can be dropped:

Since $\mathcal{L}_{\omega_1,\omega}$ has downward Lowenheim-Skolem for individual sentences, no uncountable structure can be pinned down up to isomorphism by a single $\mathcal{L}_{\omega_1,\omega}$-sentence.
Some Scott sentences have uncountable models! Indeed, consider the linear order $(\mathbb{Q};<)$. This is potentially isomorphic (= is $\mathcal{L}_{\infty,\omega}$-equivalent, or by Barwise becomes isomorphic in some forcing extension) to any dense linear order without endpoints, including for example $(\mathbb{R};<)$. So a fortiori any $\mathcal{L}_{\omega_1,\omega}$-sentence true in $(\mathbb{Q};<)$ also has uncountable models.

Stack Exchange Network

Equivalence of models in infinitary logic

1 Answer 1

You must log in to answer this question.

Equivalence of models in infinitary logic

1 Answer 1

You must log in to answer this question.

Related