🧠Model Theory Unit 6 – Compactness and Löwenheim–Skolem Theorems

Key Concepts and Definitions

• Model theory studies mathematical structures and their properties using formal languages and logical tools
• A model is a set with relations, functions, and constants that satisfy a set of sentences in a formal language
• A theory is a set of sentences closed under logical consequence
• A theory is consistent if it has a model
• A theory is complete if for every sentence, either the sentence or its negation is in the theory
• A theory is categorical if all its models are isomorphic
• Elementary equivalence means two structures satisfy the same first-order sentences

Compactness Theorem: Statement and Intuition

• The Compactness Theorem states that a set of first-order sentences has a model if and only if every finite subset has a model
• Intuitively, if every finite piece of a theory is consistent, then the whole theory is consistent
• The Compactness Theorem allows constructing models by building them up from finite pieces
• The theorem is a powerful tool for proving the existence of models with specific properties
• The Compactness Theorem is analogous to the finite intersection property in topology
  • A collection of closed sets in a compact space has a non-empty intersection if every finite subcollection has a non-empty intersection
• The Compactness Theorem can be used to prove the existence of non-standard models of arithmetic

Proof Techniques for Compactness

• One common proof technique is the ultraproduct construction
  • An ultraproduct is a quotient of a direct product of structures by an ultrafilter
  • If each structure in the product satisfies a first-order sentence, then the ultraproduct satisfies the sentence
• Another proof technique is the finitary nature of first-order proofs
  • If a set of sentences is inconsistent, then a finite subset is inconsistent
  • This is because proofs are finite and can only use a finite number of assumptions
• Gödel's Completeness Theorem can be used to prove the Compactness Theorem
  • If every finite subset of a set of sentences is consistent, then the whole set is consistent
• The Compactness Theorem can be proved using the topology of Stone spaces
  • The Stone space of a theory is compact, and models correspond to points in the Stone space

Applications of Compactness

• The Compactness Theorem can be used to prove the existence of non-standard models of arithmetic
  • These models contain infinite numbers larger than any standard natural number
• The theorem can be used to prove the existence of saturated models
  • A saturated model realizes all types over small subsets
• Compactness can be used to prove the Ax-Kochen-Ershov Principle in valued fields
  • This principle relates the theory of a valued field to the theories of the residue field and value group
• The Compactness Theorem is used in the proof of the Keisler-Shelah Theorem
  • Two structures are elementarily equivalent if and only if they have isomorphic ultrapowers
• Compactness is used in the study of pseudofinite structures
  • A structure is pseudofinite if it satisfies every first-order sentence true in all finite structures

Löwenheim–Skolem Theorems: Upward and Downward

• The Upward Löwenheim–Skolem Theorem states that if a theory has an infinite model, then it has models of all larger cardinalities
• The Downward Löwenheim–Skolem Theorem states that if a theory has an infinite model, then it has a model of cardinality at most the size of the language
• The Löwenheim–Skolem Theorems show that first-order logic cannot characterize infinite structures up to isomorphism
• The theorems imply the existence of non-standard models of arithmetic and set theory
• The Downward Löwenheim–Skolem Theorem is used to construct countable elementary substructures

Proof Strategies for Löwenheim–Skolem

• The Upward Löwenheim–Skolem Theorem can be proved using the Compactness Theorem
  • Add new constant symbols to the language for each element of a larger set
  • Use Compactness to show that the expanded theory has a model
• The Downward Löwenheim–Skolem Theorem can be proved using a chain construction
  • Build an elementary chain of substructures of size at most the language
  • The union of the chain is the desired model
• The Downward Löwenheim–Skolem Theorem can also be proved using the Tarski-Vaught Test
  • A substructure is elementary if it satisfies the Tarski-Vaught criterion
• The Löwenheim–Skolem Theorems can be proved using the Reflection Principle in set theory
  • Every finite set of formulas is reflected in a countable transitive model

Connections Between Compactness and Löwenheim–Skolem

• The Compactness Theorem and the Upward Löwenheim–Skolem Theorem are equivalent
  • Each can be proved using the other
• The Compactness Theorem and the Downward Löwenheim–Skolem Theorem together imply the existence of countable non-standard models of arithmetic and set theory
• The Löwenheim–Skolem Theorems can be viewed as a strengthening of the Compactness Theorem
  • They provide more control over the cardinality of models
• The Compactness Theorem and the Löwenheim–Skolem Theorems are fundamental tools in model theory
  • They are used in many proofs and constructions

Implications and Limitations in Model Theory

• The Compactness Theorem and Löwenheim–Skolem Theorems show the limitations of first-order logic in characterizing infinite structures
  • They imply the existence of non-standard models (non-standard analysis, non-standard set theory)
• The theorems show that first-order theories cannot specify the cardinality of their infinite models
  • Infinite structures cannot be characterized up to isomorphism
• The Löwenheim–Skolem Theorems have implications for the foundations of mathematics
  • They are related to the incompleteness phenomena in arithmetic and set theory
• The theorems highlight the expressive power and limitations of first-order logic
  • Many mathematical concepts (finiteness, uncountability) are not first-order definable
• The Compactness Theorem and Löwenheim–Skolem Theorems are key tools in model-theoretic constructions and proofs
  • They are used in the study of saturated models, stability theory, and classification theory