Second-Order Logic: Logic or Set Theory in Disguise?

1. What is Second-Order Logic?

Before we can debate its status, we need a clear idea of what second-order logic is and how it differs from the first-order logic you already know. In first-order logic, quantifiers like $\forall x$ and $\exists x$ range over individual objects in a domain. Second-order logic adds new variables (e.g., $X,Y,P$) and quantifiers ($\forall X,\exists X$) that range over properties of those objects.

The following short video provides an excellent, clear introduction to this distinction.

As the video explains, a first-order statement might be "There exists an x such that x is a prime number," written $\exists x\text{IsPrime}(x)$. A second-order statement could be "There exists a property P such that Socrates has P," written $\exists PP(\text{socrates})$. This ability to quantify over properties gives SOL tremendous power.

The Expressive Power of Second-Order Logic

One of the main motivations for using SOL is its ability to characterize mathematical structures categorically, meaning it can define them up to isomorphism. First-order logic, due to the Löwenheim-Skolem theorem, cannot do this for any theory with an infinite model. For any infinite structure, there are always other, non-isomorphic structures that satisfy the same first-order sentences (e.g., non-standard models of arithmetic).

Second-order logic overcomes this. For instance, the axioms of Peano Arithmetic can be formulated in SOL with a single induction axiom that quantifies over all properties (sets) of numbers:

This axiom states that for any property $X$, if 0 has it and it's passed from $n$ to its successor $s(n)$, then all numbers have it. Because this quantifies over all subsets of the natural numbers, it rules out non-standard models. Any model satisfying the second-order Peano axioms is isomorphic to the standard natural numbers.

This expressive strength is a major point in its favour. For many mathematicians and philosophers, SOL better captures the intended meaning of mathematical theories. However, this power comes at a great philosophical and technical price.

2. The Indictment: "Set Theory in Sheep's Clothing"

The primary critique of second-order logic, most famously articulated by W. V. Quine, is that its semantics are inextricably linked to set theory. The meaning and truth of SOL sentences depend on a background theory of sets, making it less a pure logic and more a branch of mathematics.

The most damning piece of evidence is that we can formulate second-order sentences whose validity is equivalent to deep, unresolved problems in set theory, like the Continuum Hypothesis (CH).

Let's break down the significance of this:

• The Continuum Hypothesis (CH) is the claim that there is no set whose cardinality is strictly between that of the integers and the real numbers.
• Gödel (1940) and Cohen (1963) proved that CH is independent of the standard axioms of set theory (ZFC). This means you can't prove it or disprove it from ZFC.
• The existence of a sentence ${\theta }_{CH}$ in SOL that has a model if and only if CH is true means that the question of whether ${\theta }_{CH}$ is valid depends on your background set theory.

This leads to the problem of non-absoluteness. The truth value of a second-order sentence can change depending on which model of set theory you inhabit.

For critics like Quine, this is unacceptable for a system claiming to be logic. Logic is supposed to be the bedrock of reasoning, independent of specific mathematical assumptions. If the validity of a logical formula depends on an open question like CH, then that system is no longer pure logic; it's set theory.

This entanglement is also why SOL loses the key metatheoretical properties of first-order logic:

• Completeness: There is no effective proof system that can derive all valid second-order sentences.
• Compactness: It's not true that if every finite subset of a set of SOL sentences has a model, the whole set has a model.
• Löwenheim-Skolem Theorem: SOL has sentences that only have uncountable models, so the theorem fails.

These are not just technical losses; they are losses of the very features that make first-order logic a stable, well-understood, and universally applicable framework for formal reasoning.

3. The Defence of Second-Order Logic

Despite these powerful criticisms, many philosophers and logicians defend SOL's status as logic. They argue that its expressive power is a feature, not a bug, and that the Quinean critique relies on a particular conception of what logic must be.

An Inferentialist Perspective

One line of defense comes from inferentialism, the view that the meaning of logical constants is given by their inference rules, not by their model-theoretic semantics. In the previous lesson, we saw how this idea functions in the context of logical pluralism. Greg Restall applies a similar approach to defend SOL.

