1
$\begingroup$

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 proof this theorem directly, without using proof by contradiction?

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Xander Henderson Feb 16 at 17:24
  • $\begingroup$ I'm defining them axiomatically. $\endgroup$ – Vinicius ACP Feb 16 at 17:45
  • $\begingroup$ 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... $\endgroup$ – user21820 Feb 25 at 17:22
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – Vinicius ACP Feb 16 at 19:21
  • $\begingroup$ @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$. $\endgroup$ – Nate Eldredge Feb 16 at 21:09
  • $\begingroup$ 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! $\endgroup$ – Vinicius ACP Feb 16 at 21:50
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.