Principle of Strong Induction

114 Views Asked by At

I attempt a proof of the second principle of mathematical induction which I believe is this :

$S$ is a subset of $\Bbb N$ such that $1\in S$ and whenever $1,2,...,n\in S$, $n+1\in S$. Then $S=\Bbb N$.

Let $T:=\Bbb N \setminus S$. I must show that $T$ is empty. If possible let $T$ be nonempty. Then $T$ has a least element $m$. Since $1\in S, m≠1$. So $m-1$ must be a positive integer that is not in $T$ i.e. $m-1\in S$.

(If I were trying to prove the weak induction principle, this is where I use the hypothesis to show that $(m-1)+1=m\in S$, thus arriving at a contradiction and ending the proof. But here I must show that $1,2,...,m-1\in S$ in order to do that.)

Let $U:=${$n\notin S : 1<n<m-1$}. If possible let $U$ be nonempty. Then it has a least element $k≠1$. That means $1,2,...,k-1\in S \implies k\in S$, which is a contradiction. Thus $U$ must be empty. That is, $1,2,...,m-1\in S \implies m\in S$. This contradicts our very first assumption that $T$ is nonempty. So $T$ is empty and $S=\Bbb N$.

Is the proof alright?

1

There are 1 best solutions below

1
On BEST ANSWER

Note that for your $m$, $1, \ldots m-1 \in S$ by minimality (as they are all smaller than $m$ and so cannot be in $\mathbb{N}\setminus S$), so then $m \in S$ by the strong induction property. Contradiction.