Why is this more-detailed proof more acceptable than its trivial counterpart?

Question

Say that we're asked to give a proof of 'proof by induction'.

i.e. for some property $P$, proving that $$\forall n,P(1) \wedge [P(k) \implies P(k+1)] \implies \forall n, P(n)$$.

Now, I understand the following proof, but it seems rather superfluous:

Assume that $P(1)$ and that $P(k) \implies P(k+1).$

Assume, towards a contradiction, that there exists at least one positive integer $n$ such that $P(n)$ is false, which means the set $S=\{n:P(n) \ \text{is false}\}$ is nonempty.

By the well-ordering property, there exists a smallest element of $S$- let's call it $m$ ($\in \Bbb{Z^+}$)

Now, $m\neq 1$, since $P(1)$ is true (by assumption), so $m>1$.

Now, $m-1<m$, and $m-1 \in \mathbb{Z^+}, $ so $\underbrace{m-1 \notin S}_{m \ \text{is the smallest element of }S}$, so $P(m-1) \ \text{is true}$.

But we have that $P(k) \implies P(k+1)$ by assumption, so $P(m)$ must be true (since $P(m-1)$ is true), a contradiction. Hence, the set $S=\{n:P(n) \ \text{is false}\}$ is empty. i.e. $\forall n, P(n)$. $\square$

Now, I think that this proof really labours the point. Why is it not sufficient just to say that $P(1)$ is true, and $P(k) \implies P(k+1)$, therefore, $P(2) \implies P(3) \implies P(4) \implies ... \implies P(n) \implies...$

Answer 1

Most of the time in mathematics, the concept of proof is an informal one, more importantly it is a social concept. Meaning that what counts as a proof is what certain people say it counts as a proof (e.g. your audience, your lecturer, journal reviewers, etc).

But there is another instance of what proof means, a well defined instance, namely that of formal proof.
Neither of your proofs is a formal one, so if any of them counts as a proof is something that is person-dependent.

Personally, at this level of elementary-hood, anything that includes $\ldots$ to me doesn't count as a proof, I'd rather call it a layout, plausibility argument or general description of what the actual ('social') proof would look like. (I would however accept $\ldots$ if used at a more complex level). I also reject anything related to drawings as proofs. I accept the first version as proof over the second one because it's much clearer how one would formalize it.

Answer 2

I agree that that what the OP proposed at the end of the question does not count as a proof of induction. When he writes $... \implies P(n) ...$, i.e., in English, "at some point this implies $P(n)$ for any natural number $n$", that is simply a restatement of the principle of induction, not a proof.

Mathematically, there are two ways that people usually introduce the principle of induction into the body of their work:

1. State it as a foundational axiom. Effectively one is saying, "this is so obvious that it simply must be true on its own". This is pretty close to what I think the OP is saying at the end of their question. This is definitely done in places, such as the famous Peano Axioms (see axiom 9).

2. Prove it from the (arguably) even more obvious well-ordering principle, which is taken as the axiom. This is interesting because the whole point of the axiomatic method in mathematics is to reduce the facts that must be taken on faith to the smallest and most obvious elements possible. Since a lot of people find well-ordering to be more basic, this is what's done in many texts.

Note that the two principles (induction and well-ordering) are in fact logically equivalent. A writer can take either one as an axiom, and then use that to prove the other. For example, in Peano's work, induction was taken as the axiom and well-ordering proved from that.

It's a bit of a personal taste issue about which principle feels more "fundamental" and is thus taken as the axiom. But as soon as you say "prove induction", this can't be literally from nothing; it must make use of some more basic prior assumption/axiom.