🧠Model Theory Unit 3 – Terms, Formulas, and Satisfaction

Key Concepts and Definitions

• Terms represent objects, functions, or relations within a mathematical structure and are constructed using variables, constants, and function symbols
• Formulas express properties or relationships between terms using logical connectives (conjunction, disjunction, implication) and quantifiers (universal, existential)
• Atomic formulas consist of a relation symbol applied to terms and serve as the building blocks for more complex formulas
• Free variables are not bound by quantifiers and can be assigned values from the universe of a structure
• Bound variables are quantified and range over the entire universe of a structure
• Sentences are formulas with no free variables and are either true or false in a given structure
• Theories are sets of sentences closed under logical consequence and describe classes of structures that satisfy them

Fundamental Formulas and Notation

• Terms are denoted by lowercase letters (x, y, z) and are constructed recursively using function symbols and constants
• Function symbols are represented by lowercase letters (f, g, h) with an associated arity indicating the number of arguments they take
• Constants are treated as 0-ary function symbols and are denoted by lowercase letters (a, b, c)
• Relation symbols are denoted by uppercase letters (P, Q, R) with an associated arity indicating the number of arguments they take
• Logical connectives include conjunction ($\land$), disjunction ($\lor$), implication ($\rightarrow$), and negation ($\neg$)
• Quantifiers include the universal quantifier ($\forall$) and the existential quantifier ($\exists$)
• Formulas are constructed using atomic formulas, logical connectives, and quantifiers, with parentheses used to specify the order of operations
• The equality symbol ($=$) is a special binary relation symbol used to express equality between terms

Structures and Models

• A structure (or model) $\mathcal{M}$ consists of a non-empty universe (or domain) $M$ and interpretations for the language's constants, function symbols, and relation symbols
• The universe $M$ is a set of elements over which the variables in formulas range
• Constants are interpreted as specific elements of the universe
• Function symbols are interpreted as functions mapping tuples of elements from the universe to elements of the universe
• Relation symbols are interpreted as relations (subsets) on the universe, with the arity of the relation matching the arity of the symbol
• Isomorphic structures have the same universe size and satisfy the same sentences, differing only in the labeling of their elements

Satisfaction and Truth

• Satisfaction is the key notion connecting structures and formulas, determining when a formula is true in a given structure under a specific variable assignment
• A variable assignment $s$ is a function mapping variables to elements of the universe $M$
• The satisfaction relation $\mathcal{M} \vDash \varphi[s]$ denotes that the formula $\varphi$ is true in the structure $\mathcal{M}$ under the variable assignment $s$
• Satisfaction is defined recursively on the structure of formulas, with atomic formulas, logical connectives, and quantifiers each having their own satisfaction conditions
• A sentence $\varphi$ is true in a structure $\mathcal{M}$ (denoted $\mathcal{M} \vDash \varphi$) if it is satisfied by all variable assignments, as it has no free variables
• Logical consequence ($\Gamma \vDash \varphi$) holds when every model of the theory $\Gamma$ is also a model of the sentence $\varphi$

Model Construction Techniques

• Model construction techniques are used to build structures that satisfy specific properties or theories
• Diagramming involves representing the elements and relations of a structure graphically, helping to visualize and reason about the model
• Chasing arrows in diagrams allows for the derivation of new facts about the structure by following the implications of its relations
• Compactness ensures that if every finite subset of a theory has a model, then the entire theory has a model
• Löwenheim-Skolem theorems state that if a theory has an infinite model, then it has models of all infinite cardinalities (downward) and models of arbitrarily large cardinalities (upward)
• Ultraproducts combine a family of structures using an ultrafilter, preserving certain properties and allowing for the construction of new models

Theories and Their Properties

• Theories are sets of sentences closed under logical consequence, describing classes of structures that satisfy them
• Complete theories have the property that for every sentence $\varphi$, either $\varphi$ or its negation $\neg \varphi$ is a logical consequence of the theory
• Consistent theories have at least one model, while inconsistent theories have no models and entail every sentence
• Decidable theories have an effective procedure for determining whether a given sentence is a logical consequence of the theory
• Axiomatizable theories can be characterized by a recursively enumerable set of axioms
• Theories are categorical in a cardinal $\kappa$ if all models of the theory of cardinality $\kappa$ are isomorphic

Applications and Examples

• Peano arithmetic (PA) is a first-order theory of the natural numbers with addition, multiplication, and a successor function, serving as a foundation for number theory
• Group theory studies algebraic structures with a binary operation satisfying associativity, identity, and inverse properties, with examples including symmetry groups and matrix groups
• Linear orders are structures with a binary relation that is transitive, antisymmetric, and total, such as the natural numbers with the less than or equal to relation ($\leq$)
• Graphs are structures consisting of a set of vertices and a binary edge relation, with applications in network analysis and optimization problems
• Database theory uses model theory to study the properties of relational databases, with tables as structures and queries as formulas
• Model-theoretic semantics provides a formal framework for the interpretation of natural language sentences using structures and satisfaction

Common Pitfalls and Tips

• Carefully track variable scope and binding when constructing and evaluating formulas to avoid confusion between free and bound variables
• Pay attention to the arity of function and relation symbols when building terms and atomic formulas
• Use parentheses judiciously to clearly specify the intended order of operations in complex formulas
• Be mindful of the distinction between satisfaction under a variable assignment and truth in a structure, especially when dealing with sentences
• Exploit the recursive nature of term and formula construction when proving properties or defining satisfaction conditions
• Utilize model construction techniques strategically to build counterexamples or demonstrate the consistency of theories
• Familiarize yourself with common axiom schemas (e.g., group axioms, order axioms) and their corresponding classes of structures
• Practice translating between formal statements and their natural language counterparts to build intuition and understanding