🧠Model Theory Unit 2 – Structures and Signatures

Key Concepts and Definitions

• Structures consist of a set (called the universe or domain) together with a collection of relations, functions, and constants defined on the set
• Signatures (also known as vocabularies) specify the non-logical symbols used to describe a structure including relation symbols, function symbols, and constant symbols
• Models are structures that satisfy a set of sentences or axioms in a given language
• Theories are sets of sentences closed under logical consequence used to describe classes of structures
• Isomorphisms are bijective mappings between structures that preserve the interpretations of all relation, function, and constant symbols
• Homomorphisms are mappings between structures that preserve the interpretations of all relation, function, and constant symbols but may not be bijective
  • Embeddings are injective homomorphisms
  • Surjective homomorphisms are called epimorphisms
• Elementary equivalence occurs when two structures satisfy the same first-order sentences

Language and Syntax

• First-order languages consist of logical symbols (connectives, quantifiers, variables) and non-logical symbols (relation, function, and constant symbols)
• Well-formed formulas (wffs) are constructed recursively from atomic formulas using logical connectives and quantifiers
  • Atomic formulas are formed by applying relation symbols to terms
  • Terms are variables, constants, or function symbols applied to terms
• Sentences are wffs with no free variables
• Theories are sets of sentences closed under logical consequence
• Compactness theorem states that a set of sentences has a model if and only if every finite subset has a model
• Löwenheim-Skolem theorems relate the cardinality of models to the cardinality of the language
  • Downward Löwenheim-Skolem theorem states that if a theory has an infinite model, it has a model of every infinite cardinality greater than or equal to the cardinality of the language
  • Upward Löwenheim-Skolem theorem states that if a theory has an infinite model, it has models of arbitrarily large cardinality

Types of Structures

• Algebraic structures include groups, rings, fields, modules, and vector spaces
  • Groups are sets with a binary operation satisfying associativity, identity, and inverse axioms
  • Rings are groups with an additional binary operation satisfying distributivity and other axioms
• Order structures include posets, lattices, and well-orders
  • Posets (partially ordered sets) are sets with a binary relation that is reflexive, antisymmetric, and transitive
  • Lattices are posets in which every pair of elements has a least upper bound and greatest lower bound
• Topological structures include topological spaces and metric spaces
  • Topological spaces are sets with a collection of open sets satisfying certain axioms
  • Metric spaces are sets with a distance function satisfying non-negativity, symmetry, and triangle inequality
• Combinatorial structures include graphs and hypergraphs
• Measure-theoretic structures include measure spaces and probability spaces

Signatures and Their Role

• Signatures determine the non-logical symbols used to describe structures
• Relation symbols represent relations on the universe of a structure
  • Relation symbols have an arity specifying the number of arguments
  • Example: $\leq$ is a binary relation symbol in the signature of an ordered set
• Function symbols represent functions on the universe of a structure
  • Function symbols have an arity specifying the number of arguments
  • Example: $+$ is a binary function symbol in the signature of a group
• Constant symbols represent distinguished elements of the universe of a structure
  • Example: $0$ is a constant symbol in the signature of a ring
• Signatures are used to define the language in which structures can be described and theories can be formulated
• Changing the signature can drastically alter the expressiveness of the language and the properties of the structures that can be described

Isomorphisms and Homomorphisms

• Isomorphisms are structure-preserving bijections between structures
  • If there exists an isomorphism between two structures, they are said to be isomorphic
  • Isomorphic structures are essentially the same, differing only in the names of their elements
• Homomorphisms are structure-preserving mappings between structures that may not be bijective
  • Homomorphisms preserve the interpretations of relation, function, and constant symbols
  • Injective homomorphisms (embeddings) preserve the truth of all formulas
  • Surjective homomorphisms (epimorphisms) preserve the truth of all universal formulas
