Mathematics.

model theory

Model Theory

Mathematical Logic120 minDifficulty9 out of 10

You should know: first order logic

Overview

Model theory studies the relationship between formal languages and their interpretations (models). It asks: which mathematical structures satisfy a given set of sentences? Key results include the completeness theorem, compactness, Löwenheim–Skolem, and the powerful tools of types and saturation used in algebra and geometry.

Intuition

A model is a set \(M\) together with interpretations of the symbols of a language \(\mathcal{L}\). The sentence \(\forall x \exists y\, (y > x)\) is true in the natural numbers but false in any finite model. Model theory asks which sentences are true in which structures, and when two structures are indistinguishable by sentences — elementary equivalence.

Formal Definition

Definition
M=(M,(fiM)i,(RjM)j,(ckM)k)\mathcal{M} = (M, (f_i^\mathcal{M})_i, (R_j^\mathcal{M})_j, (c_k^\mathcal{M})_k)

An L-structure M: a domain with interpretations of function symbols, relation symbols, and constants

model
M⊨φ  ⟺  φ is true in M under Tarski’s inductive definition\mathcal{M} \models \varphi \iff \text{\(\varphi\) is true in \(\mathcal{M}\) under Tarski's inductive definition}

Satisfaction relation

satisfaction
M≡N  ⟺  ∀φ sentence:M⊨φ  ⟺  N⊨φ\mathcal{M} \equiv \mathcal{N} \iff \forall \varphi \text{ sentence}: \mathcal{M} \models \varphi \iff \mathcal{N} \models \varphi

Elementary equivalence: same first-order theory

elementary-equivalence
M≺N  ⟺  M⊆N and ∀aˉ∈M,φ:M⊨φ(aˉ)  ⟺  N⊨φ(aˉ)\mathcal{M} \prec \mathcal{N} \iff \mathcal{M} \subseteq \mathcal{N} \text{ and } \forall \bar{a} \in M, \varphi: \mathcal{M} \models \varphi(\bar{a}) \iff \mathcal{N} \models \varphi(\bar{a})

Elementary substructure relation

elementary-substructure

Notation

NotationMeaning
M⊨φ\mathcal{M} \models \varphiStructure M satisfies sentence φ
Th(M)\text{Th}(\mathcal{M})Complete theory of M: all sentences true in M
M≡N\mathcal{M} \equiv \mathcal{N}M and N are elementarily equivalent
M≺N\mathcal{M} \prec \mathcal{N}M is an elementary substructure of N
tp(aˉ/A)\text{tp}(\bar{a}/A)Type of tuple a over parameter set A

Theorems

Theorem 1: Gödel Completeness Theorem
Afirst−ordersentenceφisprovablefromatheoryTiffφistrueineverymodelofT:T⊢φ  ⟺  T⊨φ.A first-order sentence \varphi is provable from a theory T iff \varphi is true in every model of T: T \vdash \varphi \iff T \models \varphi.
Theorem 2: Compactness Theorem
Asetoffirst−ordersentencesΣhasamodeliffeveryfinitesubsetofΣhasamodel.A set of first-order sentences \Sigma has a model iff every finite subset of \Sigma has a model.
Theorem 3: Löwenheim–Skolem Theorem
Ifacountablefirst−ordertheoryThasaninfinitemodel,ithasmodelsofeveryinfinitecardinality.Inparticular,ifThasamodelofsizeκ≥∣L∣+ℵ0,ithasamodelofanycardinalityλ≥∣L∣+ℵ0.If a countable first-order theory T has an infinite model, it has models of every infinite cardinality. In particular, if T has a model of size \kappa \geq |\mathcal{L}| + \aleph_0, it has a model of any cardinality \lambda \geq |\mathcal{L}| + \aleph_0.
Theorem 4: Morley's Categoricity Theorem
IfacountablecompletetheoryTiscategoricalinsomeuncountablecardinal,itiscategoricalineveryuncountablecardinal.If a countable complete theory T is categorical in some uncountable cardinal, it is categorical in every uncountable cardinal.

Worked Examples

  1. Extend the language with a new constant \(c\). Consider the theory \(T = \text{Th}(\mathbb{N}) \cup \{c > \bar{n} : n \in \mathbb{N}\}\) where \(\bar{n}\) is the numeral for \(n\).

  2. Every finite subset of \(T\) is satisfied by \((\mathbb{N}, m)\) where \(m\) is larger than the largest mentioned numeral. By compactness, all of \(T\) has a model \(\mathcal{M}\).

  3. In \(\mathcal{M}\), the element interpreting \(c\) satisfies \(c > n\) for every standard \(n\) — it is a non-standard natural number.

Answer: Compactness yields a non-standard model of arithmetic containing elements greater than every standard natural number.

Practice Problems

Difficulty 7/10

Use Löwenheim–Skolem to exhibit two elementarily equivalent models of different cardinalities.

Difficulty 8/10

Explain why no first-order theory can characterise \(\mathbb{N}\) up to isomorphism.

Difficulty 9/10

Prove that the class of finite groups is not axiomatisable in first-order logic.

Historical Background

Gödel proved the completeness theorem for first-order logic in 1929 and the incompleteness theorems in 1931. Tarski formalised the notion of truth in a model in the 1930s. Abraham Robinson developed non-standard analysis via model theory in the 1960s. Morley's categoricity theorem (1965) launched stability theory, later developed by Shelah into a vast classification programme.

  1. 1929

    Gödel proves the completeness theorem for first-order logic

    Kurt Gödel

  2. 1930s

    Tarski develops the formal semantics of truth

    Alfred Tarski

  3. 1961

    Abraham Robinson founds non-standard analysis using model theory

    Abraham Robinson

  4. 1965

    Morley proves his categoricity theorem; stability theory begins

    Michael Morley

Summary

  • A model (structure) assigns concrete interpretations to the symbols of a formal language.
  • Completeness: \(T \vdash \varphi \iff T \models \varphi\) — provability equals truth in all models.
  • Compactness: a theory has a model iff every finite subtheory does.
  • Löwenheim–Skolem: theories with infinite models have models of every infinite cardinality.
  • Stability and categoricity (Morley, Shelah) classify theories by the number of their models.

References

  1. BookMarker, D. Model Theory: An Introduction. Springer, 2002.
  2. BookChang, C. & Keisler, H. Model Theory. Elsevier, 1990.