Gallian: is it true that the well-ordering principle can't be proven from properties of arithmetic?

Question

I just started reading Gallian's Abstract algebra and on page 3 it says "An important property of the integers...is the so-called Well Ordering Principle. Since this property cannot be proved from the usual properties of arithmetic, we will take it as an axiom". [my emphasis]

My question is, how can one (in this case the author) be so sure that the Well Ordering Principle cannot be proved from the properties of arithmetic. Is it possible to prove statements like this (i.e. the one in italics above). If so, what would a proof look like?

Answer 1

Of course the well-ordering principle can be proved for the natural numbers in standard set theory, and you can find a proof with google.

If so, what would a proof look like?

Usually one uses set theory to prove induction, and then induction to prove well-ordering of $\Bbb N$.

I guess it depends on what the "properties of arithmetic" are that he refers to. If they are just the ring axioms for $\Bbb Z$, then yeah, that is not enough to prove well ordering of $\Bbb N$. Maybe Gallian just doesn't want to go so far afield into set theory, so he takes it as an axiom.

Answer 2

We can prove the well-ordering property if we assume the principle of induction (and similarly we can prove the principle of induction if we assume the well-ordering property). For a proof, let $A\subset\mathbb{N}$, and suppose it has no least element. Let $B$ be the set of all natural numbers $n$ such that $1,\dots,n\not\in A$. Then clearly $1\in B$ (because if $1$ were in $A$, $1$ would be the smallest element of $A$). Moreover, if $1,\dots,k\not\in A$, surely $k+1\not\in A$ (otherwise $k+1$ would be the smallest element of $A$), so $1,\dots,k+1\not\in A$. In other words, if $k\in B$ then $k+1\in B$. By induction we have $n\in B$ for all $n\in\mathbb{N}$, hence $A=\emptyset$, completing the proof.