Model Theory in Mathematical Logic: Key Concepts

The Löwenheim-Skolem theorem states that if a first order theory has an infinite model, it has models of every infinite cardinality. The video explains this seems paradoxical for set theory: if ZFC has a model, it should have models of all sizes, including countable models. This is possible because the 'size' of a model is measured externally, while the model's internal notion of size might differ. The video notes that standard models (where membership agrees with meta-theory) can be countable, while non-standard models might have different internal cardinalities. This theorem shows that first order logic cannot pin down the exact size of infinite structures.

Skolem's Paradox reveals a fundamental limitation of first-order logic in mathematics. The Löwenheim-Skolem theorem states that any consistent first-order theory with an infinite model also has a countable model. Applied to set theory, this means if set theory is consistent, it has a countable model where the universe of sets is countably infinite. Yet within this model, Cantor's theorem proves that the real numbers are uncountable. This seems contradictory: how can a set be uncountable if the entire model is countable? The resolution lies in distinguishing internal and external perspectives. From inside the model, all axioms hold and the reals are uncountable. From outside, the model itself has only countably many elements, and there exists a bijection between the model's elements and natural numbers that is not itself an element of the model. This shows that uncountability is relative to a model, not absolute, and that first-order logic cannot pin down the cardinality of infinite sets.

The Löwenheim-Skolem theorem states that any first-order mathematical theory (including Peano arithmetic and ZFC set theory) that contains an infinite model has a countable model. This means that even theories containing uncountable infinities can be satisfied by a countable collection of objects. This theorem challenges our intuitive understanding of different sizes of infinity.

The Löwenheim-Skolem theorems state that for any infinite structure, one can always find elementary substructures or elementary extensions of almost arbitrary cardinality, with the only restriction being the cardinality of the language; specifically, if κ is a cardinal at least as large as the language's cardinality and at most the structure's cardinality, there exists an elementary substructure of cardinality κ (downward version), and conversely, any consistent theory with an infinite model has models of every cardinality at least as large as the language's cardinality (upward version).

An elementary diagram of a model M consists of all atomic formulas and their negations true in M, with new constants for each element. A model N satisfies the elementary diagram of M iff there exists an elementary embedding of M into N. An elementary embedding preserves truth of all first-order formulas with parameters from the domain. The Löwenheim-Skolem Theorems describe model cardinalities: the upward version states that if a theory has an infinite model, it has models of every infinite cardinality; the downward version states that if a theory has a model of cardinality λ, it has models of every infinite cardinality ≤ λ. The proof uses the Compactness Theorem: enrich the language with new constants, add axioms for distinctness, and apply compactness. For countable languages, this shows theories have models of all infinite sizes.

This section introduces quantifier elimination, a fundamental model theory concept where every formula in a structure is equivalent to a quantifier-free formula. The lecture establishes that this property enables decidability: if truth of quantifier-free formulas can be checked algorithmically, truth of any formula can be determined. The first major example proves quantifier elimination for integers with constant 0, successor function S, and equality. The algorithm involves: converting to Prenex normal form, eliminating quantifiers one by one starting from the last, converting existential quantifiers to disjunctive normal form and distributing, and analyzing atomic formulas to eliminate quantifiers through appropriate substitutions. This simple case establishes the technical framework used in more complex theories.

A theory admits quantifier elimination if every formula is logically equivalent to a quantifier-free formula; this occurs precisely when, for any two models of the theory with a common substructure, they agree on the truth values of all quantifier-free formulas, and such theories have the property that any substructure is an elementary substructure.

Model theory distinguishes between internal and external perspectives—internal truth refers to what is true within a model, while external truth refers to what is true in the real world of mathematicians outside the model. This led to concepts like elementary equivalence—two structures can satisfy the same first-order formulas while being non-isomorphic. A theory is categorical in a cardinality K if all its models of cardinality K are isomorphic. Peano Arithmetic is not categorical in any infinite cardinality, with non-standard models containing elements larger than all standard numbers. Quantifier elimination transforms formulas into equivalent quantifier-free forms. Presburger eliminated quantifiers for arithmetic of addition, showing the theory of integers with addition and order is decidable. In this theory, every definable set in one variable is a finite union of arithmetic progressions, congruence classes, and finite intervals—called semilinear sets.

Quantifier elimination is a property of a theory where every formula is logically equivalent to a quantifier-free formula; a theory admits quantifier elimination if for every formula φ, there exists a quantifier-free ψ such that the theory proves φ ↔ ψ. Key criteria include: (1) For any two models M and N of the theory with common substructure A, and any tuple a from A, M satisfies φ(a) if and only if N satisfies φ(a); (2) The theory can eliminate existential quantifiers, meaning for any quantifier-free φ and variable x, there exists a quantifier-free ψ such that the theory proves ∃xφ ≡ ψ. The theory of dense linear order without endpoints (DLO) serves as a classic example of a theory with quantifier elimination.

