# 4.3 Elementary Equivalence

Two structures may differ as sets and operations, yet satisfy exactly the same first order sentences, and this situation is captured by the notion of elementary equivalence, which compares structures at the level of logical expressibility rather than at the level of concrete representation.

### Definition 4.23 (Theory of a Structure)

Let $\mathcal A$ be a structure for a fixed signature.

The theory of $\mathcal A$, denoted:
$$
\mathrm{Th}(\mathcal A)
$$
is the set of all sentences in the language that are true in $\mathcal A$.

Thus:
$$
\mathrm{Th}(\mathcal A)=\{ \varphi : \mathcal A \models \varphi \}
$$

This set collects all first order statements that hold in the structure.

### Definition 4.24 (Elementary Equivalence)

Let $\mathcal A$ and $\mathcal B$ be structures for the same signature.

We say that $\mathcal A$ and $\mathcal B$ are elementarily equivalent if:
$$
\mathcal A \equiv \mathcal B
$$
which means:
$$
\mathrm{Th}(\mathcal A)=\mathrm{Th}(\mathcal B)
$$

Equivalently, for every sentence $\varphi$:
$$
\mathcal A \models \varphi
\quad \text{if and only if} \quad
\mathcal B \models \varphi
$$

Thus no first order sentence can distinguish between the two structures.

### Example 4.25

Consider the ordered sets:
$$
(\mathbb Q,<)
\quad \text{and} \quad
(\mathbb R,<)
$$

These structures are not isomorphic, because one is countable and the other is uncountable.

However, they are elementarily equivalent in the language with a single binary relation symbol $<$, because both are dense linear orders without endpoints, and every first order sentence expressing such properties holds in both structures.

### Elementary Properties

Elementary equivalence captures properties that can be expressed in first order logic, but it cannot detect properties that require higher expressive power.

### Example 4.26

The property of being finite cannot be expressed by any single first order sentence.

As a result, there exist infinite structures that satisfy exactly the same first order sentences as certain finite structures up to any fixed finite level of complexity, even though they differ globally.

This illustrates that first order logic has expressive limitations.

### Lemma 4.27 (Elementary Equivalence is an Equivalence Relation)

Elementary equivalence is reflexive, symmetric, and transitive.

Proof

Reflexivity holds because every structure satisfies exactly the same sentences as itself.

Symmetry holds because equality of theories is symmetric, so if:
$$
\mathrm{Th}(\mathcal A)=\mathrm{Th}(\mathcal B)
$$
then also:
$$
\mathrm{Th}(\mathcal B)=\mathrm{Th}(\mathcal A)
$$

Transitivity holds because equality of sets is transitive, so if:
$$
\mathrm{Th}(\mathcal A)=\mathrm{Th}(\mathcal B)
$$
and:
$$
\mathrm{Th}(\mathcal B)=\mathrm{Th}(\mathcal C)
$$
then:
$$
\mathrm{Th}(\mathcal A)=\mathrm{Th}(\mathcal C)
$$

### Elementary Equivalence and Isomorphism

If two structures are isomorphic, then they are elementarily equivalent, because an isomorphism preserves the truth of all formulas.

However, the converse is not true in general, because two structures may satisfy the same sentences without being structurally identical.

### Lemma 4.28 (Isomorphism Implies Elementary Equivalence)

If:
$$
\mathcal A \cong \mathcal B
$$
then:
$$
\mathcal A \equiv \mathcal B
$$

Proof

An isomorphism is a bijective embedding that preserves all functions and relations, and therefore it preserves the truth of atomic formulas and extends to all formulas by induction on their structure.

Thus every sentence true in $\mathcal A$ is also true in $\mathcal B$, and vice versa, so their theories coincide.

### Elementary Embeddings

Elementary equivalence can be strengthened to a notion that compares structures together with maps between them.

### Definition 4.29 (Elementary Embedding)

Let:
$$
h:\mathcal A \to \mathcal B
$$
be a function between structures.

The map $h$ is an elementary embedding if for every formula $\varphi(x_1,\dots,x_n)$ and all $a_1,\dots,a_n \in A$:
$$
\mathcal A \models \varphi(a_1,\dots,a_n)
$$
if and only if:
$$
\mathcal B \models \varphi(h(a_1),\dots,h(a_n))
$$

Thus an elementary embedding preserves the truth of all formulas, not just atomic ones.

### Lemma 4.30 (Elementary Embeddings are Embeddings)

Every elementary embedding is an embedding.

Proof

Atomic formulas are special cases of formulas, so if a map preserves the truth of all formulas, it in particular preserves and reflects atomic formulas, which is exactly the condition required for an embedding.

### The Role of Theories

The theory of a structure provides a complete logical description of the properties of that structure that can be expressed in the given language.

Two structures are elementarily equivalent if they have the same theory, which means that they cannot be distinguished by any first order sentence.

This idea shifts the focus of model theory from individual structures to classes of structures that share the same theory, and it leads naturally to the study of models of a theory, which are structures satisfying a given set of sentences.

### Limitations of First Order Logic

Elementary equivalence reflects exactly what first order logic can express, but some important properties of structures are not first order definable.

For example, properties such as finiteness, countability, or completeness of an ordered field cannot be captured by first order sentences alone.

As a result, different structures may be elementarily equivalent while differing in these non definable properties, and understanding this limitation is a central theme in model theory.