Model theory Study Guide

📖 Core Concepts Signature (language) – Set of non‑logical symbols (constants, functions, relations) with fixed arities. Structure – A domain together with interpretations of all symbols of a given signature. Theory – A set of first‑order sentences (axioms). Model – A structure that satisfies every sentence of a theory (notation:  $M\models T$). Satisfiable vs. Consistent – By Gödel’s completeness theorem, a theory is satisfiable ⇔ it is syntactically consistent (no contradiction can be proved). Complete theory – For each sentence $\varphi$, either $\varphi\in T$ or $\neg\varphi\in T$. Elementary substructure – Substructure $N\subseteq M$ such that every first‑order formula with parameters from $N$ has the same truth value in $N$ as in $M$. Elementary embedding – Injective map $f:M\to N$ preserving truth of all formulas; its image is an elementary substructure of $N$. Compactness – If every finite subset of a set of sentences is satisfiable, the whole set is satisfiable. Löwenheim–Skolem – Any infinite structure in a countable signature has a countable elementary substructure; conversely, for any infinite cardinal $\kappa$, smaller structures embed elementarily into size‑$\kappa$ structures. Definable set – Subset of $M^n$ defined by a formula (with or without parameters). Quantifier elimination (QE) – Every formula is equivalent (modulo the theory) to a quantifier‑free one; definable sets become Boolean combinations of atomic formulas. Model‑completeness – Every embedding between models of the theory is elementary; equivalently every formula is equivalent to an existential quantifier‑free formula. 📌 Must Remember Gödel Completeness: $T$ consistent ⇔ $T$ has a model. Compactness Corollary: Any unsatisfiable theory contains a finite unsatisfiable subset. Löwenheim–Skolem Consequence: A theory with an infinite model has models of all infinite cardinalities (in a countable language). QE Examples: Real closed fields, algebraically closed fields, Boolean algebras. Model‑completeness ⇔ Existential QE: Every formula ≡ $\exists y\,\psi(x,y)$ with $\psi$ quantifier‑free. ω‑categoricity ⇔ finitely many $n$‑types: For each $n$, $Sn(T)$ is finite, all types isolated. Morley’s Categoricity Theorem: For a countable language, categoricity in one uncountable cardinal ⇒ categoricity in all uncountable cardinals. Stability Spectrum: Countable $T$ is either unstable, strictly stable (stable above some $\lambda$), or superstable (stable in every infinite $\kappa$). Łoś’s Theorem: $\varphi$ holds in an ultraproduct $\prod Mi/U$ iff $\{i: Mi\models\varphi\}\in U$. 🔄 Key Processes Checking elementary substructure (Tarski–Vaught Test) For each formula $\exists y\,\psi(a,y)$ with $a\in N$, if $M\models\exists y\,\psi(a,y)$ then find $b\in N$ with $M\models\psi(a,b)$. Applying Quantifier Elimination Rewrite each formula step‑by‑step using known QE for the theory (e.g., replace $\exists x (p(x)=0)$ by the discriminant condition in ACF). Constructing an Ultraproduct Choose an index set $I$, structures $(Mi){i\in I}$, and an ultrafilter $U$ on $I$. Form the product $\prodi Mi$, then quotient by the relation “agree on a set in $U$”. Realising a Type Given a type $p(x)$ over $A$, enlarge the model to a saturated elementary extension $M'$ with $|M'|>|A|$; $p$ is realised in $M'$. Testing ω‑categoricity Compute $Sn(T)$ for small $n$. If each is finite, $T$ is ω‑categorical. 🔍 Key Comparisons Signature vs. Reduct vs. Expansion Signature: full list of symbols. Reduct: forget some symbols → smaller language. Expansion: add new symbols with interpretations. Elementary Substructure vs. Substructure Substructure: closed under functions, inherits relations. Elementary: additionally preserves truth of all formulas with parameters. Model‑complete vs. Quantifier‑eliminable Model‑complete: every embedding is elementary (existential QE). QE: stronger; every formula is equivalent to a quantifier‑free formula. Atomic vs. Saturated Atomic: every realized type over $\emptyset$ is isolated. Saturated: realises all types over small parameter sets (size $<|M|$). ω‑categorical vs. κ‑categorical (uncountable) ω‑categorical: unique countable model up to iso. κ‑categorical (uncountable): unique model of size $\kappa$; Morley’s theorem links all uncountable $\kappa$. ⚠️ Common Misunderstandings “Compactness ⇒ Finite models exist.” Compactness only guarantees a model if every finite subset is satisfiable; it does not force the model to be finite. “Quantifier elimination makes a theory decidable automatically.” QE gives a decision procedure only when the quantifier‑free fragment is itself decidable (as in ACF, RCF, Boolean algebras). “All complete theories are ω‑categorical.” Completeness is about deciding every sentence; ω‑categoricity is a structural uniqueness property and fails for many complete theories (e.g., dense linear orders without endpoints). “Saturated = atomic.” They are opposites: atomic models have only isolated types, while saturated models realise all possible types (many non‑isolated). 🧠 Mental Models / Intuition Structures as “worlds” where the language’s symbols tell you the “rules of the game”. Elementary embedding = “perfect copy” of the source’s logical landscape inside the target. Compactness = “local consistency → global consistency”: if every finite piece fits, the whole puzzle can be assembled. Ultraproduct = “majority vote” across an indexed family: a statement holds in the product if it holds on a “large” set of indices (in the ultrafilter). ω‑categoricity = “only one way to build a countable world”; any two countable models are forced to look the same. 🚩 Exceptions & Edge Cases Finite signatures vs. uncountable signatures – Löwenheim–Skolem and categoricity results are stated for countable signatures; they may fail or need modification for larger languages. Compactness fails in finite model theory – No guarantee that locally consistent finite sentences have a finite model. QE does not imply model‑completeness in the reverse direction: a model‑complete theory may still need quantifiers for some formulas. Saturation requires enough cardinality – A structure of size $\aleph0$ cannot be $\aleph1$‑saturated. 📍 When to Use Which To prove a theory has no new models of a given size: use Löwenheim–Skolem (countable → countable submodel) or Morley’s categoricity theorem. To decide a sentence in ACF, RCF, Boolean algebras: apply quantifier elimination → reduce to quantifier‑free truth check. When checking elementary equivalence: compare ultrapowers (if ultrapowers are isomorphic, the originals are elementarily equivalent). To build a model omitting a type: invoke the Omitting Types Theorem (countable case). To classify stability: compute number of $1$‑types over sets of size $\kappa$; if ≤ $\kappa$, the theory is $\kappa$‑stable. 👀 Patterns to Recognize Finite‑vs‑Infinite dichotomy – Many theorems (compactness, Löwenheim–Skolem) hinge on infiniteness of the language or domain. “Every definable set is a Boolean combination of …” – Appears when QE holds (e.g., semialgebraic sets for RCF). Isolation of types = finiteness of $Sn(T)$ – Spot this pattern when testing ω‑categoricity. Saturation ↔ Realising all small types – When a model is “big enough,” it automatically realises any consistent description over a smaller set. 🗂️ Exam Traps Confusing “complete theory” with “categorical.” – A theory can be complete without being ω‑categorical (e.g., theory of dense linear orders without endpoints). Assuming compactness works for finite structures. – In finite model theory, compactness fails; a finite‑consistent set may have no finite model. Believing every model‑complete theory has QE. – Counterexample: theory of algebraically closed fields is model‑complete and has QE, but there are model‑complete theories without QE. Misreading “saturated” as “maximally large.” – Saturation is about realising types, not about cardinality alone. Using Löwenheim–Skolem in uncountable languages without justification. – The theorem’s standard form requires a countable signature. --- Study this guide repeatedly; the bullet‑point format makes quick scanning before the exam painless and effective.