Math 557 Oct 1

Elementary Equivalence

Key Concepts

• Two \(\mathcal{L}\)-structures are elementary equivalent if for all \(\mathcal{L}\)-sentences \(\sigma\), \[\mathcal{M} \models \sigma \; \iff \; \mathcal{N} \models \sigma\]

Problems

Exercise 1
Show that for any two \(\mathcal{L}\)-structures \(\mathcal{M}, \mathcal{N}\), \[ \mathcal{M}\equiv \mathcal{N} \; \iff \; \operatorname{Th}(\mathcal{M}) = \operatorname{Th}(\mathcal{N}). \]

Deduce that a theory \(T\) is complete iff any two models are elementary equivalent.

Take-home problem

Let \(\mathcal{L}\) be an arbitrary language. Show that for finite \(\mathcal{L}\)-structures \(\mathcal{M}, \mathcal{N}\),

\[ \mathcal{M} \equiv \mathcal{N} \; \iff \; \mathcal{M} \cong \mathcal{N} \]

We already know this for finite languages (since in this case a single sentence can force isomorphism). How can we extend this to arbitrary languages?

Dense linear orders

Exercise 2
Let \(\operatorname{DLO}\) be the theory of dense linear orders without endpoints (i.e. no minimal or maximal element) in the language \(\mathcal{L}_{<}=\{<\}\) of orders.

Find a finite axiomatization of \(\operatorname{DLO}\), as well as a model.

\(\operatorname{DLO}\) is going to be an important example for us. In many ways, it exemplifies what an “easy” mathematical theory looks like. We will make this precise over the coming weeks. We start with the observation that there cannot be any “non-standard” countable models.

Exercise 3
Show that any two countable models of \(\operatorname{DLO}\) are isomorphic.

This is a famous result due to Cantor. For the proof, think “back and forth”.