Quantifier elimination is a proof technique where one eliminates quantified variables from a formula by performing computations on the database. Starting with a formula with K variables, one repeatedly eliminates one variable at a time by checking how many values satisfy the remaining constraints and modifying the database accordingly. After eliminating all quantifiers, the result becomes a quantifier-free formula whose solutions can be enumerated efficiently through Cartesian products with constant-sized exceptions.

The combination of results by Morley and Shelah generated classification theory, which aims to classify all first-order theories into classes (stable, superstable, etc.) based on combinatorial behavior of models, number of types, and saturation. This is a major program within logic with implications for concrete mathematics. Often, theories from algebra or analysis fall into one of these classes. The theory of algebraically closed fields of fixed characteristic is ω-stable and superstable, categorical in every uncountable power. The theory of non-abelian free groups is stable but not superstable. The theory of additive groups of modules is stable but not superstable. Model theory has had a huge impact on modern algebra. Tarski's proof of decidability of the theory of real closed fields implied that geometric problems (like determining whether a polynomial equation has real solutions) are decidable and founded the theory of semialgebraic sets. Tarski and Seidenberg showed that many geometric properties of semialgebraic sets can be deduced from logical formulations. A notable application to number theory was done by Ax and Kochen in the 1960s, who derived the solution of a conjecture about the density of solutions of certain equations. In the 1990s, Hrushovski applied model theory to solve problems in combinatorics and algebraic geometry, including the functional case of the Mordell-Lang conjecture. Wilkie showed that the reals with the exponential function are o-minimal, implying that any definable set is a finite union of points and monotonic intervals. This discovery has both theoretical importance and practical significance, leading to tame versions of analytic theorems. The semantic view of theories defines a scientific theory as the set of its models, helping avoid problems of strict syntactic verificationism. In practice, physicists construct models like climate models, atomic models, and cosmological models, and a general law is considered valid if all these real models satisfy it. The formal semantics of natural languages, including Montague Grammar, is infused with model-theoretic notions. To define the meaning of 'every student reads a book,' one constructs a model of individuals, properties, and relations, and the sentence is true if and only if in that structure, for every student, there exists a book such that the student reads it. Web semantic technologies like OWL are based on description logics with model-theoretic semantics. A reasoner can determine if an ontology has models or is inconsistent. Many verification tools, called model checkers, literally control models of systems. In the chip industry, to verify that a memory access protocol does not deadlock, one constructs a finite model—a state machine representing all possible configurations. One expresses the property 'never deadlock' in temporal logic like CTL or LTL and uses an algorithm to verify if that formula is true in that model. If not true, the tool provides a countermodel—a sequence of states violating the property. A relational database can be viewed as a model of a set of formulas—the integrity constraints. SQL essentially implements first-order logic with extensions on tables. A query like 'select' is like finding all X such that P(X) in a model. When using search engines, filters on tables, and similar tools, one is unconsciously using model inference—finding all X in the model (dataset) that satisfy F(X). Sudoku can be viewed as a satisfiability problem—finding a model of a finite theory. The constraints of Sudoku are universal formulas, and the solution is an interpretation (assignment of digits to cells) that satisfies all formulas. More important problems like optimization and planning in artificial intelligence are often reduced to satisfiability problems. A SAT solver searches for a Boolean interpretation that makes all clauses true. When a smartphone solves a scheduling problem, calculates a route, or computes a flight schedule, behind it is often a SAT or SMT solver—essentially the search for a model. The correctness theorem states that if any formula is provable, then it is true in every model. No sound system can prove false theorems. Conversely, the completeness theorem states that if any formula is true in every model of a theory, then it is provable. These results establish the equivalence between syntactic consequence (via formal proofs) and semantic consequence (via truth in all models) for first-order logic. For classical first-order logic, Gödel's completeness theorem shows that the syntactic characterization of consequence (via formal proofs) and the semantic characterization (via truth in all models) coincide. A formula φ is provable from Γ if and only if φ is a logical consequence of Γ. In virtue of correctness and completeness, Γ is consistent if and only if Γ has a model. This establishes a direct bridge between the proof-theoretic notion of consistency (no derivation of absurdity) and the model-theoretic notion of satisfiability. Gödel showed the relative consistency of the continuum hypothesis by constructing an inner model where it holds. Cohen showed the relative consistency of its negation by constructing a model where it does not hold. Together, these results imply that the continuum hypothesis is independent of ZFC. The proof-theoretic approach (Jensen, elimination of cuts, transfinite induction) provides syntactic consistency proofs for arithmetic theories. The model-theoretic approach (set-theoretic, Gödel's constructible universe, Cohen's forcing) provides relative consistency by constructing models where certain axioms hold and others fail. For the completeness theorem, there are at least two non-isomorphic models of T—one where G is true and one where G is false. In general, if a first-order theory with infinite models is incomplete, it cannot be categorical; the converse does not hold. There are complete theories that are not categorical. Categoricity in an infinite cardinality implies completeness without assuming any algorithmic decidability. When facing a logical problem, one wants to verify whether a certain sentence follows from axioms. There are two approaches: try to find a formal proof of φ from Γ (proof-theoretic approach); try to find a model of Γ in which φ is false (model-theoretic approach, i.e., construct a counterexample). For classical first-order logic, the two paths are mutually exclusive (by correctness) and exhaustive (by completeness). This duality is exploited in decision algorithms. Craig's interpolation theorem states that if α logically implies β, there exists a formula γ containing only symbols common to α and β such that γ is a consequence of α and β is a consequence of γ. This result has two proofs: one proof-theoretic (using cut elimination and Herbrand-Megill lemma) and one model-theoretic (using Robinson's joint consistency theorem). A conservative extension adds new vocabulary and definitions without adding new truths expressible with the old vocabulary. From the proof-theoretic perspective, new symbols don't give extra power on old sentences; from the mod

