Logik II: Model theory

Martin Bays

Universität Münster, Wintersemester 2019-2020^{∗} version d4657169 en^{†}

1 Overview

• A key goal of model theory is to understand the definable sets of a structure M, the subsets of powers M^{n} defined by formulas.

• Gödel vs Tarski: Some structures have uncontrollably wild definable sets, becoming ever more complicated as we allow more quantifiers; for example, in (N; +, ·), already with one unbounded existential quantifier we can define arbitrary recursively enumerable sets. However, it is a remarkable fact that many structures important to mathematics avoid these Gödelian phenomena and are “tame”: their definable sets are well-controlled (in particular, all definable by formulas with only a few quantifiers), they often have decidable theories, and sometimes the models of the theory being classifiable up to isomorphism. Examples include:

– (ℂ; +, ·), (𝔽_{p}^{alg}; +, ·), (ℝ; +, ·), (ℚ_{p}; +, ·);

– (ℚ; <);

– Vector spaces;

– (ℤ; +), (ℤ; ∗), (ℤ; +, <) (but not (ℤ; ·, <)! CHECKME);

– (ℝ; +, ·, x ↦ e^{x});

– (ℂ; +, ·, x ↦ x^{ζ}) (for most ζ ∈ ℂ);

– Compact Lie groups ¡—e.g.—¿ (SO_{3}(ℝ); ·);

– (𝔽_{p}; +, ·) for an “infinite” (pseudofinite) prime p;

– Compact complex manifolds (complex tori, Calabi-Yau manifolds, etc);

– Differential and difference equations (in a certain sense);

– Free groups (F_{n}; ∗).

∗These lecture notes are licensed under the Creative Commons Attribution-Sharealike licence CC-BY-SA 4.0 https://creativecommons.org/licenses/by-sa/4.0/ by Martin Bays 2019 .

†Dies Skript ist auch auf Deutsch verfügbar.

We will examine only a fraction of this richness in this course, but we will develop tools with wide applicability.

• We often study a structure by considering other models of its theory. We will see three key results of this kind. Let M be an infinite L-structure.

– “Monster models exist”: M elementarily extends to a highly saturated and homogeneous model of its theory. We can then study M by working in this “smooth” extension; this is an incarnation of Robinson’s non-standard analysis.

– (L countable) Ryll-Nardzewski: M has a unique countable model of its theory iff for each n ∈ N there are only finitely many L-definable subsets of M^{n}.

– (L countable) Baldwin-Lachlan: for an uncountable cardinal κ, M has a unique model of its theory of cardinality κ iff M is prime and minimal over a strongly minimal set defined over the prime model. (We’ll define these terms later; a strongly minimal set is a particularly straightforward structure, and being prime and minimal over it implies that the definable sets of M are “constructed” from its definable sets in a certain sense.)

2 Preliminaries

We work in ZFC throughout the course.

2.1 Syntax and structure

• A (first-order) (1-sorted) language is a set L of relation symbols, function symbols, and constants.

• An L-structure M = (M; (R^{M})_{R}, (f^{M})_{f}, (c^{M})_{c}) is a non-empty set M equipped with interpretations of the symbols of L:

– R^{M} ⊆ M^{n} for R ∈ L an n-ary relation symbol;

– f^{M} : M^{n} → M for f ∈ L an n-ary function symbol;

– c^{M} ∈ M for c ∈ L a constant.

Often, we write M to refer to the underlying set M.

• An L-term is a variable, a constant, or f(t_{1}, …, t_{n}) where t_{i} are L-terms and f is an n-ary function symbol.

• An atomic L-formula is t_{1} ≐ t_{2} or Rt_{1} … t_{n} where t_{i} are L-terms and R is an n-ary relation symbol.

• An L-formula is an atomic L-formula or ¬ϕ or (ϕ∧ϕ′) or ∃x.ϕ where ϕ, ϕ′ are L-formulas and x is a variable.

• An L-sentence is an L-formula with no free variables.

• For M an L-structure and σ an L-sentence, M ⊨ σ is defined recursively.

• Abbreviations:

(ϕ ∨ ψ) ↦ ¬(¬ϕ ∧ ¬ψ)
(ϕ → ψ) ↦ (¬ϕ ∨ ψ)
(ϕ ↔ ψ) ↦ ((ϕ → ψ) ∧ (ψ → ϕ))
∀x.ϕ ↦ ¬∃x.¬ϕ
x ≐ y̸ ↦ ¬x ≐ y

• If L′ ⊇ L and M is an L′-structure, we write M|_{L} for the corresponding L-structure, and call M|_{L} the reduct of M to L, and M an expansion of M|_{L} to L′.

