Semantics and Model Theory

Semantics and Model Theory (The Meaning)

Scope: This section synthesizes the rigorous mathematical framework for determining the “meaning” of formal languages, known as Model Theory or Semantics. Following the structure of metalogic defined in Theodore Sider’s Logic for Philosophy and P.D. Magnus’s forall x: Calgary, we articulate the definitions of interpretations, valuations, and the precise conditions required to establish logical truth and validity within Propositional (PL) and First-Order Logic (FOL).

  • Reading: [forallx] 30–33, 41; [Sider] 4.2, 4.3, 4.5
  • Primary Focus: [Sider] Chapter 4. This is the heart of the “Meta” turn. Move from truth tables to understanding Models as set-theoretic structures.
  • Supplement: Use [forallx] Chapters 30–33 as a “safety net” for a gentler introduction to models before returning to Sider.

4.1. The Semantic Conception of Logic

While proof theory concerns symbol manipulation according to syntactic rules, semantics concerns the relationship between those symbols and the “world” they represent. This approach models logical consequence as truth-preservation across all possible interpretations.

4.1.1. Models and Interpretations
  • Sider, pp. 34-35, 38

To evaluate formal sentence truth, we construct Models—abstract mathematical representations of possible states of affairs.

A model functions as a semantic bridge, connecting the formal language to the world. It assigns “semantic values” to the non-logical expressions (sentence letters, names, predicates), allowing us to hold the logical constants fixed while varying the “universe” and the meanings of content words.

From this, we define Semantic Consequence: a sentence \(\phi\) is a consequence of a set of sentences \(\Gamma\) (written \(\Gamma \vDash \phi\)) if and only if there is no interpretation in which all members of \(\Gamma\) are true and \(\phi\) is false. Equivalently, \(\phi\) is true in every model in which all members of \(\Gamma\) are true (Sider, p. 10; Magnus et al., pp. 9–10). A sentence is valid (or a logical truth) if it is true in every possible interpretation.

The Classical Choice: By modeling validity as a function returning a Boolean (True/False), we enforce the Law of Excluded Middle. We assume the universe is “complete”—that every question has an answer waiting for us. Constructive systems would return a program or evidence instead of a simple bit.

4.2. Propositional Semantics (PL)

In Propositional Logic, the “world” is simple, consisting entirely of the truth or falsity of atomic facts. Thus, a PL interpretation requires no domains or objects—merely an assignment of truth values.

4.2.1. Interpretations and Valuations
  • Sider, pp. 36-37
  • Magnus et al., p. 81
  • PL-Interpretation: A PL-interpretation is strictly defined as a function \(I\) that assigns a truth value (represented as 1 or 0, or T or F) to every sentence letter (\(P, Q, R...\)) in the language.
  • The Valuation Function: Once an interpretation \(I\) fixes atomic truth values, a valuation function (\(V_I\)) determines the truth value of every complex formula based on the fixed meanings of the logical connectives.
  • Completeness of Truth Tables: A complete truth table represents every possible valuation for a given set of sentence letters. If a sentence contains \(n\) distinct letters, there are \(2^n\) possible valuations (rows) required to determine its semantic status.
4.2.2. Truth Conditions for Connectives
  • Sider, pp. 37, 39

We define the valuation function VI​ recursively. For any PL-interpretation I and sentences ϕ,ψ, we can model the truth conditions as a functional process valuation that reduces complex sentences to atomic truth values.

-- Truth Conditions for PL Connectives
-- We model the valuation function as a recursive process
(define (valuation formula interpretation)
  (match formula
    ;; Base Case: Atomic Sentence
    ((Atomic p) (get-value p interpretation))

    ;; Recursive Steps: Connectives
    ((Not p)    (not (valuation p interpretation)))
    ((And p q)  (and (valuation p interpretation) (valuation q interpretation)))
    ((Or p q)   (or  (valuation p interpretation) (valuation q interpretation)))
    ((Implies p q) (or (not (valuation p interpretation)) (valuation q interpretation)))
    ((Iff p q)     (= (valuation p interpretation) (valuation q interpretation)))
  )
)

