Direct proof of Archimedean Property (not by contradiction)

Question

I looked at the proof of Archimedean Property in several places and, in all of them, it is proven using the following structure (proof by contradiction), without much variation:

If $\space x \in \mathbb{R} \space,\space y \in \mathbb{R},$ and $x > 0$, then there is at least one natural number $n$ such that $nx > y$. $\bf{(*)}$

Proof:
Let $A$ be the set of all $nx$, where $n$ runs through the positive integers. $$A=\left\{nx \space| \space n \in \mathbb{N}\right\}$$ If $\bf{(*)}$ were false, which is equivalent to suppose that: $$nx \leq y, \space \forall n \in \mathbb{N}$$ then $y$ would be an upper bound of $A$. But then $A$ has a least upper bound in $\mathbb{R}$. Put $\alpha = \sup A$. Since $x > 0$, $\alpha - x < \alpha$, and $\alpha - x$ is not an upper bound of $A$. Hence $\alpha - x < mx$ for some positive integer $m$. But then $\alpha < (m+1)x \in A$, which is impossible, since $\alpha$ is an upper bound of $A$. Then, by contradiction, there exist an natural number n such that $nx > y$. $\tag*{$\blacksquare$}$

---

The following is a bit of what I found. All of these sources prove the property by contradiction:

Basic Real Analysis - Howland

Mathematical Analysis - Browder

A First Course in Analysis - Donald Yau

Principles of Mathematical Analysis - Rudin

A Course in Calculus and Real Analysis - Ghorpade & Limaye

Elementary Real Analysis - Thomson, J. Bruckner & A. Bruckner

---

So, my question is: How to prove this theorem directly, without using proof by contradiction?

Answer 1

We can modify the proof to be a direct proof by defining $A$ as

$A = \{nx|n \in \mathbb N, nx \le y\}$.

Then we don't need say the contradiction is equivalent to this being unbounded; we can simply note that $y$ is an upper bound of $A$. However we have to consider if $A$ is empty. (which could happen if $y < x$.)

If $A$ is empty we are done. For any natural $n$ then $nx \not \in A$ so $nx > y$.

If $A$ is not empty .... then the proof continues as it was given.

($A$ has a $a = \sup A$ and $a-x$ is not an upper bound so there exists an $mx$ so that $a-x < mx \le a$ so $(m+1)x > a =\sup A $. No need to say "But that's impossible" as we made no contrary assumption to begin with. Instead we point out so $(m+1)x \not \in A$ so $(m+1) x > y$.)

The contradiction was unnecessary. But I think it may have been to ease the student into just how broad and powerful the least upper bound property actually is.

Answer 2

I think I can patch up Surb's idea (now deleted).

For simplicity, assume $y \ge 0$. Let $A = \{k \in \mathbb{N} : k \le y/x\}$. This set is bounded above by construction, and it is nonempty since $0 \in A$, so it has a least upper bound; call it $t$. If we can show $t$ is a natural number, then $n=t+1$ is the desired natural number.

Since $t = \sup A$, there exists $k_0 \in A$ with $t-1 < k_0 \le t$. Note that $k_0 \in \mathbb{N}$. Also, by definition of supremum, for any $0 < \epsilon < 1$ there exists $k \in A$ with $k > t-\epsilon$. However, then $|k-k_0| < 1$, and $k, k_0$ are both natural numbers, so $k=k_0$. Thus $k_0 > t-\epsilon$. As this is true for every $\epsilon > 0$, we must have $k_0 \ge t$. Hence $t = k_0$ and so $t \in \mathbb{N}$.

Answer 3

A constructive proof would use a Cauchy sequence of rational numbers (or a Dedekind cut of the rationals, depending on how you define the reals.)

We’ll prove there is a natural $p>y$ for any real $y.$

Given a Cauchy sequence of rationals, $(c_k)_{k=1}^\infty=\left(\frac{a_k}{b_k}\right)_{k=1}^\infty,$ with $a_k,b_k$ integers and $b_k$ positive.