• If M is an L-structure and A ⊆ M, the expansion by constants for A is the expansion M_{A} of M to L(A) := L ˙∪A defined by a^{M_{A}} := a.

• If ϕ = ϕ(\overline{x}, \overline{y}) (meaning the free variables of ϕ are among \{x_{1}, …, x_{n}, y_{1}, …, y_{m}\}) and a_{i} ∈ A, we write ϕ(\overline{a}, \overline{y}) for the L(A)-formula obtained by substituting a_{i} for x_{i} (i = 1, …, n). We write M ⊨ ϕ(\overline{a}) to mean M_{A} ⊨ ϕ(\overline{a}).

• A partial isomorphism of L-structures is a partial function θ : M −−→ N such that for any atomic L-formula ϕ(x_{1}, …, x_{n}) and any a_{i} ∈ dom(θ), M ⊨ ϕ(\overline{a}) iff N ⊨ ϕ(θ(\overline{a})). If this holds for any L-formula ϕ, we call θ a partial elementary map.

• An embedding is a total partial isomorphism θ : M ⟶ N.

• An elementary embedding is a total partial elementary map θ : M ⟶^{⪯} N.

• An isomorphism is a surjective embedding θ : M ⟶^{≅} N.

• A substructure (resp. elementary substructure), of an L-structure N is an L-structure M on a subset of N such that the inclusion ι : M → N is an embedding (resp. an elementary embedding).

• We write M ≤ N or M ⊆ N for a substructure, and M ⪯ N for an elementary substructure.

2.2 Theories

• An L-theory is a set of L-sentences.

• The theory of an L-structure M is

Th(M) := {σ : M ⊨ σ, σ is an L-sentence}.

• An L-structure M is a model of an L-theory T,

M ⊨ T,

if M ⊨ σ for all σ ∈ T.

• T is consistent if it has a model.

Remark 2.1. T is consistent iff T ⊭ ¬∃x.x ≐ x.

• T ⊨ σ means: M ⊨ σ for any M ⊨ T. We also write T ⊢ σ.

• A consistent L-theory T is complete if for any L-sentence σ

T ⊨ σ or T ⊨ ¬σ.

• L-structures M, N are elementarily equivalent, M ≡ N, if Th(M) = Th(N).

Remark 2.2. T is complete iff M ≡ N whenever M, N ⊨ T.

Remark 2.3. If A is a common subset of L-structures M and N, then id_{A} : M −−→ N is partial elementary iff M_{A} ≡ N_{A}.

In particular, M ⪯ N iff M_{M} ≡ N_{M}.

3 Ultraproducts

Let I be a set.

∅ ≠ B ⊆ P(I) is a filter base if

• X, Y ∈ B ⇒ ∃Z ∈ B.X ∩ Y ⊇ Z;

• ∅ ∉ B.

A maximal filter base U is an ultrafilter; equivalently: U is a filter base, and for any X ⊆ I, gilt

X ∈ U or I \ X ∈ U.

As an immediate consequence of Zorn’s Lemma, we have

Fact 3.1. Any filter base B ⊆ P(I) extends to an ultrafilter B ⊆ U ⊆ P(I) .

Remark 3.2. Fact ?? is not a theorem of ZF, and it is strictly weaker than the axiom of choice modulo ZF.

Remark 3.3. Ultrafilters are upwards-closed: if X ⊆ Y then X ∈ U ⇒ Y ∈ U. An upwards-closed filter base is a filter.

If U ⊆ P(I) is an ultrafilter and (A_{i} : i ∈ I) are sets, the ultraproduct ∏_{i→U} A_{i} (also written ∏_{i∈I} A_{i}/U) is the quotient of the product ∏_{i} A_{i} by the equivalence relation

(a_{i})_{i} ∼^{U} (a′_{i})_{i} iff {i : a_{i} = a′_{i}} ∈ U.

If a_{i} ∈ A_{i}, let lim_{i→U} a_{i} := (a_{i})_{i}/ ∼^{U}∈ ∏_{i→U} A_{i}.

If U ⊆ P(I) is an ultrafilter and a_{i} are elements of sets A_{i} (i ∈ I), the ultralimit lim_{i→U} a_{i} be the equivalence class of the sequence (a_{i})_{i} under the equivalence relation (a_{i})_{i} ∼^{U} (a′_{i})_{i} iff {i : a_{i} = a′_{i}} ∈ U. If A_{i} are sets, the ultraproduct is the set of all ultralimits,

∏_{i→U} A_{i} := ^{∏_{i∈I} A_{i}}/_{∼^{U}} = { lim_{i→U} a_{i} : a_{i} ∈ A_{i}} .

We have lim_{i→U}(a_{i}, b_{i}) = (lim_{i→U} a_{i}, lim_{i→U} b_{i}).