Notation: This is a recursive evaluation function. It matches the structure of the formula and recursively calls itself (valuation) on the sub-components.

  • Negation (¬): As defined in the (Not p) case, \(V_I(\neg \phi) = 1\) iff \(V_I(\phi) = 0\). A negation is true if and only if the sentence being negated is false.
  • Conjunction (\(\land\)): The (And p q) case requires both recursive calls to return true. \(V_I(\phi \land \psi) = 1\) iff \(V_I(\phi) = 1\) and \(V_I(\psi) = 1\). A conjunction is true if and only if both conjuncts are true.
  • Disjunction (\(\lor\)): The (Or p q) case returns true if either recursive call returns true. \(V_I(\phi \lor \psi) = 1\) iff \(V_I(\phi) = 1\) or \(V_I(\psi) = 1\). This represents inclusive “or”; it is true if at least one disjunct is true.
  • Conditional (\(\to\)): The (Implies p q) case is equivalent to (not p) or q. \(V_I(\phi \to \psi) = 1\) iff it is not the case that \(V_I(\phi) = 1\) and \(V_I(\psi) = 0\). The material conditional is false only when the antecedent is true and the consequent is false.
  • Biconditional (\(\leftrightarrow\)): The (Iff p q) case checks for equality of truth values. \(V_I(\phi \leftrightarrow \psi) = 1\) iff \(V_I(\phi) = V_I(\psi)\). It is true when both sides have the same truth value.

Example: If \(P\) is true (1) and \(Q\) is false (0), then: * \(P \land Q\) is 0. * \(P \lor Q\) is 1. * \(P \to Q\) is 0.

4.3. First-Order Semantics (FOL)

First-Order Logic semantics requires a richer ontology than Propositional Logic. We cannot simply assign truth values to atomic sentences; we must derive them from the relationships between objects in a Domain of Discourse.

A Warning from the Constructivists: Notice that our code for valuation works perfectly for Propositional Logic (finite truth tables) but hits a wall in First-Order Logic (infinite domains).

L.E.J. Brouwer would point out that this is not a bug in the code; it is a “bug” in Classical Logic. Classical Logic claims that statements about infinite sets are strictly True or False, even though no algorithm can ever verify them.

In this guide, our code represents the Finite Projection of logic. When the logic goes beyond what the code can execute (like checking an infinite domain), we are crossing the boundary from Computation (Bishop) to Metaphysics (Hilbert).

-- A Classical Semantics Function
-- Brouwer would warn: This function is not computable for infinite domains!
isValid :: Model -> Formula -> Boolean
isValid model phi =
  case domain model of
    Finite   -> bruteForceCheck model phi  -- Constructively valid
    Infinite -> undefined                  -- The Classical "Leap of Faith"
4.3.1. Structures and Models
  • Sider, p. 118

A PC-Model (Predicate Calculus Model) is an ordered pair \(\langle D, I \rangle\) consisting of a Domain and an Interpretation Function.

-- Definition of a Model
Domain :: Set Object
Interpretation :: Symbol -> Extension
Model :: {Domain, Interpretation}

Notation: Model is defined as a tuple (pair) containing a Domain and an Interpretation function.

  • The Domain (\(D\)): As modeled by Set Object, this is a non-empty set of objects (e.g., numbers, people) that constitutes the “universe” of the model. The quantifiers \(\forall\) and \(\exists\) range over this set (Sider, p. 118; Magnus et al., p. 264).
  • The Interpretation Function (\(I\)): This function maps non-logical symbols to semantic values:
    • Names: For every constant symbol \(\alpha\), Interpretation(\(\alpha\)) is an object in \(D\).
    • Predicates: For every \(n\)-place predicate \(\Pi\), Interpretation(\(\Pi\)) is a set of \(n\)-tuples drawn from \(D\) (the extension). For example, Interpretation(\(F\)) is a subset of \(D\); \(F\) is true of an object if the object is in that subset.

Example: Consider a model \(M = \langle D, I \rangle\) where \(D = \{1, 2\}\) and \(I(F) = \{1\}\). Here, \(F(a)\) is true if \(I(a) = 1\), but \(\forall x F(x)\) is false because \(2 \in D\) but \(2 \notin I(F)\).

