A Computational Approach to Philosophical Metalogic Pt. 3

Table of Contents

You are reading the third part of the Computational Metalogic guide. This section focuses on Semantics and Translation, bridging the gap between the formal system defined in the previous section and the interpretation of truth.

4. 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

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 (Sider, pp. 34–35).

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 (Sider, p. 38).

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
  • 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 (Sider, p. 36).
  • 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 (Sider, p. 37).
  • 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 (Magnus et al., p. 81).
4.2.2. Truth Conditions for Connectives

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 (Sider, p. 37).
  • 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 (Sider, p. 39).
  • 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 (Sider, p. 39).
  • 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 (Sider, p. 37).
  • 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 (Sider, p. 39).

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

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 (Sider, p. 118).

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

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 (Sider, p. 120).
  • 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$ (Sider, p. 120).
  • Satisfaction: An object $u$ satisfies a formula $A(x)$ if the formula is true when $x$ refers to $u$ (Magnus et al., p. 273).
4.3.3. Truth for Quantifiers

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)$ (Sider, p. 121).
  • 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$ (Sider, p. 121).
  • 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$ (Sider, p. 122).

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).

5. Translation and Expressive Power

Scope: This section synthesizes the rigorous frameworks for translating complex natural language concepts into First-Order Logic (FOL), enabling the formalization of nuanced claims beyond simple predication. We articulate the mechanical rules for quantifier transformation, the semantic implications of multiple quantifiers, and the specific logical structures required to express identity, numerical quantities, and definite descriptions.

  • Reading: [LPL] 11, 14; [TLB] 7.3–7.5; [forallx] 25, 26, 28, 38; [Sider] pp. 137–156 (Selections)
  • Primary Focus: [LPL] Chapters 11 & 14 and [TLB] 7.3–7.5. Before proving theorems about the system, master the expressive power of the system. Use LPL to understand how identity and definite descriptions formalize complex claims.

5.1. Equivalence and Transformation

Efficient proofs and translations often require the mechanical manipulation of logical forms. Derived rules allow for the transformation of formulas into logically equivalent strings without altering their truth conditions, serving as the "algebra" of the logical system.

5.1.1. Conversion of Quantifiers (CQ)

The Conversion of Quantifiers (CQ) rules function as De Morgan's Laws for predicate logic, permitting the movement of negation across quantifiers. We can model this as a syntactic transformation function convert:

(define (convert formula)
  (match formula
    ((Not (ForAll x phi)) (Exists x (Not phi))) ;; Push Negation In
    ((Not (Exists x phi)) (ForAll x (Not phi))) ;; Push Negation In
    ((ForAll x phi)       (Not (Exists x (Not phi))))
    ((Exists x phi)       (Not (ForAll x (Not phi))))))

Notation: This function demonstrates syntactic transformation. It takes a formula structure and returns a different but logically equivalent structure.

Mechanically, this means that negating a universal claim ("Not everything is F") is logically equivalent to asserting an existential negation ("Something is not F"). Conversely, negating an existential claim ("Nothing is F") is equivalent to a universal negation ("Everything is non-F").

Formal Equivalence:

  • $\neg \forall x \phi \iff \exists x \neg \phi$
  • $\neg \exists x \phi \iff \forall x \neg \phi$
  • $\forall x \phi \iff \neg \exists x \neg \phi$
  • $\exists x \phi \iff \neg \forall x \neg \phi$

These rules allow the "pushing in" or "pulling out" of negation signs to normalize formulas for proof strategies (Zach et al., pp. 317–319).

5.2. Multiple Quantifiers and Scope

FOL's expressive power increases significantly with the use of multiple quantifiers. The semantic meaning of such sentences is determined strictly by the ordering and scope of the quantifiers involved.

5.2.1. Nested Quantifiers and Order

When a formula contains multiple quantifiers, their order dictates the logical relationship between the variables.

  • $\forall x \exists y$ (Universal-Existential): This order expresses dependence. In $\forall x \exists y R(x,y)$, the choice of $y$ depends on the choice of $x$. For example, "Everyone has a mother" allows a different mother for each person.
  • $\exists y \forall x$ (Existential-Universal): This order expresses independence. In $\exists y \forall x R(x,y)$, the object $y$ is fixed and relates to every $x$. For example, "There is someone who is everyone's mother" implies a single individual serves as the mother for all (Barker-Plummer et al., pp. 298–300; Zach et al., pp. 213–217).

Example:

  • $\forall x \exists y Loves(x, y)$: "Everyone loves someone" (Dependence: the loved one depends on the lover).
  • $\exists y \forall x Loves(x, y)$: "There is someone whom everyone loves" (Independence: one specific person is loved by all).
5.2.2. The Quantifier Shift Fallacy

A common logical error involves illicitly swapping the order of quantifiers. Reversing the order from ∀x∃y to ∃y∀x changes the meaning from a "many-many" relationship to a "one-many" relationship. Metalogic requires precise scope analysis to prevent these fallacious inferences (Zach et al., pp. 213–217).