For functions f_{i} : A_{i} → B_{i}, we define

lim_{i→U} f_{i} : ∏_{i→U} A_{i} → ∏_{i→U} B_{i}

by

( lim_{i→U} f_{i})( lim_{i→U} a_{i}) := lim_{i→U} f_{i}(a_{i}).

If (M_{i} : i ∈ I) are L-structures, the ultraproduct M = ∏_{i→U} M_{i} is the L-structure such that

• as sets, M := ∏_{i→U} M_{i};

• R^{M} := ∏_{i→U} R^{M_{i}} for R ∈ L a relation symbol;

• f^{M} := lim_{i→U} f^{M_{i}} for f ∈ L a function symbol;

• c^{M} := lim_{i→U} c^{M_{i}} for c ∈ L a constant symbol.

Theorem 3.4 (Łos). For L-structures M_{i}, an L-formula ϕ(\overline{x}), and \overline{a}_{i} ∈ M_{i},

∏_{i→U} M_{i} ⊨ ϕ( lim_{i→U} \overline{a}_{i}) iff \{i : M_{i} ⊨ ϕ(\overline{a}_{i})\} ∈ U.

Proof. Exercise.

If U ⊆ P(I) is an ultrafilter and M is an L-structure, the ultrapower M^{U} is ∏_{i→U} M. Then M ⊆ M^{U} via the

Lemma 3.5. With respect to the diagonal embedding

a ↦ lim_{i→U} a,

M is an elementary substructure, M ⪯ M^{U}.

Proof. Exercise.

An ultrafilter U is principal if there is i_{0} ∈ I such that U = {X ⊆ I : i_{0} ∈ X}. Then ∏_{i→U} M_{i} ≅ M_{i_{0}}.

4 Compactness

Theorem 4.1 (Compactness). Suppose every finite subset of an L-theory T is consistent. Then T is consistent.

Proof. Say M_{T′} ⊨ T′ for T′ ⊆_{fin} T.

For T′ ⊆_{fin} T, let [T′] = {T′′ : T′ ⊆ T′′ ⊆_{fin} T } ⊆ P^{fin}(T). Let B = {[T′] : T′ ⊆_{fin} T } ⊆ P(P^{fin}(T)). Then B is a filter base, since [T′] ∩ [T′′] = [T′ ∪ T′′], and [T′] ≠ ∅ since T′ ∈ [T′]. Let U ⊇ B be an ultrafilter on P^{fin}(T).

Let M = ∏_{T′→U} M_{T′}.

Then for σ ∈ T, {T′ : M_{T′} ⊨ σ} ⊇ {T′ : σ ∈ T′} = [{σ}] ∈ U, so by Łos, M ⊨ σ.

So M ⊨ T, so T is consistent.

5 Elementary extensions

Theorem 5.1 (Tarski test). Suppose M is an L-structure and A is a subset. Then TFAE:

(i) A is the domain of an elementary substructure;

(ii) for every L(A)-formula in one free variable ϕ(x), if M ⊨ ϕ(b) for some b ∈ M, then M ⊨ ϕ(a) for some a ∈ A.

Proof.

(i) ⇒ (ii): Let A be the elementary substructure with domain A. Then if M ⊨ ∃x.ϕ(x), then A ⊨ ∃x.ϕ(x); so say a ∈ A and A ⊨ ϕ(a); but then M ⊨ ϕ(a) by elementarity, as required.

(ii) ⇒ (i): By (ii) with ϕ(x) = x ≐ x we have A ≠ ∅, and by (ii) with ϕ(x) = x ≐ f(\overline{a}) we have that A is closed under functions. So A is the domain of a substructure A.

We show by induction on complexity that for any L(A)-sentence σ,

A ⊨ σ ⇔ M ⊨ σ.

This holds for σ atomic by the definition of substructure, and if it holds for σ and σ′ then clearly it holds for ¬σ and (σ ∧ σ′).

So suppose σ = ∃x.ϕ(x), and the induction hypothesis holds for ϕ(a) for any a ∈ A .

If A ⊨ σ, then A ⊨ ϕ(a) for some a ∈ A, so M ⊨ ϕ(a) by the induction hypothesis, so M ⊨ σ. Conversely, if M ⊨ σ, then M ⊨ ϕ(b) for some b ∈ M, so, by (i), M ⊨ ϕ(a) for some a ∈ A, so A ⊨ ϕ(a) by the induction hypothesis, so A ⊨ σ.

TODO: Lowenheim-Skolem; Vaught?

6 Types and Saturation

… Example: non-principal countable ultrapower in countable lang is ℵ_{1}-saturated.

7 Quantifier elimination