Baby Rudin Theorem 1.20 (b) Proof

Question

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$?

Answer 1

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.

Answer 2

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.

Answer 3

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} $$

Answer 4

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.