He uses Nuel Belnap's criteria for when a new connective (or quantifier) is genuinely logical:

1. Existence (Conservativeness): Adding the new rules to your language should not allow you to prove new statements that don't involve the new symbol. It shouldn't collapse your system.
2. Uniqueness: The rules should define the symbol uniquely. Any two symbols following the same rules should be inter-derivable.

Restall argues that the standard introduction and elimination rules for the second-order quantifier $\forall X$ meet Belnap's criteria. They are a conservative extension of the base logic, and they uniquely define the quantifier's role. From this perspective, the quantifier $\forall X$ has just as much right to be called 'logical' as $\forall x$ or $\wedge$.

So where does the problem lie? Restall argues the issue isn't with the logic of SOL, but with the choice of models. The incompleteness arises from a mismatch between the proof rules and the standard semantics, where $\forall X$ means "for all subsets".

Standard vs. Henkin Semantics

This brings us to the crux of the technical and philosophical debate:

• Standard Semantics: Assumes that second-order variables range over the full power set of the domain of individuals. This is the source of both the great expressive power (categoricity) and the metatheoretical problems (incompleteness, dependence on CH).
• Henkin Semantics: Generalizes the semantics by allowing second-order variables to range over a specified collection of subsets of the domain, not necessarily all of them.

With Henkin semantics, second-order logic regains completeness. A sentence is a theorem if and only if it is true in all Henkin models. However, this comes at a cost. A Henkin model is essentially a two-sorted first-order model—one sort for individuals, one for 'properties'—with an axiom schema for comprehension. The critic can now say: "See! You've just recreated the problem. You've made SOL behave by turning it into a first-order theory in disguise."

Restall suggests an intermediate path. He argues that while Henkin models are useful for characterising provability, there's something defective about non-standard ones. Standard models are more 'stable' because they are not vulnerable to being falsified by simply expanding the language with a new predicate. This suggests that standard models, despite their problems, capture something essential about the intended meaning of second-order quantification.

Conclusion

The debate over second-order logic is a clash of fundamental intuitions about what logic should be.

• On one side (the Quinean critique): Logic must be topic-neutral, ontologically innocent, and possess a complete proof theory. Its validity should not depend on substantive mathematical questions. By these criteria, SOL is not logic; it is mathematics—specifically, set theory.

• On the other side (the defense): Logic is the study of the most general forms of reasoning, and its language should be as expressive as needed for this task. The ability of SOL to capture the intended meaning of mathematical structures is a sign of its logical power. The metatheoretical 'defects' are a necessary price for this expressiveness.

There is no consensus on this issue. Your position likely depends on whether you prioritize the metatheoretical purity of first-order logic or the expressive richness of second-order logic. The debate reveals that the boundary between logic and mathematics is not a sharp line, but a philosophically contested border.

Key Takeaways:

• Second-order logic (SOL) extends first-order logic by allowing quantification over properties and relations.
• This gives SOL immense expressive power, allowing it to define structures like the natural numbers categorically.
• The primary criticism, from Quine, is that SOL is "set theory in sheep's clothing" because its semantics are tied to set theory.
• The truth of SOL sentences can be non-absolute, depending on background set-theoretic axioms like the Continuum Hypothesis (CH).
• SOL lacks the key metatheoretical properties of FOL: completeness, compactness, and Löwenheim-Skolem.
• The debate is often framed by the choice between standard semantics (powerful but incomplete) and Henkin semantics (complete but less powerful, resembling a two-sorted FOL).

Preview of the Next Lesson:

In our next lesson, we will continue this theme of fundamental disagreement by asking: Assess whether disagreements between classical and non-classical logicians are genuine disputes or merely verbal. This connects directly to today's lesson. When a classical logician and an intuitionist argue about the Law of Excluded Middle, are they disagreeing about a fundamental logical principle, or are they, as Quine might suggest, simply "changing the subject" by using logical connectives with different meanings? This question probes the very nature of logical debate.