Mathematical induction is a way to give finite proofs for (some of the) claims that concern infinitely many objects. For this reason it can be thought of as an approximation of the ω-rule. However, mathematical induction looks nothing like the ω-rule. And yet it is powerful enough in almost all cases. Of course, we know there are limits to this applicability (historically the first limit being the Gödel's sentence which can be easily proved with the ω-rule, but can't be proved using induction). But such cases are really rare.

So, how come the mathematical induction is so applicable? Or to put it in a different way, why does it approximate the ω-rule so well even though (on the surface) it does not seem to have any connection to the ω-rule?

A possible answer that occurred to me is that our minds tend to use patterns (recursive definitions) when reasoning about abstract concepts. Since we are finite, we have to use recursion for infinite objects too. Thus all the infinite objects we are interested in are either recursively defined, or somehow related to objects that are recursively defined. And induction very naturally fits with the recursion, for obvious reasons. Thus it may be that it is not that there is some deep reason for the applicability of the induction, but rather we are only really interested in those claims that fit the induction format well.

This question might have a good purely mathematical answer (e.g. a non-obvious link between mathematical induction and the ω-rule), but I feel the question is too soft for math sites on SE, so I'm posing it on philosophy.SE.


First, let me recall some details for readers unfamiliar with the topic:

The (classical) ω-rule intuitively says: if you can prove the sentence "P(n)" for each specific natural number n (conflating the number n with its corresponding numeral for simplicity), then you can prove the sentence "∀xP(x)." It takes a bit of care to make this precise and non-tautologous. Ultimately, what we have is a definition of a class of things called valid sequents, and the ω-rule is one rule among many (the others being the usual rules of the sequent calculus for first-order logic) which says the following:

If Γ ⊢ P(n) is a valid sequent for each specific natural number n, then Γ ⊢ ∀xP(x) is also a valid sequent.

(Think of "Γ ⊢ p" as meaning "From Γ we may infer p." The distinction between ⊢ and → can be hard to see at first, but it winds up being important; for now, just take it for granted.)

The set of ω-valid sequents is then the smallest set of expressions of the form "Γ ⊢ p" (for Γ a set of sentences and p a sentence in the language of arithmetic) which is closed under the sequent rules, including the ω-rule.

By contrast, induction - which I'll phrase as an inference rule here, to more closely compare with the ω-rule - says the following:

If Γ ⊢ P(0) is a valid sequent, and Γ ⊢ ∀x(P(x)→P(x+1)) is a valid sequent, then Γ ⊢ ∀xP(x) is a valid sequent.

Note that the ω-rule treats all instances equally and involves no high-complexity expressions, whereas induction treats 0 as special and involves a high-complexity expression (the "induction clause"). So there is indeed an apparent discrepancy between induction and the ω-rule.

OK, now on to the question. As is so often the case, I think it's helpful to respond with a new question:

What motivates the ω-rule in the first place?

Certainly we don't believe it in general - there are lots of discrete ordered semirings where it breaks down. Something about ℕ specifically means that it's enough to check every "concrete term" (think Herbrand semantics) in order to verify that a property holds globally. So where does that come from?

The answer will depend on presentation, of course, but broadly speaking we're looking at the well-ordering principle: ℕ is assumed from the get-go to be "minimal" in an appropriate sense. Specifically, no proper subset of ℕ can contain 0 and be closed under successor. But this exactly matches the form of induction! So really the ω-rule is a consequence of a "higher-level" (= set-theoretic) principle which does parallel induction.

This, I think, does partially address your question by explaining away the apparent difference in form between the ω-rule and induction. However, there's still the question of effectiveness of the latter. At this point it's worth observing that induction is actually parameterizable: rather than restrict the induction scheme to formulas of first-order logic, we can consider "𝔏-induction" for any logic 𝔏, e.g. second-order logic, fixed-point logic, ... See here for more on this idea.

So in a sense, the idea of an "internal induction scheme" is really setting the stage for a gradation of induction schemes. We can now consider the following spinoff of the "strength" part of your question: why is first-order induction so "close to the top" in the parameterized-induction-scheme hierarchy? This actually leads to some interesting apparently-open questions, but one bit of evidence is that any "reasonable" logic 𝔏 whose induction scheme is strictly stronger than that of first-order logic in fact pins down ℕ up to isomorphism. See e.g. here. The narrative that leaps to mind, then, is that "natural" properties of ℕ should be implied by fragments of the induction idea given by "reasonable" logics which don't require perfect information about ℕ, and that limits us exactly to first-order Peano arithmetic.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.