4.3.2. Variable Assignments and Satisfaction
  • Sider, p. 120
  • Magnus et al., p. 273

Because FOL contains variables (\(x, y, z\)) functioning as placeholders, we cannot define truth directly for open formulas like \(Fx\). We require a variable assignment.

  • Definition: A variable assignment \(g\) is a function that assigns a specific object from the domain \(D\) to every variable in the language.
  • Variant Assignment (\(g_{\alpha}^{u}\)): To evaluate quantifiers, we must test whether a formula holds when a variable stands for different objects. \(g_{\alpha}^{u}\) is an assignment identical to \(g\) except that it assigns object \(u\) to variable \(\alpha\).
  • Satisfaction: An object \(u\) satisfies a formula \(A(x)\) if the formula is true when \(x\) refers to \(u\).
4.3.3. Truth for Quantifiers
  • Sider, pp. 121-122

We define truth in FOL relative to a model M and a variable assignment g. We can model this using a satisfies? function that handles the variable assignment updates.

(define (satisfies? model assignment formula)
  (match formula
    ((ForAll x phi)
     ;; True if phi is satisfied for EVERY object 'u' in the domain
     (every? (lambda (u)
               (satisfies? model (update assignment x u) phi))
             (model.domain)))

    ((Exists x phi)
     ;; True if phi is satisfied for AT LEAST ONE object 'u'
     (some? (lambda (u)
              (satisfies? model (update assignment x u) phi))
            (model.domain)))))

Notation: (lambda (u)...) creates an anonymous function. every? and some? are higher-order functions that check if a predicate holds for all or some elements of a collection (the domain).

  • Atomic Sentences: \(V_{M,g}(\Pi \alpha_1... \alpha_n)=1\) iff the tuple of objects denoted by \(\alpha_1... \alpha_n\) is in the extension \(I(\Pi)\).
  • Universal Quantifier (\(\forall\)): As shown in the ForAll case, the formula is true iff for every object u in the domain \(D\) (checking satisfies? for all assignments). Formally, \(V_{M,g}(\forall \alpha \phi)=1\) iff for every object \(u\) in the domain \(D\), \(V_{M,g_{\alpha}^{u}}(\phi)=1\). The formula must hold for every possible assignment of the variable \(\alpha\).
  • Existential Quantifier (\(\exists\)): As shown in the Exists case, the formula is true iff there is at least one object u in the domain \(D\) such that the recursive call holds. Formally, \(V_{M,g}(\exists \alpha \phi)=1\) iff there is at least one object \(u\) in the domain \(D\) such that \(V_{M,g_{\alpha}^{u}}(\phi)=1\).

Guided Example: Evaluating Truth

Consider a tiny Model \(\mathfrak{M}\): - Domain (D): \(\{1, 2\}\) - Interpretation (I): - \(I(Even) = \{2\}\)

Is the sentence \(\exists x Even(x)\) True or False in \(\mathfrak{M}\)?

(Hint: To evaluate an existential quantifier, you must check if there is at least one object in the Domain that the Interpretation function assigns to the predicate.)

4.4. Soundness and Completeness

Metalogic investigates the relationship between the semantic notion of validity (⊨) and the proof-theoretic notion of derivability (⊢).

4.4.1. Soundness

Soundness is the property that a proof system never proves a false conclusion from true premises.

  • Theorem: If \(\Gamma \vdash \phi\), then \(\Gamma \vDash \phi\).
  • Significance: If a sentence is provable in the system, it is guaranteed to be a semantic consequence. There are no “false positives” in the proof system (Sider, p. 134; Magnus et al., p. 390).
4.4.2. Completeness

Completeness is the property that a proof system is capable of proving all valid consequences.

  • Theorem: If \(\Gamma \vDash \phi\), then \(\Gamma \vdash \phi\).
  • Significance: If a sentence is a semantic consequence (true in all models), there exists a derivation for it in the system. There are no “missing truths” that the system cannot reach (Sider, p. 134; Magnus et al., p. 360).

Having established the core definitions of truth and provability, we now turn to the language’s expressive capacity. Before we prove the system’s limits (Metalogic), we must master its full descriptive power (Translation).

Problem Sets

Continue to Part 5: Translation →