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

I would like to know how from the very basic I can teach some one the above title statement. Here is my plan.

$\textbf{First}$ I will state WOP: Every non-empty set of positive integers contains a least element.

$\textbf{Second}$ I will state PMI:

$(1)$ $0\in T$.

$(2)$ $n\in T\implies n+1\in T$

We show that $T=\Bbb N$.

Suppose I want to prove $\textbf{First}$ statement using The $\textbf{second}$

So I take $T$ be a non-empty subset of natural number, enough to show it has a least element. ( is that right?)

$\textbf{proof}:$ Assume by contradiction that $T$ has no least element, let $$W=\{x:x\notin T\}$$ since $0$ is a lower bound of natural number so $0\in W$, now here can I say like this: let $0,1,\dots,n\in W\Rightarrow n+1\in W$. Then $n+1$ can not be in $T$ since then it would be a lower bound of $T$ and since $0,1,\dots,n\notin T$, so $n+1\notin T$ by induction $W=\mathbb{N}$, so $T=\phi$

$\textbf{Now}$ Suppose every nonempty subset of $\Bbb N$ has a least element. Let $T$ be a subset of $\Bbb N$ with the following properties

$(1)$ $0\in T$.

$(2)$ $n\in T\implies n+1\in T$

We show that $T=\Bbb N$.

Let $T$ be as above. Consider the set of $\Bbb N\setminus T$, and assume by contradiction it is not empty. By the WOP, it has a least element, call it $x$.

I am not able to proceed further, Thank you for help and discussion.

-

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.

-
You might wanna add the student's answer here. – Git Gud Jun 30 '13 at 16:21
It's worth noting that the induction you're using here is what is often known as complete induction, and is not the same as PMI as stated above (though they are equivalent). – Cameron Buie Jun 30 '13 at 16:51
Strange name. I was always taught that complete was to distinguish from the (incomplete) induction as in: The sun has come out all this days, it will come out tomorrow. So, complete induction was just a name for mathematical induction. Strong is the name I have seen for this. – Mlazhinka Shung Gronzalez LeWy Jun 30 '13 at 17:40
Yeah. I am pretty sure Wikipedia is just perpetuating the mistake some author did in some book (logic.stanford.edu/intrologic/chapters/chapter_09.html). – Mlazhinka Shung Gronzalez LeWy Jun 30 '13 at 17:59
That's another common one. Although I've also seen that one used to refer to any induction between standard and complete induction. For example, I've seen the following referred to as "strong induction": If $P(0)$ and $P(1)$ both hold, and if $P(n+2)$ holds whenever $P(n)$ and $P(n+1)$ do, then $P(n)$ holds for all $n$. – Cameron Buie Jun 30 '13 at 20:03

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.

-
your contradiction seems very strange, what we need to prove that is a contradiction? I did not get the point – Un Chien Andalou Jun 30 '13 at 16:49
Which contradiction? One contradiction came from the assumption that $T$ was an inductive set of naturals, so since $n\in T$ we know $n+1\in T$. But by definition of $n:=x-1,$ we have $x\in T$, and we chose $x$ to be the least element that wasn't in $T,$ so we have a contradiction. In the other, we showed that $T$ has a least element, but we assumed that it didn't have a least element, so we have a contradiction. – Cameron Buie Jun 30 '13 at 16:55
yeah, I am asking about the 2nd contradiction in your comment, we needed to show that $T$ has a least element right? and you finally proved it, then why did you assume that it does not have a least element? – Un Chien Andalou Jun 30 '13 at 17:16
The assumption that $T$ is non-empty allowed us to bring PMI (as you stated it) into play and get $n\in W$ such that $n+1\notin W$. The assumption that $T$ had no least element was then used to show that each of $1,...,n-1\in W$. We could go another way, though: (a) Prove as a Lemma that any finite non-empty set of positive integers has a least element. (PMI will be used here.) (b) Assume that $T$ is a non-empty set of positive integers. (c) Find $n\in W$ such that $n+1\notin W$ (as above). (d) Conclude that if $n+1$ isn't the least element of $T$, then ... – Cameron Buie Jun 30 '13 at 17:33
... the set of elements of $T$ strictly between $0$ and $n$ has a least element by our Lemma, and that least element will be the least element of $T.$ – Cameron Buie Jun 30 '13 at 17:33