5.3. Identity and Numerical Quantification

Standard FOL is often augmented with the identity predicate (=) to form Predicate Logic Extended (PLE). This addition allows the language to express numerical distinctions—counting objects solely through logical structure.

5.3.1. The Identity Predicate

Identity is treated as a binary predicate with fixed semantic properties. (Recall the deduction rules for identity from Section 3.6).

  • Logical Truth: The statement $\forall x (x=x)$ is a logical truth; everything is self-identical (Bergmann et al., p. 381).
  • Semantics: The sentence $a=b$ is true if and only if the terms $a$ and $b$ refer to the exact same object in the domain (Sider, pp. 137–140).

Example: "Mark Twain is Samuel Clemens" translates to $m = s$. "Mark Twain is the author of Huck Finn" translates to $Author(m, h)$.

5.3.2. Expressing Numerical Quantities

By combining quantifiers, negation, and identity, we can define precise numerical quantities without using numbers as primitive objects.

  • "At Least n": To say "There are at least two Fs," one asserts the existence of two objects that are both F and are distinct from each other.
-- Expressing "At Least Two" (Existence of Distinct Objects)
AtLeastTwo :: Predicate -> Formula
(AtLeastTwo F) = (Exists x (Exists y
                   (And (F x)
                        (And (F y)
                             (Not (= x y))))))

Notation: This defines a complex formula structure (macro) in terms of simpler primitives (Exists, And, =).

  • Formalization: As modeled above, AtLeastTwo requires finding two distinct witnesses x and y in the domain such that they are both F and not identical to each other. Formally: $\exists x \exists y (F(x) \land F(y) \land \neg (x=y))$ (Barker-Plummer et al., pp. 375–377; Bergmann et al., pp. 312–313).

  • "At Most n": To say "There is at most one F," one asserts that if any two objects are F, they must be identical.

  • Formalization: $\forall x \forall y ((F(x) \land F(y)) \to x=y)$ (Barker-Plummer et al., pp. 375–377).

  • "Exactly n": This is the conjunction of "at least n" and "at most n." To say "There is exactly one F," one asserts existence and uniqueness.

  • Formalization: $\exists x (F(x) \land \forall y (F(y) \to x=y))$ (Zach et al., pp. 413).

5.4. Definite Descriptions

Definite descriptions are phrases of the form "The F" (e.g., "The King of France"). Formalizing these phrases requires addressing the implication of uniqueness and existence hidden within the article "the."

5.4.1. Russell's Theory of Descriptions

Bertrand Russell analyzed definite descriptions as complex existentially quantified conjunctions rather than singular names.

-- Russell's Analysis of "The F is G"
The :: Predicate -> Predicate -> Formula
(The F G) = (Exists x
              (And (F x)
                   (And (ForAll y (Implies (F y) (= y x)))
                        (G x))))

Notation: This captures Russell's Theory of Descriptions as a structural template. It translates "The F is G" into an existence claim, a uniqueness claim, and a predication.

  • Mechanism: Bertrand Russell analyzed definite descriptions not as singular names, but as complex existentially quantified conjunctions. The sentence "The F is G" is analyzed into three logical components (Zach et al. 2025, p. 243):

    1. Existence: (Exists x (F x)) - There is at least one thing that is F.
    2. Uniqueness: (ForAll y (Implies (F y) (= y x))) - There is at most one thing that is F (everything that is F is identical to x).
    3. Predication: (G x) - That specific thing is G.

  • Formalization: The sentence "The King of France is bald" is translated as:

$\exists x (K(x) \land \forall y (K(y) \to y=x) \land B(x))$

This structure avoids the paradox of referring to non-existent objects by rendering the entire statement false if no such $x$ exists (Barker-Plummer et al., pp. 388–390; Bergmann et al., pp. 315–316; Sider, pp. 146–147).

5.4.2. Function Symbols and the Iota Operator

Advanced formalizations may use function symbols or the iota operator (ι) to represent descriptions.

  • Function Symbols: A function symbol maps $n$ terms to a unique term. Complex noun phrases can be formalized using function terms (e.g., $f(a)$ for "the father of $a$") (Bergmann et al., pp. 319–322).
  • The Iota Operator: Some systems introduce a variable-binding operator $\iota x \phi$ (read "the $x$ such that $\phi$"). While this simplifies notation, its semantics must still resolve the issue of "empty descriptions" (descriptions that fail to refer), typically by reverting to Russell's quantificational analysis (Sider, pp. 146–147).

This completes our survey of the expressive power of First-Order Logic. By mastering these translation schemas—from basic quantifiers to complex definite descriptions—we see that FOL transcends the status of a dry calculus; it is a flexible instrument capable of modeling nuanced philosophical claims. However, the true power of logic lies beyond translation; it is found in understanding the mathematical properties of the system itself.

Continue to Part 4: Metalogic and Conclusion →