Proving the equivalency of Principle of Mathematical Induction and Well Ordering Principle

Induction implies well order: Let $A$ be the set of all elements not in the non-empty $T$. Then $0\in A$ otherwise $0$ is the least element of $T$.

Assume that $k\in A$ for all $k<n$. If $n\in T$ then $n$ is the least element of $T$. Therefore $n\in A$. By induction all elements are in $A$ and then $T$ is empty.

Well order implies induction: Let $P$ be a property such that $P(0)$ and such that for all $n$ if $P(k)$ for all $k<n$ then $P(n)$. Let $T$ be the set of elements not satisfying $P$. If $T$ is non-empty, then it has a first element $a$. Since it is the first element not satisfying $P$, then for all $k<a$ $P(k)$. By assumption $P(a)$. Contradiction. Therefore $T$ is empty, i.e. all elements satisfy $P$.

The answer from a student once: Let $A$ be a non-empty set. Consider $\sum_{x\in A}x$. If $A$ doesn't have a first element we cannot begin to sum. Contradiction.

Advice: First break the mindframe of only using induction when $P(n)$ is an algebraic formula in $n$,by solving problems involving other types of propositions. After a few examples involving disease spread, colors, geometric statements, etc. they are able to imagine the property $n\notin T$ as a candidate to run induction.


In your first part, there are a couple of things you should fix. Suppose by way of contradiction that $T$ is a non-empty set of positive integers with no least element and let $$W=\{x\in\Bbb N:x\notin T\}.$$ (Note the change, there.) Since $T$ is a set of positive integers, then $0\in W$. Since $T$ is non-empty, then there is some positive integer (so some natural number) $m\in T$. Hence, $W\subsetneq\Bbb N,$ but $0\in W,$ so by PMI, there is some $n\in W$ such that $n+1\notin W$ (meaning $n+1\in T$).

Now, clearly, $1\in W,$ for otherwise, $1$ would be the least element of $T$. But then $2\in W,$ for otherwise $2$ would be the least element of $T$. We can continue in this fashion through finitely-many steps (so PMI isn't brought into play in this part), and see that also $3,4,...,n-1\in W$. Hence, $0,1,2,...,n\in W,$ but $n+1\in T,$ so $T$ has a least element. Contradiction.

It's worth noting that I rewrote the proof in this part largely to avoid the use of what is known as complete induction, and use only PMI as stated in your post.


To continue your second part: We know that $x$ can't be $0$, since $0\in T$. Put $n=x-1$. Since $x$ is a positive integer, then $n\in\Bbb N$, and since $x$ is the least element of $\Bbb N\setminus T,$ then we know $n\in T$ (since $n<x$). But then by assumption $x=n+1\in T,$ a contradiction.