Well ordering principle

Question

I am trying to understand why is the well ordering principle stated as an axiom of integers.

In the process, I found a "proof" of the principle (which is obviously wrong) and want to understand where the error is.

Let $S$ be a subset of $\mathbb{N}$, let $n \in S$. Then we have :

• Either $n$ is less than every other element of $S$ and then $S$ has a least element.
• Either the above is false, then take $m$ to be least element of the finite set $S\cap [0\ldots n]$ which is necessarily non empty (because if contains at least $n$ itself) and then $m$ will be less than any element of $S$.

Where is the error? Is it the use of axiom of choice when I take "let $n \in S$"? In that case is it true that axiom of choice implies well ordering principle of integers? (I know axiom of choice implies well ordering theorem, but here i am talking about well ordering principle of integers with natural order).

May be the error is assuming that every finite subset of $\mathbb{N}$ has a least element? Thanks for help.

Answer 1

First you are assuming that finite sets are well ordered without question.

Which I suppose follows from the induction principle.

But really the statement: $S \cap [0.... n]$ is necessarily non-empty or else $n$ would be the least element of $S$--- is simply wrong. You might as well say or else Micky Mouse would be a bulldog, for all the logical implication I can see.

Well, maybe that was an exageration.

$[0.... n]$ contains all natural number equal or less than $n$ so if $S\cap [0...n]$ is empty then one can conclude $S$ contains only natural numbers greater than $n$.

So what?

It certainly does NOT contain $n$ (because $S\cap [0...n]$ is empty; it does NOT contain $n$) and $n$ is certainly NOT the least element of $S$ ($n$ is not eve in $S$). You could conclude $n$ is less than any and all of the elements of $S$. ....

But what does that have to do with whether $S$ has a least element or not?

Answer 2

We need to be clear on our axioms here. I will be using this list of the Peano axioms because it includes an axiomatic ordering of the numbers and does not include an induction axiom nor the well ordering principle. We will also need ZFC.

There are some problems with your proof under these axioms:

1. The symbol $\{0, 1, \dots, n\}$ is not defined by any of the axioms. You have to define that yourself (probably using the axiom schema of specification).
2. None of the axioms guarantee that the resulting subset is finite (which you probably need induction to do, but see next point). If we're very strict, the word "finite" does not appear in the ZFC axioms at all, so you may need to define it and prove various other things about it as well.
3. None of the axioms guarantee that all finite subsets of the natural numbers (of whatever size) have a least element, and I don't believe you can prove that fact without using induction in some form. You can prove a bounded form of this (i.e. if you pick some number $k$, then you can prove that all finite sets of at most $k$ elements have a least element), but your proof needs the unbounded form to find $m \in \{0, 1, \dots, n\} \cap S$ (because you don't know the value of $n$ in advance).