Each worksheet prints cleanly on A4 or Letter. Answer keys are on a separate page.

The Lumenary · First-year graduate

Model theory

Name: ______________________

Date: ______________________

You will learn to

Define elementary equivalence and elementary embeddings, and use the Tarski–Vaught test
Prove Łoś's theorem and use ultraproducts to give a second proof of compactness
Prove that the theory of dense linear orders without endpoints has quantifier elimination and is $\aleph_0$ -categorical, hence complete
State quantifier elimination for algebraically closed fields and relate it to Chevalley's theorem on constructible sets
Explain the Lefschetz principle and prove the Ax–Grothendieck theorem with it

1.
Which pairs of structures (each in the language $\{<\}$ ) are elementarily equivalent? Choose all that apply.
- A. $(\mathbb{Q}, <)$ and $(\mathbb{R}, <)$
- B. $(\mathbb{N}, <)$ and $(\mathbb{Z}, <)$
- C. $(\mathbb{Z}, <)$ and $(\mathbb{Q}, <)$
- D. $(\mathbb{Q}, <)$ and $(\mathbb{Q} \cap (0,1), <)$
- E.linear orders with $7$ and with $8$ elements
2.
Using the rule for Ehrenfeucht–Fraïssé games on finite linear orders, what is the least $m$ such that the linear orders with $m$ and $m + 1$ elements satisfy the same sentences of quantifier rank at most $4$ ?
3.
In the inductive proof of Łoś's theorem, which step is the only one that uses that $U$ is an ultrafilter (and not merely a filter)?
- A.The negation step
- B.The conjunction step
- C.The existential step
- D.The atomic step
4.
The key lemma says: in a DLO, $\exists x\,(\bigwedge_{a \in A} a < x \wedge \bigwedge_{b \in B} x < b)$ is equivalent to $\bigwedge_{a \in A, b \in B} a < b$ . In $(\mathbb{Z}, <)$ the equivalence fails for $A = \{0\}$ , $B = \{1\}$ . Which axiom of DLO does $\mathbb{Z}$ violate that the proof used here?
- A.Density
- B.No greatest element
- C.No least element
- D.Linearity (totality) of the order
5.
To show that $\varphi(a, b) = \exists x\,(a < x \wedge x < b)$ is not equivalent in $(\mathbb{Z},<)$ to any quantifier-free formula in $a, b$ , which pair of inputs works?
- A. $(0, 1)$ and $(0, 2)$
- B. $(0, 1)$ and $(1, 0)$
- C. $(0, 2)$ and $(5, 7)$
- D. $(3, 3)$ and $(0, 1)$
6.
With orderStructure ℚ and orderStructure ℝ as the structures, which Lean statement correctly formalises “ $(\mathbb{Q}, \le)$ and $(\mathbb{R}, \le)$ are elementarily equivalent but not isomorphic”?
- A.(ℚ ≅[Language.order] ℝ) ∧ ¬ Nonempty (ℚ ≃[Language.order] ℝ)
- B.Nonempty (ℚ ≃o ℝ)
- C.∀ φ : Language.order.Sentence, ℚ ⊨ φ
- D.∃ φ : Language.order.Sentence, ℚ ⊨ φ ∧ ℝ ⊨ φ
7.
The Ax–Grothendieck theorem says injective polynomial maps $K^n \to K^n$ are surjective when $K$ is algebraically closed. Which of these are counterexamples over a field that is not algebraically closed? Choose all that apply.
- A. $x \mapsto x^3$ on $\mathbb{Q}$
- B. $x \mapsto x^p$ on $\mathbb{F}_p(t)$
- C. $x \mapsto x^3$ on $\mathbb{R}$
- D. $x \mapsto x^3$ on $\mathbb{C}$
8.
How many complete $2$ -types over $\emptyset$ does the theory DLO have? (Use quantifier elimination: a type in variables $x, y$ is determined by the atomic formulas it contains.)
9.
Make the key lemma constructive in $\mathbb{Q}$ . Write witness(lows, highs) that takes two lists of Fractions and returns a Fraction $x$ with $a < x$ for every $a$ in lows and $x < b$ for every $b$ in highs, or None if no such $x$ exists. Follow the four cases of the proof.
Computational — Practice

