Well ordering principle for rationals

Question

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.

Answer 1

Your claim isn't true.

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.

Answer 2

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.

Answer 3

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)

Answer 4

$\newcommand{\naturalset}{\mathbb{N}}$ $\newcommand{\realset}{\mathbb{R}}$ $\newcommand{\rationalset}{\mathbb{Q}}$ $\newcommand{\integerset}{\mathbb{Z}}$ $\newcommand{\inv}[1]{{#1}^{-1}}$ $\newcommand{\powerset}[1]{\mathcal{P}\left(#1\right)}$ $\newcommand{\addprime}[1]{{#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.