# Well ordering principle for rationals

Why can positive rationals be not well ordered? If we define the relation to be greater than(>), then every subset will have a least element. Or why are positive or even integers not well ordered? By the same logic we can always find a least element in any subset. I know I am wrong at some very fundamental point, but please explain it to me.

• Positive integers equipped with usual order are well ordered. Negative integers are not. E.g. the set $\{-n\mid n=1,2,3,\dots\}$ has no least element. Sep 21, 2018 at 7:52
• It dosen't make sense to talk about rationals in the context of the well ordered principle. It is the only the case that if $A \subseteq \mathbb{N} \wedge A \neq \emptyset \implies \exists m, m \leq a \forall a \in A$. Feb 5, 2022 at 22:32

The positive rationals can be well-ordered

Since $$\mathbb{Q}$$ bijects with $$\mathbb{N}$$, the well-ordering on $$\mathbb{N}$$ will induce a well-ordering on $$\mathbb{Q}$$ and hence on the positive rationals.

However,

The usual ordering of positive rationals is not a well-ordering

The usual ordering is, of course, $$\frac{a}{b}>\frac{c}{d}$$ if and only if $$ad>bc$$ (where $$a,b,c,d$$ are positive integers).

If it is a well-ordering, then there is a least positive rational $$p/q$$. But halving it gives a smaller positive rational $$p/(2q)$$, so $$p/q$$ can't be the least, contradiction.

• To clarify your last paragraph: the set of rationals $\{q\mid q\in\mathbb Q, q>0\}$ has no smallest element. Sep 21, 2018 at 7:37
• Please clarify if the subset is having fixed elements with least element p/q then how is p/2q the least when it was not in the subset initially , are you taking open interval , what about even integers Sep 21, 2018 at 7:39
• The even integers $2\mathbb{Z}$ under the usual ordering is not well-ordered. Indeed, the subset $\{m\in 2\mathbb{Z}:\text{$m$is negative}\}$ has no least element. That is to say, there is no even integer $m_0$ smaller than every element of the chosen subset. Oct 5, 2018 at 19:52
• @mathnormie You are correct in saying that if the number of elements in the set is finite, then the elements are well ordered. Dec 19, 2021 at 13:20
• @NeelSandell thanks for this explanation. I am also struggling to get the full argument because of the same doubt which @ mathnormie has. Maybe it is obvious to many others, but for people new to this material, it is not very obvious. I can come to terms to the statement that nonempty subset of nonnegative rationals are not always well ordered only if I consider set to be non finite. Jan 11, 2022 at 7:21

Positive integers are well ordered but positive rationals are not because for well ordered, every non empty subset must have least element( least element must belong to subset and there is difference between least element and greatest lower bound). There are many subsets which have no least point in positive rationals like the subset $${1, 1/2, 1/4, 1/8, 1/16, ...}$$ has no least element or the set of all positive rationals greater than any irrational number.

• In the example you mean that the subset was an open interval so we cannot find least element , what about positive integers Sep 21, 2018 at 7:17
• @mathnormie: Read the first five words in the answer again. Sep 21, 2018 at 8:05
• I meant even integers , my teacher say its not well ordered Sep 21, 2018 at 8:15
• @mathnormie "my teacher say" is neither a good argument nor helpful. Maybe you should post the definition used by your teacher and someone can point a mistake either on the definition or on the argument. Oct 5, 2018 at 16:26

As a supplement, the definition can be written as

1. Every nonempty set of nonnegative integers absolutely has a smallest element.

2. Some sets of nonnegative rationals do not have a smallese element. (note that we only say some sets do not posess this property)