Answer key — Model theory

1.
Elementarily equivalent: $(\mathbb{Q},<)$ and $(\mathbb{R},<)$ , and $(\mathbb{Q},<)$ and $(\mathbb{Q} \cap (0,1),<)$ — all are models of the complete theory DLO. The others are separated by a sentence: a least element ( $\mathbb{N}$ vs $\mathbb{Z}$ ), density ( $\mathbb{Z}$ vs $\mathbb{Q}$ ), and “exactly $7$ elements” (sizes $7$ vs $8$ ).
2.
With $k = 4$ , $L_m \equiv_4 L_{m+1}$ iff $m \ge 2^4 - 1 = 15$ . So the least such $m$ is $15$ : the orders with $15$ and $16$ elements agree on every sentence with at most four nested quantifiers, while $14$ and $15$ do not. (The experiment checks the analogous thresholds $1, 3, 7$ for $k = 1, 2, 3$ by exhaustive search.)
3.
Only the negation step: $M \models \neg\varphi$ iff $\|\varphi\| \notin U$ iff $I \setminus \|\varphi\| \in U$ , and the last equivalence is exactly the ultrafilter property. For a mere filter $F$ , the same induction proves Łoś's equivalence for formulas built from atomic ones by $\wedge$ and $\exists$ only; it fails for $\neg$ , and even for $\vee$ , since $A \cup B \in F$ does not imply $A \in F$ or $B \in F$ .
4.
Density. $0 < 1$ holds, but no integer $x$ has $0 < x < 1$ . The case of the proof with $A$ and $B$ both nonempty is exactly an application of density. This is also why $\mathrm{Th}(\mathbb{Z},<)$ fails to have quantifier elimination in $\{<\}$ (Lean: dlo_elim_core_fails_discrete).
5.
Quantifier-free formulas in $a, b$ only see which of $a < b$ , $a = b$ , $b < a$ holds. The pairs $(0,1)$ and $(0,2)$ both satisfy $a < b$ , so every quantifier-free formula takes the same value on them, while $\varphi(0,1)$ is false and $\varphi(0,2)$ is true. Hence $\mathrm{Th}(\mathbb{Z},<)$ does not have quantifier elimination in $\{<\}$ .
6.
(ℚ ≅[Language.order] ℝ) ∧ ¬ Nonempty (ℚ ≃[Language.order] ℝ). The two conjuncts are the lesson's rat_elem_equiv_real (from completeness of DLO) and rat_not_equiv_real (from the uncountability of ℝ).
7.
Counterexamples: $x \mapsto x^3$ on $\mathbb{Q}$ (misses $2$ ) and the Frobenius $x \mapsto x^p$ on $\mathbb{F}_p(t)$ (misses $t$ ). Over $\mathbb{R}$ the cube map is a bijection, and over $\mathbb{C}$ it is not injective. The proof needs algebraic closure for the transfer: completeness of $\mathrm{ACF}_p$ and the Lefschetz principle apply only to algebraically closed fields.
8.
By QE, a complete type $p(x, y)$ is determined by which of $x < y$ , $x = y$ , $y < x$ it contains, and exactly one of them holds. Each is consistent with DLO. So there are exactly $3$ complete $2$ -types. (Similarly $S_n(\mathrm{DLO})$ is finite for every $n$ — it corresponds to weak orderings of $n$ variables — consistent with DLO being $\aleph_0$ -categorical by the Ryll-Nardzewski theorem.)
9.
```
from fractions import Fraction

def witness(lows, highs):
    if lows and highs:
        lo, hi = max(lows), min(highs)
        return (lo + hi) / 2 if lo < hi else None
    if lows:
        return max(lows) + 1
    if highs:
        return min(highs) - 1
    return Fraction(0)
```
Each branch is one case of the proof: density (midpoint), no greatest element ( $\max + 1$ ), no least element ( $\min - 1$ ), nonemptiness ( $0$ ). When max(lows) >= min(highs), some $a \ge b$ with $a$ in lows, $b$ in highs, so no $x$ can satisfy $a < x < b$ .