Exploration 4: Diagrams

November 7, 2023.

The goal of this exploration is to show that all properties of a model $M$ can be captured by a certain theory (its diagram). In particular, two models are isomorphic if they have the same diagram.

In this section, we show that every embedding can be written equivalently as a model. (Diagram lemma)

Recall that embeddings are precisely maps which preserve existential formulas: $A\models\phi(\bar{a})$ iff $B\models\phi(f\bar{a})$ for all $\exists_1$-formulas $\phi$.

How do we construct an embedding $f:A\to B$? It would mean finding a name in $B$ for every element in $A$, such that every existential formula $\phi$ is preserved. This seems hard to verify and construct! With all the tools we have in model theory, there must be an easier way.

We’ll generalize the above procedure. We name every element of $A$ by extending the language with a constant $c_a$ for every element $a\in A$. We define the diagram of $A$, $diag(A)$, as the theory where for every atomic sentence $\phi(\bar{a})$ or its negation $\lnot\phi(\bar{a})$ true in $A$ for elements $\bar{a}$, $diag(A)$ contains the sentence $\phi(\bar{c}_a)$ or $\lnot\phi(\bar{c}_a)$ for the corresponding $\bar{c}_a$.

Note that by construction, every finite subset of $diag(A)$ is modelled by $A$. So by compactness, $diag(A)$ has a model. Let $B$ be any model of $diag(A)$. Then there is an embedding $f:A\to B$ where each element of $A$ is mapped to the interpretation of the corresponding $c_a$ in $B$. And f is an embedding because it preserves all atomic formulas, because $B$ models all atomic sentences in $diag(A)$ and therefore all atomic formulas.

This means that A embeds into any model of $diag(A)$. Conversely, every embedding of A is a model of $diag(A)$!

This is called the diagram lemma, which states that the following are equivalent:

• B ⊨ diag(A).
• A (uniquely up to isomorphism) embeds into B.
• f : A → B is an embedding.

Usually the first criterion is written in an even weaker form:

• B can be expanded to a model of diag(A).

This is because we could just use the diagram lemma above to obtain the unique embedding f : A -> B’, and then restrict the codomain to B by taking the reduct of the expansion B’. The reverse direction is trivial; if A embeds into B then we know that B models diag(A), and any expansion of B must also model diag(A).

<-──────-><-─────–>

In this section, we show that every elementary embedding can be written equivalently as a model. (Elementary diagram lemma)

There is a simple extension of the diagram lemma to elementary embeddings (embeddings that preserve all first-order sentences). Take the elementary diagram of A, eldiag(A), as the theory where for every first-order sentence ϕ(a̅) true in A for elements a̅, eldiag(A) contains the sentence ϕ(c̅ₐ) for the corresponding c̅ₐ.

By the same argument in the previous section, A elementarily embeds into any model of diag(A) via the unique (up to isomorphism) mapping of a to the model’s interpretation of cₐ.

This is the elementary diagram lemma, stating the following are equivalent:

• B can be expanded to a model of eldiag(A).
• A (uniquely) elementarily embeds into B.
• f : A → B is an elementary embedding.

We can even extend this to a theorem showing when two models are elementarily equivalent (i.e. model the same first-order sentences). One way to show two models are elementarily equivalent is to show that they elementarily embed into each other. By the elementary diagram lemma above, we have:

• A ≡ B when:
  • A can expand to a model of eldiag(B), and
  • B can expand to a model of eldiag(A).

The criterion can be made even simpler. Since we always have A ⊨ eldiag(A) and B ⊨ eldiag(B), we only need eldiag(A) ⊆ eldiag(B), and vice versa. Therefore,

• A ≡ B when eldiag(A) = eldiag(B).

That is, if A and B share the same elementary diagram, then they are elementarily equivalent!

Now we’ll show the converse: when two models are elementarily equivalent, they share the same elementary diagram.

• If A ≡ B, then any sentence ϕ in L is either in eldiag(A) or not.
• If ϕ ∈ eldiag(A) then A ⊨ ϕ.
• Since A ≡ B, B ⊨ ϕ, and therefore ϕ ∈ eldiag(B).
• So eldiag(A) ⊆ eldiag(B).
• The same argument can be used in the other direction, so eldiag(B) ⊆ eldiag(A).
• Therefore the two elementary diagrams are the same.

So in the end we have:

• A ≡ B iff eldiag(A) = eldiag(B).

< Back to category Exploration 4: Diagrams (permalink)
Exploration 3: Homomorphism preservation theorems Intro to model theory

---