• Isomorphism theorems relate the structure of homomorphic images, kernels, and quotients
  • First isomorphism theorem states that the image of a homomorphism is isomorphic to the quotient of the domain by the kernel
  • Second isomorphism theorem relates the quotients of a structure by two substructures
  • Third isomorphism theorem relates the quotients of a quotient structure
• Categoricity is the property of a theory having all models isomorphic to each other
  • Example: the theory of dense linear orders without endpoints is $\aleph_0$-categorical (all countable models are isomorphic)

Model-Theoretic Operations

• Substructures are structures whose universe is a subset of the universe of a larger structure, with the relations, functions, and constants restricted to the subset
  • Example: subgroups are substructures of groups
• Elementary substructures are substructures that satisfy the same first-order sentences as the larger structure
  • Tarski-Vaught test is a criterion for determining if a substructure is elementary
• Unions of chains of structures are structures whose universe is the union of the universes of the structures in the chain, with the relations, functions, and constants extended naturally
  • Elementary chains are chains of elementary substructures
  • Tarski's union theorem states that the union of an elementary chain is an elementary extension of each structure in the chain
• Products of structures are structures whose universe is the Cartesian product of the universes of the component structures, with the relations, functions, and constants defined componentwise
• Ultraproducts are quotients of products of structures by ultrafilters
  • Łoś's theorem states that an ultraproduct satisfies a first-order sentence if and only if the set of components satisfying the sentence is in the ultrafilter
  • Ultraproducts can be used to prove the compactness theorem and construct non-standard models of arithmetic

Applications in Mathematics

• Model theory provides a framework for studying the semantics of mathematical theories
• Algebraic geometry uses model theory to study the connections between geometric objects and their algebraic representations
  • Zariski geometries are structures that behave like algebraic varieties
  • Model-theoretic methods have been used to prove deep results in diophantine geometry
• Number theory uses model theory to study the logical properties of arithmetic and other number systems
  • Non-standard models of arithmetic have been used to prove results about prime numbers and diophantine equations
  • Ax-Kochen theorem uses model theory to relate the solvability of diophantine equations over $p$-adic fields to their solvability over the rationals
• Set theory uses model theory to study the logical properties of the universe of sets
  • Gödel's constructible universe $L$ is a model of ZFC that satisfies the generalized continuum hypothesis
  • Forcing is a technique for constructing models of set theory with specific properties
• Theoretical computer science uses model theory to study the logical properties of computation
  • Finite model theory studies the expressive power of logics on finite structures
  • Descriptive complexity theory relates the complexity of computational problems to the logical complexity of their definitions

Common Challenges and Solutions

• Quantifier elimination is the process of finding an equivalent quantifier-free formula for a given formula
  • Tarski's quantifier elimination procedure for real-closed fields has important applications in algebraic geometry and robotics
  • Presburger arithmetic (the theory of the natural numbers with addition) admits quantifier elimination, while Peano arithmetic (with multiplication) does not
• Decidability is the property of a theory having an effective procedure for determining whether a given sentence is provable from the theory
  • Decidable theories include the theory of algebraically closed fields, the theory of real-closed fields, and Presburger arithmetic
  • Undecidable theories include Peano arithmetic and the theory of groups
• Stability theory studies the classification of theories based on the structure of their models
  • Stable theories have a well-behaved notion of independence and admit a dimension theory
  • Unstable theories exhibit more complex behavior and may not have a well-defined notion of dimension
• O-minimality is a property of ordered structures that generalizes many of the desirable properties of real-closed fields
  • O-minimal structures have a tame topology and admit a form of cell decomposition
  • Many important structures in real algebraic geometry and real analytic geometry are o-minimal
• NIP (not the independence property) is a generalization of stability that includes many important unstable theories
  • Theories with NIP have a well-behaved notion of invariant types and admit a Vapnik-Chervonenkis dimension
  • Examples of NIP theories include the theory of algebraically closed fields, the theory of real-closed fields, and the theory of the p-adic numbers