$$\newcommand{\naturalset}{\mathbb{N}}$$ $$\newcommand{\realset}{\mathbb{R}}$$ $$\newcommand{\rationalset}{\mathbb{Q}}$$ $$\newcommand{\integerset}{\mathbb{Z}}$$ $$\newcommand{\inv}{{#1}^{-1}}$$ $$\newcommand{\powerset}{\mathcal{P}\left(#1\right)}$$ $$\newcommand{\addprime}{{#1}^{\prime}}$$

While $$\rationalset$$ is not well-ordered in the usual sense, it can be well-ordered by defining a strict total order from its relation to $$\naturalset$$. Below is a proof for existence of well-ordering for $$\rationalset$$.

As $$\rationalset$$ is countable, there exists a bijection $$f: \rationalset \to \naturalset$$. Then there exists a set $$R \in \powerset{\rationalset^{2}}$$ such that for any $$a, b \in \rationalset$$, $$a R b$$ if and only if $$f\left(a\right) < f\left(b\right)$$. We argue that this $$R$$ is a well-ordering for $$\rationalset$$. It is then our desire to prove the following properties:

(1) for any $$a \in \rationalset$$, $$\neg \left(a R a\right)$$;

(2) for any $$a, b, c \in \rationalset$$, if $$a R b$$ and $$b R c$$, then $$a R c$$;

(3) for any $$a, b \in \rationalset$$, if $$a R b$$, then $$\neg \left(b R a\right)$$;

(4) for any $$a, b \in \rationalset$$, it is either $$a R b$$ or $$b R a$$ or $$a = b$$.

(5) Suppose $$\addprime{R}$$ is defined by the following statement: for any $$x, y$$, $$x \addprime{R} y$$ if and only if $$x R y$$ or $$x = y$$. Then for any $$S \subseteq \rationalset$$, if $$S \neq \emptyset$$, then there exists an element $$a \in S$$ such that for any $$b \in S$$, $$a \addprime{R} b$$.

First, assume $$a \in \rationalset$$. Suppose that $$a R a$$. Then it is clear that $$f\left(a\right) < f\left(a\right)$$, which together with $$f\left(a\right) = f\left(a\right)$$. forms a contradiction. Then $$\neg\left(a R a\right)$$.

Next, assume that $$a, b, c \in \rationalset$$ and that $$a R b$$ and $$b R c$$. It is then clear that $$f\left(a\right) < f\left(b\right)$$ and $$f\left(b\right) < f\left(c\right)$$. Immediately, we have $$f\left(a\right) < f\left(c\right)$$, which leads to $$a R c$$.

Further, assume that $$a, b \in \rationalset$$ and that $$a R b$$. Further assume that $$b R a$$. Then we have $$f\left(a\right) < f\left(b\right)$$ and $$f\left(b\right) < f\left(a\right)$$, which leads to a contradiction. Then it is clear that $$\neg\left(b R a\right)$$.

One step further, assume that $$a, b \in \rationalset$$. It is clear that $$f\left(a\right) < f\left(b\right)$$ or $$f\left(b\right) < f\left(a\right)$$ or $$f\left(a\right) = f\left(b\right)$$. Assume $$f\left(a\right) = f\left(b\right)$$. Using the fact that $$f$$ is a bijection, it is clear that $$a = b$$. On the other hand, $$f\left(a\right) < f\left(b\right)$$ or $$f\left(b\right) < f\left(a\right)$$ leads to $$a R b$$ or $$b R a$$. Then it is clear that $$a R b$$ or $$b R a$$ or $$a = b$$.

Next we prove the following statement: for any $$x, y \in \rationalset$$, $$x \addprime{R} y$$ if and only if $$f\left(x\right) \leq f\left(y\right)$$. First assume that $$x \addprime{R} y$$. Then $$x R y$$ or $$x = y$$. Consequently $$f\left(x\right) \leq f\left(y\right)$$. Next, assume that $$f\left(x\right) \leq f\left(y\right)$$. It is also clear that $$x \addprime{R} y$$. Thus, we conclude that for any $$x, y \in \rationalset$$, $$x \addprime{R} y$$ if and only if $$f\left(x\right) \leq f\left(y\right)$$.

Lastly, assume $$S \subseteq \rationalset$$ and $$S \neq \emptyset$$. It is clear that $$f\left(S\right) \neq \emptyset$$. Then there exists an element $$x_{0} \in f\left(S\right)$$ such that for any $$y \in f\left(S\right)$$, $$x_{0} \leq y$$. As $$f$$ is a bijection, there exists some $$a_{0} \in \rationalset$$ such that $$a_{0} = \inv{f}\left(x_{0}\right)$$ and $$a_{0} \in S$$. Further, assume $$b_{0} \in S$$. Then $$b_{0} = \inv{f}\left(y_{0}\right)$$ for some $$y_{0} \in f\left(S\right)$$. As $$f\left(a_{0}\right) = x_{0}$$ and $$f\left(b_{0}\right) = y_{0}$$, $$f\left(a_{0}\right) \leq f\left(b_{0}\right)$$. Then $$a_{0} \addprime{R} b_{0}$$. Then we conclude that for any $$S \subseteq \rationalset$$, there exists some $$a \in S$$ such that for any $$b \in S$$, $$a \addprime{R} b$$.

From the above reasoning, $$R$$ is a well ordering for $$\rationalset$$, and we conclude that a well-ordering for $$\rationalset$$ exists.