# Proof of principle of finite induction using well ordering principle

I was reading Elementary Number Theory by David Burton and in the first chapter it had a proof of Principle of Finite Induction.

The principle of Finite Induction states that for a set $S$ containing positive integers such that:

a. $1 \in S$

b. If integer $k$ belongs to $S$, then $k+1$ also belongs to $S$.

Then $S$ is the set of all Positive Integers.

My proof was as follows:

Let $T$ be a set of positive integers that do not belong to S, such that $a$ is the least element of $T$. Then we have that $a\notin S$. So we must have that $a-1 \notin S$, because if it would have been in $S$, then by condition $(b)$, $a\in S$ which is a contradiction. So $a-1 \notin S \implies a-1 \in T$. This is a contradiction to assumption that $a$ is the least element. Thus $T$ is empty?

Is this a valid proof?

Actually I began in a similar way as David Burton, but some different paths..

Thank you! Please don't be angry because I have just started to learn these things!

• your statement of the principle of Finite Induction seems incomplete. – Mirko May 28 '17 at 4:42
• Oh yes sorry I missed a statement. – samjoe May 28 '17 at 4:43
• You didn't say what $T$ was. I assume you meant that IF $S$ was not the set of all positive integers, THEN $T$ is the set of all integers that are not in $S$. – Mirko May 28 '17 at 4:47
• Adding to Mirko's point. You should state when you take $a$ to be the least element of $T$ that you are making the assumption that $T \neq \emptyset$. – Trevor Gunn May 28 '17 at 4:49
• Um, what's the relation between T and S? Why is a not in S? Why does a-1 not in S imply a-1 in T? Would a -1 be in T if elephants ate steaks? So far as I can tell that is no less relevant. And if T is empty what does that have to do with S? I feel you wrote a key step on paper and simply forgot to include it. Namely what does T have to do with S. – fleablood May 28 '17 at 5:00

## 1 Answer

Your proof is almost correct but needs to be written more carefully. You say $a - 1 \notin S$ because then $a = (a - 1) + 1 \in S$. Which is fine except that $a - 1$ may not exist. That is, if $a = 1$ then $a - 1$ is not a positive integer. This is fine because it is taken care of by condition (a). Notice that with this correction, the proof uses both condition (a) and condition (b). You should use this as a sanity check when writing a proof: make sure that you are using all of the conditions and hypotheses.

A more precise start to the proof should read something like the following.

Suppose $S$ is a set of positive integers satisfying (a) and (b). If $S$ is not the entire set of positive integers, then its complement, $T$, is non-empty. By the well-ordering principle, there exists a least element $a$ of $T$ and by condition (a), this element must be $> 1$.

• Obviously a > 1 – samjoe May 28 '17 at 4:51
• @samjoe Yes, but you should mention that in your proof. – Trevor Gunn May 28 '17 at 4:52
• I understand your answer. We must state whatever we are assuming – samjoe May 28 '17 at 5:17