Proof strong induction with help of well-ordering theorem of $\mathbb{N}$

Question

I am preparing for my exam and need help/someone who could check my solutions for the following tasks.

1. Let $P(n), n\in \mathbb{N}$ (without $0$) be a propositional formula (if this is the correct english term) with the following properties.

• (a) There exist $m\in\mathbb{N}$ such that P(1), P(2),...,P(m) are true
• (b) Let k>m. If P(j) is true for all j<k, then P(k) is true.

Conclude from the well ordering theorem of $\mathbb{N}$, that $P(n)$ is true for all $n\in\mathbb{N}$

Let M be a nonempty set M:={$n\in\mathbb{N}$: $P(n)$ is not true}. According to the well ordering theorem, each subset of $\mathbb{N}$ has a smallest element. Let this smallest element of M be N. We know N can't be $1-m$, since P(1),...,P(m) is true. Thats why N>m. Since N is the smallest element for which P(n) is not true, then P(n) is true for all k<N and therefore for all j<k<N. But P(j) is true for all j<k implies that P(n) is true for all elements bigger than j(because of (b)), which would mean that P(N) is also true. A contradiction and therefore M is an empty set. Is this proof correct? I did this task months ago as an exercice and got full points. But I am not really satisfied with this solution and believe, that this proof is not 100% correct.

I would be grateful for any advice.

Answer 1

Your proof is correct. There is only one thing I would clean up.

After establishing $N > m$ and that $P(k)$ is true for all $k < N$, just immediately apply (b) to get P(N) is true (Here $N$ is playing the role of $k$, and $k$ is playing the role of $j$).