I'm interested in ways of showing that two elementarily equivalent structures of the same cardinality aren't isomorphic. I have seen a few ad hoc ways of doing this like showing that they have different order types or making topological arguments. Those methods, however, have a non-logical feel to them, at least to me, which can make the trick hard to spot. To some extent that is to be expected, elementarily equivalent structures cannot be distinguished by first-order logic.

I found a logic (or more accurately a family of logics parameterized by a cardinal) that can encode isomorphism with a first-order structure, but I'm curious what sharper results are available or cases where logics that are stronger than first-order logic can distinguish non-isomorphic structures.

I'm okay with cases that are restricted to only first-order structures with countable domains, or finite languages, or restricted to rings, or something.

For example, I've seen references to Scott's isomorphism theorem here and here, which I think may be such a sharper result.

If I have two $L$-structures, $A$ and $B$, then $A$ and $B$ are elementarily equivalent if and only if $\text{Th}_{\text{FOL}}(A) = \text{Th}_{\text{FOL}}(B)$.

However, structures can be elementarily equivalent without being isomorphic. For example $(\mathbb{Q}, <)$ and $(\mathbb{R}, <)$ are elementarily equivalent but not isomorphic.

This made me wonder if there is a logic that's powerful enough to make the notions of elementary equivalence and isomorphism line up.

Infinitary second-order logic $\text{ESO}(\kappa)$ can do this.

Syntactically $\text{ESO}(\kappa)$ is like first-order logic except that existential second-order quantifiers are allowed in the prenex, all quantifiers can introduce up to $\kappa$ variables and infintary conjunction can involve up to $\kappa$ conjuncts.

First, let $\kappa$ be $|L| \cup |A|$ and suppose that $|A|$ and $|B|$ are the same.

Let $\text{Enc}(B, \vec{x}, \vec{f}, \vec{R})$ be an infinitary well-formed formula that encodes that the first-order structure formed by assembling the variables $\vec{x}$, the functions $\vec{f}$ and the relations $\vec{R}$ is isomorphic to $B$. This formula does not contain any quantifiers, it is just an infinite conjunction of formulas like $f_1(x_1) = x_2$ that are true of $B$. Note that the subscripts of $f$, $x$ and $R$ are ordinals in general, not just natural numbers. We do, however, insist that $x_i \neq x_j$ whenever $i \neq j$. The variables $\vec{x}$ are the domain, they are not constant symbols.

Next, let $G$ be a mapping between symbols in $L$ like $f$ and bound variable names like $f'$.

Next, let $\text{Iso}(h, G, \vec{x}, \vec{f}, \vec{R})$ be a statement that asserts that $h$ is an injective function and that $\alpha(\vec{x}) \leftrightarrow \alpha^G(\vec{x})$ for all atomic sentences $\alpha$.

I claim that the following sentence expresses the condition of being isomorphic to $B$.

$$ [\exists h \exists \vec{x} \exists \vec{f} \exists \vec{R}]( \text{Enc}(B, \vec{x}, \vec{f}, \vec{R}) \land \text{Iso}(h, G, \vec{x}, \vec{f}, \vec{R}) ) $$

Basically, we assert the existence of enough second-order variables to build ourselves a pseudomodel inside the values of the bound variables and then assert that the universe as a whole is isomrophic to the pseudomodel.

  • 1
    $\begingroup$ Related (maybe duplicate?): math.stackexchange.com/questions/1460398/…. Note that, while able to pin down every structure up to isomorphism, the class-sized logic $\mathcal{L}_{\infty,\infty}$ still has limitations; e.g. there is no sentence in this logic which characterizes the successor cardinals. $\endgroup$ Dec 8, 2023 at 6:02


You must log in to answer this question.

Browse other questions tagged .