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$.


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}$.

  • $\begingroup$ Your conclusion must be, then $S$ is the set of of all positive integers right? $\endgroup$ – Jr Antalan Feb 18 '15 at 19:06
  • $\begingroup$ @JrAntalan Something like this: ''...properties $\mathbf{(a)}$ and $\mathbf{(b)}$ of the theorem are fulfilled. Therefore S = $\mathbb{N}$''? $\endgroup$ – Jazz Feb 18 '15 at 19:09
  • $\begingroup$ Got it, will leave an answer now. $\endgroup$ – Jr Antalan Feb 18 '15 at 19:11
  • $\begingroup$ 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... $\endgroup$ – Jr Antalan Feb 18 '15 at 19:29
  • $\begingroup$ @JrAntalan I've just modified it a little. Does it look better now? $\endgroup$ – Jazz Feb 18 '15 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}$.

  • $\begingroup$ 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. $\endgroup$ – Jazz Feb 18 '15 at 19:20
  • $\begingroup$ 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$. $\endgroup$ – Jr Antalan Feb 18 '15 at 19:31
  • $\begingroup$ Ah, I see. Thank for the clarification. $\endgroup$ – Jazz Feb 18 '15 at 19:34
  • $\begingroup$ Your welcome jazz. $\endgroup$ – Jr Antalan Feb 18 '15 at 19:41

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.