# Proving well-ordering property of natural numbers without induction principle?

In Munkres, Topology, he has this way of proving the well ordering property for the natural numbers:

1. He assumes he can work with the real numbers from the for the real numbers

2. Then he defines an inductive set as a set containing 1, and if n is in the set then n+1 is in the set.

3. He then defines the positive integers as $\mathbb{Z}_+=\cap_{\text{A is inductive.}} A$.

4. Then he states the principle of induction by saying that if A is an inductive set of positive integers, then $A=\mathbb{Z}_+$

5. Then he shows that every nonempty subset of $\mathbb{Z}_+$ has a smallest element, by first proving that every nonempy subset of $\{1,2,3,...,n\}$ has smallest element. He does that by showing that the set of positive itnegers for which this holds, is inductive, and by4 it must then be all the natural numbers. Then if D is any subset of $\mathbb{Z}_+$ and n is an element of D, then $D\cap\{1,2,3,..,n\}$ must have a smallest element bu what we have shown, and we are done, since this is the smallest element for D also.

But do we need to use the principle of induction to show this? I tried making my own proof, and I do not use induction, is the proof wrong somewhere?

Here is my proof:

Let A be a subset of $\mathbb{Z}_+$. We assume that it is not empty, so it must containt an element n.

If 1 is in the set A, then 1 must be the smallest element. If not 1 is in A, but 2 is in A, 2 must be the smallest element. An so we continue, this procedure must stop because we know that n is in the set A. And hence we will find a smallest element.

Is there something wrong with this proof? I've seen proofs like this before, where they create a procedure, and argue that the procedure must stop at one point.

• They are actually equivalent, so you can't prove one without using the other. Your statement "and this procedure must stop" is true, but unjustified. In order to justify it, how would you proceed? – Cameron Buie Aug 24 '15 at 18:56
• @CameronBuie Either the procedure stops before n or not. If the procedure stops before n, then that is your smallest element, because any other element must be larger than it, since no other element is smaller than it. If it doesn't stop before n, than we know that all of the numbers in A must be bigger than or equal to n, and hence n is the smallest number. – user119615 Aug 24 '15 at 19:11
• I think the problem is that you have not explicitly defined the procedure, but rather, only heuristically. I think you will find that, in order to prove that the procedure is actually well-defined (regardless of how large $n$ is and what the set $A$ is), you must rely on induction, or perhaps on recursion (which itself relies on induction). – Cameron Buie Aug 24 '15 at 19:37
• @CameronBuie Yeah, it looks more like a recursive definition of a function than induction. I think I may define the procedure recursively like this, h(1)=1 if 1 is in A, if not 0 is in A, for k, I define h(k)=k, if k is in A, and $h(\{1,2,..,k-1\})=\{0\}$, if not $h(k)=0$ then the smallest element will be $h(\{1,2,3..,n\})-\{0\}$, and I will have that the image is two elements, because if the image of $h(\{1,2,..,n-1\})=\{0\}$, then $h(\{1,2,3..,n\})=\{0,n\}$. Is this a correct procedure you think? So when ever argument in books when they argue like this, they are actually using recursion? – user119615 Aug 24 '15 at 20:34
• Let me see if I understand you correctly. I will use the notation $$S_n:=\{1,2,...,n\},$$ as (I think) Munkres does. Your intention, then, is to define $$h(1)=\begin{cases}1 & 1\in A\\0 &1\notin A\end{cases}$$ and, for $k\in\Bbb Z_+\setminus\{1\},$ to define $$h(k)=\begin{cases}k & k\in A\text{ and }h(S_{k-1})=\{0\}\\0 &\text{otherwise.}\end{cases}$$ Is this correct? – Cameron Buie Aug 24 '15 at 23:56

"And so we continue, this procedure must stop because we know that $n$ is in the set $A$." That's induction right there; you are writing it informally enough that the induction is not explicit.
• The problem is, that sentence is both unjustified and imprecise. Think about it this way: at some point, you need to use some property of $\mathbb{N}$ which is not true of, say, $\mathbb{Q}$: this is because nonempty subsets of $\mathbb{Q}$ do not in general have least elements. So at some point in the argument - specifically, here - you need to use some property special to $\mathbb{N}$. – Noah Schweber Aug 24 '15 at 21:57
• Maybe a better example than $\mathbb{Q}$ is $\{{n\over n+1}: n\in\mathbb{N}\}\cup \{1+2^z: z\in\mathbb{Z}\}$ (basically, this looks like $\mathbb{N}+\mathbb{Z}$): here each element has a successor, so "move on to the next number" makes sense, but if $A= \{1+2^z: z\in\mathbb{Z}\}$ then obviously the "process" will not continue forever but also not "stop" at any specific stage. You need to prove that $\mathbb{N}$ has a property which guarantees that silliness like this doesn't happen. – Noah Schweber Aug 24 '15 at 22:01
• @user119615 Here's another way to approach it: you write "this procedure must stop because we know that $n$ is in the set $A$." Can you explain, precisely, why this is so (that is, why the first clause follows from the second)? I think if you try to pin down exactly what's going on, you'll see why this is induction in disguise. – Noah Schweber Aug 30 '15 at 2:29