Use division algorithm to find integers $q_k,r_k$ with $0\leq r_k<b_k$ and $a_k=b_kq_k +r_k.$

Then, using that $(c_k)$ is Cauchy, let $\epsilon=1.$ Then let $N$ be such that $|c_n-c_m|<1$ for all $m,n\geq N.$(*) Then for $n\geq N,$

$$c_n<c_N+1=q_N+1+\frac{r_N}{b_N}<q_N+2.$$

We take $p=\max(q_N+2,0).$

---

(*) Note, this step is not constructive unless the sequence $(c_k)$ is “constructively Cauchy.” But that would be implicit - a Cauchy sequence in constructive math is implicitly one for which we don’t merely assert $N$ exists, but have a known way of finding $N$ given $\epsilon.$

There is nothing really different in the $x,y$ general case, except you need to show in constructive reals that if $x>0$ then the quotient of the two constructive Cauchy sequences is a constructive Cauchy sequence. That’s really an orthogonal argument. You also need to know that $x>0$ constructively - you need to know when the sequence for $x$ becomes bounded away from zero, and by what bound.

Answer 4

For fun I thought up the following convoluted argument. I am not an expert, but more of a laymen in this area trying to string together a proof for this cool theorem.

Lemma 1 For all reals $b$, there is a largest integer $n$ such that $n \leq b$.

Proof: Suppose not. Then for all $n$ we have $n < b$, in which case $$ \int_{0}^\infty 1_{\leq b}(t) - 1_{\leq n}(t) \mathrm{d}t >0 $$ for all integer $n$. However, if $n\leq b$, then the above equals $b-n$. The limit of this as $n\to \infty$ is clearly $-\infty$ which contradicts the above displayed inequality. $\square$

Lemma 2 Every interval $(a,b]$ of length at least $1$ contains an integer.

Proof: Let $I$ be $(a,b]$ where $b-a\geq 1$ and $a \geq 0$. Suppose that this interval contains no integer. Let $n$ be the largest integer not exceeding $b$. We have actually that $n+1>b$, as $b$ is not an integer. As $I$ contains no integer, $n \leq a$. But then $1\leq b-a < n+1 - n =1$. This is a contradiction. $ \square$

Lemma 3 For integer $m>0$, let $x\in (0, m]$ and $y$ be reals. Then there exists an integer $n$ such that $nx > y$.

Proof: Suppose first that $m=1$. If $y \leq 0$ then $n=1$ suffices, as $x >0 \geq y$. So suppose that $y > 0$. Let $$f (t) = xt.$$ This function is monotonically increasing in $t$ and satisfies $f(t+\delta) = f(t) + x\delta $. Now, $$f(y/x) = y $$ As $x\in (0,1]$, we have $1/x \geq 1$, so that there is an integer $n\in (y/x, y/x + 1/x]$ satisfying $$ nx = f(n) = f(y/x + (n- y/x)) = y + f(n-y/x) > y. $$

For the induction step, suppose that the result holds for some $m \geq 1$, and let $x\in (m+1,m]$. By induction, there is an integer $n$ such that $n(x-1) > y$, but then $nx > y + x > y$. $\square$

Answer 5

We know that $1 \in \mathbb{N}$ and $1 \in \mathbb{R}$.

Thus, if $x \leq 1$ then $n_x = 1$ and we are done.

Now assume, $x > 1$. Let M = $\{k \in \mathbb{N} : k < x\}$. Then $1 \in M$.

Thus, $M\neq \varnothing$ and is bounded above by $x$.

By the completeness property, we can then infer that sup$M$ exists. If we let $u = \text{sup}M -1 $ then we know that $\exists k \in M$ such that $k > u$.

$\therefore\text{sup}M < k + 1$, which is a natural number by the inductive property of natural numbers.

Since, $k + 1 > \text{sup}M$, we have that $k + 1 \not \in M$. By setting $n_x = k + 1$, we have proved the Archimedean Property. $\square$