Gallian: is it true that the well-ordering principle can't be proven from properties of arithmetic? 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?

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.
