2. Quine’s Mathematical Logic and Stratification
Quine - New Foundations for Mathematical Logic (1937)
Willard Van Orman Quine proposed New Foundations for Mathematical Logic as a direct alternative to the rigid Theory of Types established by Whitehead and Russell in Principia Mathematica.
Quine’s objective was to translate pure mathematics into formal logic utilizing a completely minimized primitive vocabulary, abandoning hierarchical type theory to allow for the existence of a single, universal class (\(V\)).
- Quine, W. V. (1937). New Foundations for Mathematical Logic. The American Mathematical Monthly, 44(2), pp. 70-80.
The Primitives
Imagine building an entire programming language from just three CPU instructions. Quine’s language operates strictly on three primitive mathematical constructs:
- Membership: \(x \epsilon y\) (Object \(x\) belongs to set \(y\))
- Alternative Denial: \((\phi\vert{}\psi)\) (The logical NAND gate)
- Universal Quantification: \((x)\phi\) (For all \(x\), \(\phi\) is true)
Everything else in mathematics—from addition to complex geometry—must be built from these three atoms. To prevent human mathematicians from writing endless strings of NAND gates, Quine created 15 Derivative Definitions to act as typographical macros.
The 15 Derivative Definitions
Quine groups his definitions into logical phases. By unpacking these phases, you can see how higher-level human reasoning compiles down to raw syntax.
Phase 1: Boolean Connectives (D1 - D5)
Quine proves that every standard logical operator (AND, OR, NOT) can be simulated using only the NAND gate (\(|\)).
- D1: Denial (Not)
\(\sim\phi =_{def} (\phi\vert\phi)\) > Why it matters: Passing the exact same proposition into both sides of a NAND gate creates an absolute logical NOT. - D2: Conjunction (And)
\((\phi\cdot\psi) =_{def} \sim(\phi\vert\psi)\) > Why it matters: By wrapping the NAND operation in a negation (D1), the system constructs logical AND. - D3: Implication (If-then)
\((\phi\supset\psi) =_{def} (\phi\vert\sim\psi)\) - D4: Alternation (Or)
\((\phi\lor\psi) =_{def} (\sim\phi\supset\psi)\) - D5: Equivalence (Iff)
\((\phi\equiv\psi) =_{def} ((\phi\vert\psi)\Vert(\phi\lor\psi))\)
Phase 2: First-Order Logic (D6 - D8)
With Boolean logic established, Quine defines existential quantifiers and identity without adding new primitive operations.
- D6: Particular Quantification (Exists)
\((\exists\alpha)\phi =_{def} \sim(\alpha)\sim\phi\) > How it works: “There exists an \(\alpha\)” is geometrically defined as “It is NOT the case that for ALL \(\alpha\), \(\phi\) is false.” - D7: Inclusion (Subclass)
\((\alpha\subset\beta) =_{def} (\gamma)((\gamma\epsilon\alpha)\supset(\gamma\epsilon\beta))\) - D8: Identity (Equals)
\((\alpha=\beta) =_{def} (\gamma)((\alpha\epsilon\gamma)\supset(\beta\epsilon\gamma))\) > Leibniz’s Law: Two objects are mathematically identical if and only if they belong to all the exact same classes. You don’t look inside the objects; you look at what contains them.
Phase 3: Definite Descriptions (D9 - D10)
How do we mathematically point to a specific object without knowing its name?
- D9: Description in Context
\(((\iota\alpha)\phi\epsilon\beta) =_{def} (\exists\gamma)((\gamma\epsilon\beta)\cdot(\alpha)((\alpha=\gamma)\equiv\phi))\) > Translation: “The specific \(\alpha\) (defined by \(\phi\)) is a member of \(\beta\).” - D10: Description as a Class
\((\beta\epsilon(\iota\alpha)\phi) =_{def} (\exists\gamma)((\beta\epsilon\gamma)\cdot(\alpha)((\alpha=\gamma)\equiv\phi))\) > Translation: “\(\beta\) is a member of the specific class \(\alpha\) (defined by \(\phi\)).”
Phase 4: Class and Relational Abstractions (D11 - D15)
This is the heart of Contextual Eliminability. Abstractions (like “the set of all even numbers”) are not real objects; they are temporary macros that explode into definite descriptions.
- D11: Class Abstraction
\(\hat{\alpha}\phi =_{def} (\iota\beta)(\alpha)((\alpha\epsilon\beta)\equiv\phi)\) > The Engine: This takes the notation for a set (\(\hat{\alpha}\)) and mechanically unpacks it into the definite description rules established in D9/D10. - D12: Unit Class (Singleton)
\(\{\alpha\} =_{def} \hat{\beta}(\beta=\alpha)\) - D13: Pair Class
\(\{\alpha,\beta\} =_{def} \hat{\gamma}((\gamma=\alpha)\lor(\gamma=\beta))\) - D14: Ordered Couple (Kuratowski Pair)
\((\alpha,\beta) =_{def} \{\{\alpha\},\{\alpha,\beta\}\}\) > The Fatal Flaw: Quine imported the standard Kuratowski ordered pair. If element \(\alpha\) is type \(n\), the set \(\{\alpha\}\) is type \(n+1\), and the nested set \(\{\{\alpha\}\}\) is type \(n+2\). This means the resulting ordered pair is a full two integer levels higher than its constituents! As you will see in the next module, this \(+2\) type-raising shift severely restricts relational mapping, creating massive stratification violations that Hailperin must fix using a “flat” or homogeneous ordered pair. - D15: Relational Abstraction
\(\hat{\alpha}\hat{\beta}\phi =_{def} \hat{\gamma}(\exists\alpha)(\exists\beta)((\gamma=(\alpha,\beta))\cdot\phi)\)
Postulates and The Principle of Stratification
To generate theorems, Quine relies on one core postulate (P1: Extensionality) and five rules of inference (R1-R5). The most critical rule is R3 (Principle of Abstraction), which states that for any formula \(\phi\), there exists a class containing exactly the objects satisfying \(\phi\).
However, an unrestricted R3 immediately triggers Russell’s Paradox. If \(\phi\) is “not a member of itself” (\(x \notin x\)), R3 generates a self-contradictory class.
To solve this without reverting to ZFC’s total ban on the Universal Set, Quine modified the rule to R3’: A formula can only generate a class if it is stratified.
[!IMPORTANT] What is Stratification? Stratification means you can assign integers to variables such that for every membership relation \(x \epsilon y\), the type of \(y\) is exactly one integer higher than \(x\) (\(n\) and \(n+1\)).
Formulas like \(x \epsilon x\) are unstratified (because \(x\) cannot be both \(n\) and \(n+1\) simultaneously). In NF, unstratified formulas are grammatically legal to write, but R3’ forbids them from generating sets. This nullifies the paradox while perfectly preserving the Universal Set \(V\) (because the formula \(x=x\), defining the universal set, is trivially stratified as \(n=n\)).
A Concrete Example of Stratification
Let’s test the formula: “There exists a set \(y\) such that \(x \epsilon y\) AND \(y \epsilon z\)”. In formal logic: \(\exists y (x \epsilon y \cdot y \epsilon z)\)
To prove this formula is stratified, we must assign an integer to every variable such that the right side of any \(\epsilon\) is exactly \(+1\) greater than the left side. 1. Let’s arbitrarily assign \(x = 1\). 2. Because of \(x \epsilon y\), \(y\) must equal \(x + 1\). Therefore, \(y = 2\). 3. Because of \(y \epsilon z\), \(z\) must equal \(y + 1\). Therefore, \(z = 3\).
We successfully mapped integers to all variables (\(x=1, y=2, z=3\)) without any contradictions. This formula is strictly stratified.
Guided Example: Stratification Types
Examine the formula: \(x \in y \land y \in z\)
If we declare that \(type(x) = 1\), then by the rule of stratification: \(type(y) = 1 + 1 = 2\)
What must \(type(z)\) be for this entire formula to remain strictly stratified?
\(type(z) = \_\_\_\_\_\)
Problem Set: Stratification in First-Order Logic
Before mapping ontologies in code, you must manually resolve stratification boundaries in pure logic.
Problem 2.1: Resolving Russell’s Paradox
In standard notation, Russell’s paradoxical class is generated by the formula \(\phi = (x \notin x)\). Write out the explicit typing (e.g., \(n\), \(n+1\)) that proves this formula is unstratified. Explain exactly why Quine’s Rule R3’ rejects its construction as a set.
Problem 2.2: The Universal Set Proof
The Universal Set (\(V\)) is defined by the formula \(x = x\). Using Quine’s definition of identity (D8), prove that this formula is strictly stratified and therefore legally generates the set of all sets under R3’.