First order theories are classified by restrictions on allowed formulas: (1) Geometric theories permit infinite disjunctions and existential quantifiers; (2) Coherent theories restrict to finite disjunctions but allow existential quantifiers; (3) Regular theories only permit finite conjunctions and existential quantifiers, excluding disjunctions entirely. Algebraic theories (groups, modules, vector spaces) are regular because unions of submodules/subspaces don't generally form valid substructures. Contexts provide variable domains for formulas, ensuring proper interpretation with free variables.

Classification theory in model theory classifies mathematical structures based on their logical complexity rather than algorithmic decidability. While earlier classifications focused on whether problems could be solved algorithmically, modern classification uses stability-theoretic principles. A key insight is that adding constants to a structure can change its decidability status, but does not affect its classification in this framework. This provides a more robust classification system that remains stable under various extensions.

This section examines the classification of mathematical theories based on their combinatorial complexity. Stability theory characterizes theories where the number of types over any set is limited, preventing pathological behaviors. Simplicity is a weaker condition than stability but still imposes significant restrictions on structural complexity. Both concepts are characterized by properties of independence relations—stable theories have especially well-behaved independence, while simple theories maintain sufficient regularity for meaningful classification. These classifications help mathematicians understand the logical structure of various mathematical objects and determine applicable analytical tools.

The type of a tuple in a structure is the set of all formulas satisfied by that tuple, representing its complete behavior. Types are ultrafilters in the boolean algebra of definable sets. They determine many properties of theories, including stability. Classification theory studies how many models a theory has in different cardinalities, using types as the main technique. This framework allows mathematicians to classify theories by complexity, with applications across logic, number theory, and geometry.

The Ax-Grothendieck theorem states that an injective regular map between varieties over an algebraically closed field is necessarily surjective. The proof uses a model-theoretic approach: first prove the result in characteristic p > 0 using counting arguments, then extend to characteristic 0 by leveraging the completeness of the first-order theory of algebraically closed fields, which ensures that any first-order statement true for all sufficiently large characteristics is also true in characteristic 0.

This section explains how results proven for finite fields extend to algebraically closed fields using model theory. The key insight is that first-order properties true for the algebraic closure of every finite field are automatically true for all algebraically closed fields. The demonstration uses the irreducible fiber theorem as an example: first prove it for finite fields using point-counting via the bias-variance theorem, then reformulate as a first-order statement and apply the transfer principle. This methodology transforms combinatorial-algebraic arguments into universally valid geometric statements, exemplifying how model theory bridges discrete and continuous mathematics.

Model theory provides elegant frameworks for studying algebraic objects by translating algebraic questions into logical ones, where techniques like elementary equivalence, the Löwenheim-Skolem theorem, and the compactness theorem can prove results such as the Ax-Grothendieck theorem that injective polynomial maps on algebraically closed fields are necessarily surjective.

Algebraically closed valued fields admit quantifier elimination, meaning coordinate projections of semialgebraic sets remain semialgebraic. Semialgebraic sets are defined by polynomial equations and valuative inequalities, closed under finite Boolean combinations. This model-theoretic framework enables systematic analysis of definable structures through quantifier-free formulas, providing powerful tools for studying algebraic geometry over valued fields.

Model-theoretic stability provides a powerful framework for analyzing mathematical structures by examining the behavior of definable sets under quantifier elimination; this machinery, developed primarily for studying categorical theories, has found profound applications in algebraic geometry, including the Ax-Kochen-Ershov theorem on asymptotic properties of finite fields and recent work on torsion points of Drinfeld modules, demonstrating how logical tools can reveal deep structural properties of geometric objects that are difficult to access through purely topological or algebraic methods.