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?
Best Answer
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.