Theorem 1.20 (b) in Baby Rudin: Can the proof of the theorem be improved?

Question

I'm reading Principles of Mathematical Analysis, third edition, and am at Theorem 1.20(b), which is as follows:

If $x \in \mathbb{R}$, $y \in \mathbb{R}$, and $x < y$, then there exists a $p \in \mathbb{Q}$ such that $x< p < y$.

Now here is the proof given by Rudin:

Since $x<y$, we have $y-x > 0$, and Theorem 1.20(a) furnishes a positive integer $n$ such that $$n(y-x) > 1.$$ Apply Theorem 1.20(a) again to obtain positive integers $m_1$ and $m_2$ such that $m_1 > nx$ and $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.$$ If we combine these inequalities, we obtain $$nx < m \leq 1+nx < ny.$$ Since $n > 0$, it follows that $$ x < \frac{m}{n} < y.$$ This proves Theorem 1.20(b) with $p = \frac{m}{n}$.

Now I have the following questions:

(1) In the above proof, can we not dispense with the integers $m_1$ and $m_2$?

(2) How do we know that the integer $m$ satisfies the inequalities $-m_2 \leq m \leq m_1$?

(3) As Rudin has not mentioned the well-ordering principle, how do we obtain the inequalities $ m-1 \leq nx < m$?

(4) Is this proof sound enough logically even without using the well-ordering principle?

Answer 1

I'm not sure whether Rudin was implicitly appealing to the well-ordering principle, but it is possible to interpret what he's written in a way that doesn't use it.

Namely, the set $S$ of integers that are $\leq nx$ is nonempty, by the existence of $-m_2$, which belongs to the set, and bounded above, by the existence of $m_1$, which is an upper bound for it, and does not belong to it. Therefore $S$ must have a least upper bound $p$. $p$ must belong to $S$, for otherwise $S$ would have to have two elements strictly between $p-1$ and $p$, which is impossible since the elements of $S$ are integers. Then let $m = p+1$.

The inequality $-m_2 \leq m$ follows from the fact that $p = m-1$ is the largest element of $S$, and $-m_2 \in S$. The inequality $m \leq m_1$ results from $m-1 = p \leq nx < m_1$. And the inequalities $m-1 \leq nx < m$ or, equivalently, $p \leq nx < p+1$, are a consequence of the fact that $p$ is the largest element of $S$.

I would say that this proof uses a number of unstated assumptions about the integers, their basic properties, and their relationship to the real numbers (for example, the fact that the order relation is the same, or the fact that a successor integer is obtained by adding $1$ in $\mathbf{R}$). This is unavoidable, because the integers haven't been defined. However, it does not appear that an appeal to the well-ordering principle is necessary. The proof is logically deficient only to the extent that the integers are assumed to have these unstated properties.

I don't believe the proof can be substantially improved without formalizing what the integers are, perhaps defined as a subset of $\mathbf{R}$ with certain properties, if one wishes to retain the axioms for $\mathbf{R}$ as the basis for the exposition.

Answer 2

--> In the above proof, can we not dispense with the integers $m_1$ and $m_2$?

Yes. You can dispense with the integers $m_1$ and $m_2$, using the Lemma 1.

Lemma 1. For every real number $x$ there is exactly one integer $N$ such that $N \le x < N + 1$. (This integer $N$ is called the integer part of $x$, and is sometimes denoted $N = \lfloor x \rfloor$.)

Lemma 2. For any positive real number $x > 0$ there exists a positive integer $N$ such that $0 < 1/N < x$.

We now show

Proposition 3. Given any two real numbers $x < y$, we can find a rational number $q$ such that $x < q < y$.

By hypothesis, we have $y -x$ is positive. So exists a positive integer $N$ such that $0 < 1/N < y - x$, by Lemma 2. Since $xN$ is a real number, by Lemma 1, there exists a integer $n$ such that $n - 1 \le xN < n$, i.e., $n/N - 1/N \le x$ and $x < n/N$. Thus $x < n/N \le x + 1/N$. Since $1/N \le y - x$, i.e., $x + 1/N < y$, we have $x < n/N < y$. Thus $n/N$ is rational, the claim follows.

--> How do we know that the integer m satisfies the inequalities $−m_2 \le m \le m_1$?

Because of $m_1, m_2$ are positive integers, we have $−m_1 < 0 < m_2$. If we add $M := m_1 - m_2$ to both sides, we obtain $-m_2 < M < m_1$. So $M$ is a integer between $-m_2$ and $m_1$. Thus you can conclude $-m_2 \le M \le m_1$. (Clearly, the equality can not be, but it is similar to: if $P$ is true, then $(P \text{ or anything})$ is true.)

--> As Rudin has not mentioned the well-ordering principle, how do we obtain the inequalities $m−1\le nx < m$?

There are many proofs about Lemma 1. You can see one of them here. Also there exists a proof that does not use the well-ordering.

--> Is this proof sound enough logically even without using the well-ordering principle?

Is possible to prove the Lemma 1 without the well-ordering, by contradiction, or maybe using the induction principle.

Answer 3

Basically this proof is a consequence of several successive applications of the Archimedian property. There's a slightly shorter but equivalent proof that's a little less confusing then Rudin's and it's done in 2 steps.

The first step is we have to prove if a is a real number, then there exists an integer N such that N − 1 ≤ a < N. The proof is by direct construction as follows: Let S = {n ∈ Z | n > a}. Then by the Archimedean property,S is nonempty. The set S is bounded below by a, so by the well-ordering principle,S has a least element N. Then N − 1 is not an element of S. So N-1 < a < N.

2 important observations that answers 2 of your questions: This basically gives us the result Rudin derives at the beginning, but in a little clearer manner. And it answers your question,no,we really can't dispense with this step because the main result depends on it, as you'll see. It also shows you really need the well ordering principle to derive the intermediate inequalities. Rudin tends to use a lot of "toolkit" results like the WOP without statement-it's one of the reasons he gets away with being so annoyingly concise.

Now we're ready to prove the main result. From the Archimedean property of R there exists q ∈ N such that 1/q < b−a. Now consider the real number qa. There exists an integer p such that p − 1 ≤ qa < p. It follows that (p−1/q) ≤ a < p/q . This gives that p/q − 1/q ≤ a, which gives that a < p/q ≤ a + 1/q < b. That completes the proof.

As I said, it's equivalent and not radically different from Rudin's, but I personally found it a little shorter and a bit easier to follow.