Direct proof of Archimedean Property (not by contradiction)

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?

• How are you defining the real numbers? If you define them via Cauchy completion of the rationals, then then Archimedean property comes along from the rationals almost for free, and it is fairly simple to prove the property directly in $\mathbb{Q}$. If you define the reals via Dedekind cuts then, again, you get the Archimedean property almost directly from $\mathbb{Q}$. On the other hand, if you define the reals axiomatically, then contradiction is the usual approach, since you are ultimately using the least upper bound property to get things done. Feb 16, 2019 at 17:24
• I'm defining them axiomatically. Feb 16, 2019 at 17:45
• My own proof of the stronger theorem of existence of floor/ceil was direct (essentially Nate's), so I have no idea why everyone you cite uses a highly convoluted way by contradiction. I also want to add that judicious use of the supremum axiom as an oracle can likewise yield 'constructive' proofs of the intermediate value theorem for $f(a) ≤ c ≤ f(b)$ (a desired point is $\sup\{ x : x∈[a,b] ∧ ∀y∈[a,x] ( f(y) ≤ c ) \}$) and the extreme value theorem for $f$ on $[a,b]$ (a desired point is $\sup\{ x : x∈[a,b] ∧ ∀y∈[a,x] ( f(y) ≤ f(x) ) \}$) and Dini's theorem and so on... Feb 25, 2019 at 17:22

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.

• Well, $y/x$ is an upper bound for $A.$ $y$ is an upper bound, too, if $x\geq 1.$ Jul 4, 2021 at 17:53
• Why would $x \ge 1$? No point making special case when we will just have to address what occurs if $x < 1$ Jul 19, 2021 at 23:33

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

• I'm confused by this statement: "for any $0 < \epsilon < 1$, there exists $k \in A$ with $k > t-\epsilon$". Would not this statement force $t \in \mathbb{N}$ artificially? Because: If $\left( t \in \mathbb{R-N}\right) \geq k$, I can choose $\epsilon$ such that $\left( t-\epsilon \in \mathbb{R-N}\right) \geq k$. So, $\nexists k \in A$ with $k>t-\epsilon$ because $k\leq t=\sup A$ and $k \in \mathbb{N}$. A numerical example: if $t=\sup A=2,7$ and $\epsilon=0,1$, then $t-\epsilon=2,6$. So $\nexists k \in A \ | \ 2,6<k\leq 2,7$ Feb 16, 2019 at 19:21
• @ViniciusACP: Well, that statement is a direct consequence of the definition of supremum. It certainly does imply that $t \in \mathbb{N}$, as I showed, and in fact the $k \in A$ with $k > t - \epsilon$ turns out to be $k=t$ itself. I don't know what you mean by "artificially". Your argument mostly works too, but one needs another line to show that there couldn't be another $k' \in A$, different from $k$, between $t$ and $t-\epsilon$ for your smaller $\epsilon$. Feb 16, 2019 at 21:09
• I understood now, thanks! By the way, I used it "artificially" because I was not realizing where that statement came from, so it seemed to me that it was introduced to "make the proof work." Now I get it. I was wrong. Thanks for your help! Feb 16, 2019 at 21:50
• Hi there, sorry I think @ViniciusACP is actually correct that your proof isn't constructive because you've treated the notions of "least upper bound" and "supremum" as being equivalent, when in fact they are (constructively speaking) not equivalent. In particular, it cannot be constructively shown that every least upper bound is a supremum - see section 4 of ncatlab.org/nlab/show/join. So this proof doesn't work, I don't think. Feb 26, 2020 at 14:50
• @asldjk: I interpreted the question as just looking to avoid contradiction from a stylistic standpoint. If one really wants a constructive proof then I have no doubt that things get much more subtle; for starters we have to be much more careful with definitions and axioms. Feb 26, 2020 at 14:55

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

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.

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

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