# Can this be a valid way to prove the Principle of Mathematical Induction?

In Calculus I, Apostol appeals to the definition of an inductive set given in previous pages to prove the PMI (it's somewhat funny because the proof is just two lines).

I have been trying to do it in another way. I would like to know whether there is something wrong with it.

Theorem (I.36): Principle of Mathematical Induction: Let $S$ be a set of positive integers which has the following properties:

• (a) The number $1$ is in the set $S$.
• (b) If an integer $k$ is in $S$, then so is $k+1$.

Proof:

Let suppose that there is a set $S \subset \mathbb{N}$ which contains $1$ and an integer $k > 1$. Let assume that $k+1 \notin S$ (i.e. property (b) does not hold). Then it follows that if $k$ is in $S$, then so is $k-1 = m$, which is the same as saying that, for every integer $m \geq 1$ in $S$, there is an integer $m+1 \in S$. Hence properties (a) and (b) are fulfilled, $\implies S = \mathbb{N}$.

• Your conclusion must be, then $S$ is the set of of all positive integers right? Commented Feb 18, 2015 at 19:06
• @JrAntalan Something like this: ''...properties $\mathbf{(a)}$ and $\mathbf{(b)}$ of the theorem are fulfilled. Therefore S = $\mathbb{N}$''?
– asd
Commented Feb 18, 2015 at 19:09
• Got it, will leave an answer now. Commented Feb 18, 2015 at 19:11
• I gave my answer already, looking at your proof, its a nice attempt a bit modfication will lead you to the proof of your qestion... Commented Feb 18, 2015 at 19:29
• @JrAntalan I've just modified it a little. Does it look better now?
– asd
Commented Feb 18, 2015 at 19:31

We want to show that if (a) and (b) is satisfied by $S$ then $S=\mathbb{N}$.

Suppose to the contrary that $S \neq \mathbb{N}$. This means that there is another set of positive integers $T=S'$ (relative to $\mathbb{N}$) such that $S\cup T= \mathbb{N}$.

Since $T$ is a set of positive integers, then, by the Well Ordering Principle, it must have a least element say $a \neq 1$ since $1 \in S$. Now, we are sure that $a-1$ is in $S$, $a$ being the least element in $T$. But by (b), since $a-1\in S$, it must be that $a\in S$. A contradiction. Thus, $S= \mathbb{N}$.

• I would say that $k+1 \in T$ then. But I'm not sure how that can be included in my attempt at giving a proof or whether it's ok without bringing another set $T$ into the picture.
– asd
Commented Feb 18, 2015 at 19:20
• If your proof is via contradiction, I think that you must introduce a new set $T$. If your proof is a direct proof.... there is no need for $T$. Commented Feb 18, 2015 at 19:31
• Ah, I see. Thank for the clarification.
– asd
Commented Feb 18, 2015 at 19:34
• Your welcome jazz. Commented Feb 18, 2015 at 19:41