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.

Guided Example: The Main Connective

Translate the English sentence: “All cats are mammals.”

\(\forall x (Cat(x) \text{ \_\_\_\_ } Mammal(x))\)

Which connective belongs in the blank?

(Hint: If you use ∧, you are saying “Everything in the universe is both a cat and a mammal,” which is false. What connective accurately represents “IF it is a cat, THEN it is a mammal”?)

5.1. Translation as Parsing

From a computational perspective, “translating” English into First-Order Logic is functionally identical to writing a Parser. You are taking an unstructured string of natural language and converting it into a rigorously structured Abstract Syntax Tree (the WFF data type defined in Chapter 2).

;; Translation is Compilation
;; We define a function that maps natural language strings to ASTs
(define (parse english-string)
  (match (lex english-string)
    (("All" noun verb) 
     (ForAll x (Implies ((to-predicate noun) x) 
                        ((to-predicate verb) x))))
    (("Some" noun verb)
     (Exists x (And ((to-predicate noun) x) 
                    ((to-predicate verb) x))))))

;; (parse "All cats are mammals") 
;; -> (ForAll x (Implies (Cat x) (Mammal x)))

Notation: lex tokenizes the English string into words, and match maps those word patterns to their corresponding logical structures. Understanding translation as compiling into an AST prevents errors like using And instead of Implies for universal claims.

5.2. 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.2.1. Conversion of Quantifiers (CQ)

Zach et al., pp. 317-319

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.

5.3. 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.3.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.3.2. The Quantifier Shift Fallacy

Zach et al., pp. 213-217

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.

5.4. 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.4.1. The Identity Predicate

Bergmann et al., p. 381
Sider, pp. 137-140

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

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

5.4.2. Expressing Numerical Quantities

Barker-Plummer et al., pp. 375-377
Zach et al., p. 413

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

5.5. 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.5.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.5.2. Function Symbols and the Iota Operator

Bergmann et al., pp. 319-322
Sider, pp. 146-147

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

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.

Problem Sets

Continue to Part 6: Metalogic and Conclusion →