Working of Mathematical Induction

Question

I am aware of what proof by Mathematical Induction is. I have also used it in numerous proofs. However, I don't understand formal correctness/validity of the method down to the level of Peano Axioms. I mean I understand intuitively that because "p holds for 0" is provable, and that "if p holds for n, then p holds for n+1" is provable, then, because 0 is also a natural number, it follows that p holds for all n.

The conditional: "if it holds for n, then it holds for n+1" seems a bit like overstepping. First how is n "encoding" the essence of natural number, for it must so that the conditional applies to natural numbers in the first place. Secondly, how am I sure that in the proven sentence "...holds for n+1", symbol "+" is working as we understand it, and means that only...?

Answer 1

The Peano axioms are dependent on first-order logic. In first-order logic, we already have the ability to make statements such as "for all n, P(n) implies P(n+1)" - except that "n+1" is not part of first-order logic and instead comes from Peano arithmetic. But n+1 is well-defined: it's just a neat way to write the successor operator, which is an explicit part of the Peano axioms.

Unfortunately, that's where we run out of luck. The problem you will then run into is that the standard induction axiom is actually an axiom schema. That is, there is a separate instance of the induction axiom for each possible choice of predicate. We have to do this, because first-order logic cannot say something like "for all predicates, ..." - you need second-order logic to make a statement like that. As a result, the induction axiom is a bit weirder than the other Peano axioms, but this sort of thing is not so uncommon in the broader context of Zermelo-Fraenkel set theory (see e.g. the axiom schema of specification).

Nevertheless, there's an easy way to sidestep all of this. Completely replace the induction axiom with the well-ordering principle, which is as follows:

The set of natural numbers is well-ordered under its usual ordering.

If you like, we can replace "well-ordered" with its definition, giving us this:

Every non-empty subset of the natural numbers has a least element, under the usual ordering.

"Under its usual ordering" just means that we consider 1 to be less than 2, which is less than 3, and so on, as one would expect. You could instead choose to order the numbers in some other way, which is why we have to specify that we're talking about the "usual" ordering. Although our "and so on" may sound like a handwave, you can rigorously specify this if desired.

In my opinion, this axiom seems like it should be relatively uncontroversial. Try playing around with different subsets of the positive integers. It should be fairly obvious that, even if you use an infinite subset, you still always have a smallest element, right?

Now, how is this equivalent to mathematical induction? Well, to prove something with induction, we usually do something like this:

1. Prove that some predicate P holds for 1 (or for 0, if you consider 0 to be natural), which we write as P(1) or P(0).
2. Prove that P(n) implies P(n+1), most often by conditional proof.
3. Use the axiom of mathematical induction to conclude that P(n) holds for all natural numbers.

Here's how we would do this with the well-ordering principle:

1. As before, prove P(1) or P(0).
2. As before, prove that P(n) implies P(n+1).
3. Take the contrapositive, to get not P(n+1) implies not P(n). If it is more convenient, we may choose to skip step (2) and prove this statement directly.
4. Assume that there exists a nonempty set S consisting of all counterexamples, i.e. positive integers for which P(n) does not hold.
5. By the well-ordering principle, S must have a smallest element. Call that element k.
6. By (1), k > 1 or k > 0, so k-1 is a natural number.
7. By (3), not P(k) implies not P(k-1). So k is not actually the smallest element of S, creating a contradiction.
8. By reductio ad absurdum, S must be empty.

Answer 2

It doesn't matter if "n+1" works as we understand it. It doesn't matter what the topic is or what the successor operator is, so long as it follows the axioms. For example, suppose I lay out the following axioms:

1. a < b -> not b < a and not b=a
2. a < b and b < c -> a < c

From these axioms I can prove various things, among them:

a < b and b < c and c < d -> a < d.

Now it doesn't matter what "<" stands for. It could be the traditional less than. It could mean greater than. It could be that a < b means that a comes before b in a queue. It could mean that a is nested inside b like in one of those toys with a bunch of eggs stacked inside each other. It doesn't matter. The only thing that matters, is that whatever interpretation you put on "<", it follows the axioms. If it follows the axioms, then all of the theorems will be true of it.

The same holds for Peano arithmetic. The "zero" of Peano arithmetic doesn't have to be the number 0 and the successor function doesn't have to be the "+1" function. In Peano's own formulation of his axioms, he used one instead of zero, so the theorems described the classical natural numbers (the positive integers). Later logicians thought it was more convenient to start with zero, so they defined the natural numbers to include 0.

Alternatively, the successor function could mean to subtract one instead of add one. Then the Peano axioms describe the negative integers. Alternatively, "zero" could be the empty string, and the successor function could refer to appending the letter "a", so instead of the numbers 0, 1, 2, 3, etc. the Peano axioms are describing the strings "", "a", "aa", "aaa", etc. The theorems are still true.

The only thing that matters is that whatever you are talking about satisfies the axioms. As long as it does, the theorems are true, so the real question comes down to how you know that the natural numbers satisfy the Peano axioms. How do we know that they do? Well, that's a deep philosophical question. A rationalist would say that we have some sort of built-in knowledge of mathematics, some special intuition about it. An empiricist would put it down to experience, or try to explain that it's just a definition in some sense. Either way, the question of how we know that axioms are true is a long-standing problem in philosophy.

Answer 3

I'm a little rusty on mathematical induction, but if I recall correctly, a conditional like "if p holds for n, then p holds for n+1" is never just posited as a premise. It's always derived from more basic steps of the proof. As for how we know the symbols (like "n" and "+") mean what we take them to mean, or function only as we intend them to function: The symbol "n" is decreed by convention to represent the concept "any natural number," and we make it represent that by only permitting for "n" the same operations we would permit for "any natural number." (Same with "+" and addition.) In other words, the symbol is a shorthand notation for a well-defined concept in mathematics, and the shorthand notation can always be translated into verbal formulations of the concepts they're assigned to represent, and all the same rules apply to both; that's how we know they're doing the same thing and therefore mean the same thing. (Side-note: I don't think 0 is a natural number.)