Baby Rudin Theorem 1.20 (b) Proof

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.

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.