# Baby Rudin Theorem 1.20 (b) Proof

I have a question about Rudin's proof of Theorem 1.20 (b) in his book Principles of Mathematical Analysis. Theorem 1.20 is stated as follows:

(a) If $x\in R, y\in R$, and $x>0$, then there is a positive integer $n$ such that $$nx>y.$$ (b) If $x\in R, y\in R$, and $x<y$, then there exists a $p\in Q$ such that $x<p<y$.

I understand Rudin's proof of (a). The beginning of Rudin's proof of (b) is given below:

Since $x<y$, we have $y-x>0$, and (a) furnishes a positive integer $n$ such that $$n(y-x)>1.$$ Apply (a) again, to obtain positive integers $m_1$ and $m_2$ such that $m_1>nx$, $m_2>-nx$. Then $$-m_2<nx<m_1.$$ Hence there is an integer $m$ (with $-m_2\leq m\leq m_1$) such that $$m-1\leq nx<m.$$

I don't understand the justification for this last sentence beginning "Hence...." How is $m$ found, and why are $m_1$ and $m_2$ needed to find $m$?

• @ThomasAndrews Thanks, I understand what you are saying. However, it is the last sentence beginning "Hence..." that I am having trouble understanding. Commented Aug 26, 2013 at 18:15
• Ah, should read the question :) Commented Aug 26, 2013 at 18:16
• The existence of $m$ can be ensured by well-ordering principle which Rudin didn't mention at all. So Rudin made use of the finiteness between $m_1$ and $-m_2$ to find $m$.
– Neo
Commented May 20, 2018 at 4:56

The integers $m_1$ and $m_2$ serve to bound $nx$ between two integers. The set $$=\{-m_2+1,-m_2+2,\ldots,m_1\}$$ is a finite set of integers, so we can choose the smallest member $m$ of this set such that $nx<m$.

If we knew that $nx$ was positive, we wouldn’t need $m_2$: we could just choose the smallest positive integer $m$ such that $nx<m$, since every non-empty set of positive integers has a least element. In fact, we can use that well-ordering principle directly, once we have $m_1$ and $m_2$. Let

$$M=\{m\in\Bbb Z^+:m-m_2>nx\}\;.$$

Then $M\ne\varnothing$, since $m_1+m_2\in M$, so $M$ has a least element, say $k$. Let $m=k-m_2$. Then $m>nx$. However, $k-1\notin M$, so $m-1=k-1-m_2\not>nx$, i.e., $m-1\le nx$. But note that I needed both $m_1$ and $m_2$ to carry out this argument: $m_1$ is needed to ensure that there is at least one integer that’s big enough to exceed $nx$, and $m_2$ is needed to ensure that not every integer is big enough.

• @BrianM.Scott Why doesn't the set begin with "-m_2"? Commented Oct 14, 2014 at 13:27
• @AlanH: Because $nx$ is bigger than $-m_2$, so there’s no point in looking at $-m_2$ for a number larger than $nx$. Commented Oct 14, 2014 at 19:47
• I'm sorry, there's something I don't understand: If $k$ is the least element in $M$, and $m=k-m_2>nx,m_2>0$, doesn't that mean that $m\in M$ and that $m<k$ contradicting the minimality of $k$? Perhaps you meant $m=k+m_2$? Commented Dec 23, 2015 at 22:36
• @YoTengoUnLCD: No: in order for $m$ to belong to $M$, we’d have to have $m-m_2>nx$, i.e., $k-2m_2>nx$. Commented Dec 23, 2015 at 22:42
• @BrianM.Scott We do know that $nx>0$ because Rudin specifies in the first part of the proof (i.e., proof of the Archimedean Property ) that $x>0$. So can we let $m_1=m$ as you describe it and let $m_2=m-p$ for some natural number $p<m$??? Commented Aug 28, 2017 at 0:47

This essentially requires either induction or the well-ordering property of the natural numbers.

Let $S=\{s\in \mathbb N:m_2+s>nx\}$.

We know that $m_1-m_2\in S$. So $S$ is a non-empty set of natural numbers. By the well-ordering principle, we know that there is an $s_0$ that is the least element of $S$.

You also know that $s_0\neq 0$, since $m_2+0=m_2\leq nx$.

Finally, we know that $s_0-1\in\mathbb N$ since $s_0\neq 0$ and $s_0\in\mathbb N$ (with $0\in \mathbb N$). Since $s_0$ was the least element of $S$, we know that $s_0-1\notin S$, so $m_2+s_0-1 \leq nx$. But this means that $m=m_2+s_0$ has the property that: $$m-1 \leq nx < m$$

Alternatively, you can prove by induction on $d$ the following theorem:

If $n\in\mathbb Z$, $d\in\mathbb Z^+$ and $y\in\mathbb R$ such that $n\leq y<n+d$ then there exists $m\in\mathbb Z$ such that $m-1\leq y < m$.

Proof:

If $d=1$ then $m=n+1$ suffices.

If true for $d$, we will prove it for $d+1$.

If $n\leq y\leq n+d+1$ then either $n\leq y <n+d$ or $n+d\leq y <n+d+1$. In the former case, we can find $m$ by induction, and in the latter case, we have $m=n+d+1$ is a solution.

If there were no such $$m$$, then $$-m_2 < nx < m_1$$ would be false, since all of the following propositions would be false:

\begin{align} -m_2 &\le nx < -m_2 + 1\\ -m_2 + 1 &\le nx < -m_2 + 2\\ &\quad\,\cdots\\ m_1 - 2 &\le nx < m_1 - 1\\ m_1 - 1 &\le nx < m_1 \end{align}

To reinforce previous answers, I think the only way to rigorously prove the "Hence..." statement is to assume the well-ordering property of the integers, despite what some other answers have given; see, e.g., this related post.

Rudin states on page 1 of his book that "We shall not, however, enter into any discussion of the axioms that govern the arithmetic of the integers, but assume familiarity with the rational numbers..." I take this to mean that everything familiar to us about the integers and natural numbers is fair game. The well-ordering property is logically equivalent to mathematical induction, and mathematical induction is derived from the basic axiomatic structure of the integers. So I take this to mean that the well-ordering property, i.e., that every nonempty set of positive integers contains a least element, can be assumed to be true.

From what I can tell, the main problem without assuming well-ordering is that while sets like $$S=\left\{m\in \mathbb{Z}_+: m-m_2>nx\right\}$$ have an infimum (by Theorem 1.11 and Theorem 1.19 in Baby Rudin), we do not know whether or not the infimum is an integer. Well-ordering takes care of this. So, in fact, the least upper bound property of $$\mathbb{R}$$ is not needed after "Hence..." Part (b) of that theorem really only uses part (a), properties of ordered fields, and well-ordering of the natural numbers.