The Falling Dominoes of the Principle of Proof by Mathematical Induction, #2.

(Wikipedia, 2025)

TABLE OF CONTENTS

1. Introduction

2. The Definition of Mathematical Induction

3. Wang’s Paradox and the Predicate “Small”

4. Edward Nelson’s Critique of Mathematical Induction

5. Mathematical Induction Meets Gödel’s Incompleteness Theorems

6. Omega-Consistency and Its Role in Gödel’s Theorems

7. A Foundational Skepticism about Mathematical Induction

8. A Foundational Skepticism about Mathematical Induction

9. Conclusion

This essay will be published in three installments; this one, the second, contains sections 4-6.

But you can also download and read or share a .pdf of the complete text of this essay, including the REFERENCES, by scrolling down to the bottom of this post and clicking on the Download tab.

4. Edward Nelson’s Critique of Mathematical Induction

Edward Nelson’s work Predicative Arithmetic (Nelson, 1986) is a perfect springboard. Nelson doubted mathematical induction because it assumes an infinite totality of natural numbers exists “all at once,” which he rejected as a finitist. He argued:

Mathematical induction allows proofs of statements (e.g., ∀ n, P(n)) that imply infinite sets, which predicative systems avoid.

Nelson wrote:

[T]he reason for mistrusting the induction principle is that it involves an impredicative conception of number. It is not correct to argue that induction only involves the numbers from 0 to n; the property of being n being established may be a formula with bound variables that are thought of as ranging over all numbers. That is, the induction principle assumes that the natural number system is given. A number is conceived to be an object satisfying every inductive formula; for a particular inductive formula, therefore, the bound variables are conceived to range over objects satisfying every inductive formula, including the one in question. (Nelson, 1986: p. 1)

Thus the principle of mathematical induction has its own metaphysical presuppositions, which are questionable from the position of finitism, which we are sympathetic to. We will not be pursuing that issue in detail either, dealing with it in another article, because we are concerned in the rest of this essay with a more general argument against the principle of mathematical induction. The point in mentioning this is to show that the principle of mathematical induction is not immune to philosophical critique.

5. Mathematical Induction Meets Gödel’s Incompleteness Theorems

In 1931, Kurt Gödel published two landmark results that fundamentally changed our understanding of formal mathematical systems. These are known as Gödel’s First and Second Incompleteness Theorems.

First Incompleteness Theorem

Gödel showed that in any consistent formal system S that is sufficiently powerful to express basic arithmetic (such as Peano Arithmetic), there exist true mathematical statements that cannot be proved within that system. In other words, S is incomplete: there are propositions that are true but unprovable inside S. The proof constructs a self-referential statement (often called the “Gödel sentence”) that effectively says, “This statement is not provable in system S.” If the system could prove this statement, it would lead to a contradiction. Hence, assuming the system is consistent, the statement cannot be proved in S—but it is true.

Second Incompleteness Theorem

Gödel’s second theorem goes further, stating that such a system S cannot prove its own consistency. That is, assuming S is consistent, the statement expressing “S is consistent” cannot be proved within S itself. Stated formally:

Let S be a formal axiomatic system that:

Is consistent (does not prove contradictions),

Is effectively generated (its axioms can be listed by an algorithm),

Is sufficiently expressive to encode elementary arithmetic (e.g., Peano Arithmetic).

Gödel’s First Incompleteness Theorem says that

There exists a statement G in the language of S such that:

If S is consistent, then S does not prove G and does not prove not-G.

In words: G is undecidable in S. Neither G nor its negation ¬G can be proved within S if S is consistent.

The statement G can be interpreted as:

“This statement is not provable in S.”

Gödel’s Second Incompleteness Theorem:

Let Con(S) be a formal statement in S expressing that S is consistent. Then, assuming S is consistent,

S does not prove Con(S).

That is, S cannot prove its own consistency.

The formalization uses the notion of arithmetization of syntax: statements and proofs in S are encoded as natural numbers (Gödel numbering). The system must be strong enough to represent basic arithmetic properties and reason about proofs. These results dashed hopes that a system could demonstrate its own freedom from contradiction using only its own rules. Gödel’s incompleteness theorems reveal fundamental limits to formal systems: no sufficiently strong, consistent system can be both complete (able to prove all truths) and able to prove its own consistency.

6. Omega-Consistency and Its Role in Gödel’s Theorems

Here is the definition of Omega-Consistency:

A formal system S is ω-consistent if it never proves a statement of the form ¬P(0), ¬P(1), ¬P(2), …

for every natural number n, while at the same time proving
∃x P(x).

In other words, S does not prove that some property P holds for some natural number x, while simultaneously proving that P(n) fails for every individual natural number n.

What is the relation to Gödel’s First Incompleteness Theorem?

• Gödel’s original proof of the First Incompleteness Theorem assumed ω-consistency, a stronger form of consistency.

• Under ω-consistency, Gödel constructed a statement G (the Gödel sentence) which is true but unprovable in S.

• Later work (notably by Rosser) showed that the theorem holds assuming only ordinary consistency, not requiring the stronger ω-consistency.

Why does Omega-Consistency matter?

• ω-consistency prevents a system from having a certain kind of internal contradiction involving infinite sequences of statements.

• It is stronger than ordinary consistency but weaker than full soundness.

• Some intuitionistic and constructive frameworks reject ω-consistency because it presupposes a completed infinite totality of natural numbers, which can be philosophically problematic.

What is the relation between Omega-Consistency and Gödel’s Second Incompleteness Theorem?

• Gödel’s Second Incompleteness Theorem implies that a sufficiently strong system S (such as Peano Arithmetic) cannot prove its own consistency. Since ω-consistency is a stronger form of consistency, S also cannot prove its own ω-consistency.

• In particular, if we denote by Con_ω(S) the formal statement expressing the ω-consistency of S, then:

S does not prove Con_ω(S).

• That is, assuming S is ω-consistent, it cannot internally prove this fact.

• This means the system cannot verify even this stronger consistency condition about itself from within, further highlighting the intrinsic limitations revealed by Gödel’s incompleteness results.

Download