Well-ordering Principle Equivalent to Discreteness of Integers? The Well-Ordering Principle/Axiom for $\mathbb{Z}$ states that every nonempty subset of $\mathbb{Z}^+$ has a minimal element. From this it is easy to show that there do not exist any $n$ such that $0 < n < 1$, and consequently no $n$ with $k < n < k+1$ for all $n$, so that $\mathbb{Z}$ is "discrete." 
My question is: what about the converse? Assuming we have an ordered ring with no $n$ such that $k < n < k+1$ for all $k = k\cdot 1$, must the given ordering be a well-ordering? (Nonempty subsets of the positive set defined by the ordering have a minimal element.) I think I've heard the answer is no, as there exists a model of an ordered ring satisfying this criteria without being well-ordered, but I cannot think of one. If anyone has an answer/proof on this matter, I'd like to see it. Thanks.
 A: A simple explicit counterexample is the ring $\mathbb{Z}[x]$, ordered such that $x$ is infinitely large.  Explicitly, the ordering is defined by saying a polynomial is positive iff its leading coefficient is positive, and $p(x)>q(x)$ iff $p(x)-q(x)$ is positive.  The positive elements of this ordered ring are not well-ordered because the set $\{x-n:n\in\mathbb{Z}\}$ has no least element.
A: The answer is no: by e.g. the Compactness Theorem, there are ordered rings satisfying $x\le y<x+1\implies y=x$ but whose positive elements are not well-ordered. (Proof: Let $T$ be the first-order theory, in the language of ordered rings together with a new constant symbol $c$, consisting of the ordered ring axioms, the discreteness axiom above, and the additional axioms


*

*$c>0$

*$c-1>0$

*$c-1-1>0$

*...
Since every finite subset of $T$ has a model - an expansion of $\mathbb{Z}$, with $c$ interpreted as an appropriately large natural number - all of $T$ has a model. But the reduct of this model to the theory of rings does not have a well-ordered set of positive elements.)
What's really going on here is that "well-orderedness" is extremely complicated property, well beyond the ability of first-order logic to capture. This can be made precise in a number of ways. One particularly nice approach is via descriptive set theory. There is a natural topology on the set of (say) linear orderings with domain $\mathbb{N}$; this space is in fact a Polish space. For any first-order theory of linear orders $T$, the subset of this space consisting of models of that theory is Borel - in fact, $\Sigma^0_\omega$. By contrast, the set of well-ordered relations is coanalytic - much, much worse than Borel!

Natural examples of such rings are somewhat hard to come by, but do exist: see e.g. https://mathoverflow.net/questions/21367/proof-that-pi-is-transcendental-that-doesnt-use-the-infinitude-of-primes/21389#21389. EDIT: Or Eric's answer, which is much simpler :P.
