0
$\begingroup$

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

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

1 Answer 1

4
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .