How to prove that the both definition of completeness of $\mathbb{R}$ are equivalent?

Question

In the definition of completeness of a set, in particular $\mathbb{R}$, I have seen the following definitions:

1. Dedekind: Every non-empty bounded of subset has a least upper bound (with respect to the natural order).
2. Cauchy: Every Cauchy sequence converges.

However, how can one prove that both of these definitions are equivalent ?

Answer 1

You can try to add another step in between which is the famous

Bolzano-Weierstrass Theorem: Every infinite bounded set has an accumulation point.

And then prove them in cyclic fashion : Dedekind implies Bolzano implies Cauchy implies Dedekind. The first step can be completed by starting with an infinite bounded set $S$ and another set $$A=\{x\mid x\in\mathbb{R}, x\text{ exceeds only a finite number of members of }S \} $$ (note that $0$ is also "a finite number" so that $x\in A$ if $x$ does not exceed any member of $S$).

Then $A$ is bounded above (any upper bound of $S$ is also an upper bound of $A$) and $M=\sup A$ exists according to Dedekind's version of completeness. Consider the interval $(M-\epsilon, M+\epsilon) $ for any arbitrary $\epsilon>0$. There is a member $a\in A$ such that $a>M-\epsilon$ and hence only a finite number of members of $S$ are less than $a$. On the other hand since $M+\epsilon$ is not in $A$ so there are an infinite number of members of $S$ which are less than $M+\epsilon$ and out of these only a finite number are less than $a$. It follows that there are infinitely many members of $S$ in $(M-\epsilon, M+\epsilon)$. Thus $M$ is an accumulation point of $S$.

---

Next we establish Bolzano-Weierstrass implies Cauchy. Let $\{x_{n}\} $ be a Cauchy sequence then it is bounded. And if the sequence takes only a finite number of values it is easy to see that it becomes constant after a certain point and converges to the same constant. So let the range of the sequence $\{x_{n} \}$ be infinite. Then by Bolzano-Weierstrass the sequence has an accumulation point $x$. We show that $x_{n} \to x$ as $n\to\infty$. Let $\epsilon>0$ be arbitrary. There is a positive integer $N$ such that $|x_{m}-x_{n} |<\epsilon /2$ whenever both $m, n$ exceed $N$. And since $x$ is an accumulation point of the sequence $\{x_{n} \} $ it follows that there is a value of $m>N$ such that $|x_{m} - x|<\epsilon/2$. Therefore we have $$|x_{n} - x|\leq|x_{n} - x_{m} |+|x_{m} - x|<\epsilon $$ for all $n>N$ and this means that $x_{n} \to x$ as $n\to\infty$.

---

Finally we establish that Cauchy implies Dedekind. Let $S$ be a non-empty set bounded above and $K$ be an upper bound for $S$. Let $a\in S$. We construct sequences $x_{n}, y_{n} $ in the following manner. Let $x_{1}=a, y_{1}=K$. If $(x_{n}+y_{n})/2$ is an upper bound for $S$ then $$x_{n+1}=x_{n},y_{n+1}=\frac{x_{n}+y_{n}} {2} $$ otherwise $$x_{n+1}=\frac{x_{n}+y_{n}} {2} ,y_{n+1}=y_{n}$$ This way the sequences are obtained in a recursive manner. It should be clear from the above construction that for every $n$ there is some member $s\in S$ (depending on $n$) such that $x_{n} \leq s$ and $y_{n}$ is an upper bound for $S$ for all values of $n$. Further it is clear that $x_{n}$ is non-decreasing and $y_{n} $ is non-increasing and $$x_{n} \leq y_{n}, y_{n} - x_{n} =\frac{y_{1}-x_{1}} {2^{n-1}} $$ Clearly this also implies that $|x_{n+1}-x_{n}|\leq (y_{1}-x_{1})/2^{n-1}$. It is easily proved that $x_{n} $ is a Cauchy sequence and let's say it converges to $x$. By the given relations between $x_{n}, y_{n} $ it follows that $y_{n}$ also converges to $x$.

We show that $x=\sup S$. Since $y_{n} $ is an upper bound for $S$ it follows that $y_{n} \geq s$ for any $s\in S$. It follows by taking limits that $x\geq s$ and hence $x$ is also an upper bound for $S$. Since $x_{n} \to x$ it follows that for any $\epsilon>0$ there is some $x_{n} >x-\epsilon$. And by construction there is an element $s\in S$ such that $s\geq x_{n} $. Thus $s>x-\epsilon$ and therefore $x=\sup S$.

---

You may also try to prove equivalence of these formulations of completeness to gain better understanding.

Answer 2

Proof of $(2)\Rightarrow(1)$: Let a nonempty bounded $A\subset{\mathbb R}$ be given. Then there is an $a\in A$ and an $M\in{\mathbb Z}$ with $M\geq x$ for all $x\in A$. This $M$ is an upper bound of $A$, and no $s<a$ is an upper bound of $A$. Define a sequence $(z_n)_{n\geq0}$ as follows:

$$z_n:=\min\left\{k\cdot2^{-n}\>\biggm|\>k\in{\mathbb Z}, \ k\cdot2^{-n}{\rm\ is\ an\ upper\ bound\ of\ }A\right\}\qquad(n\geq0)\ .$$ If $z_n=k_n\cdot2^{-n}$ then $(k_n-1)\cdot2^{-n}$ is no longer an upper bound of $A$. It follows that either $z_{n+1}=z_n$ or $z_{n+1}=z_n-2^{-(n+1)}$, hence $|z_n-z_{n+1}|\leq 2^{-(n+1)}$. By the triangle inequality this implies $$|z_m-z_n|<2^{-n}\qquad(m\geq n\geq0)\ .$$ Therefore $(z_n)_{n\geq0}$ is a Cauchy sequence in ${\mathbb R}$, and by assumption converges to a point $\xi\in{\mathbb R}$.

I claim that $\sup A=\xi$.

Proof. If there is an $a\in A$ with $a>\xi$ then there is an $n$ with $\xi<z_n<a$, contrary to the definition of $z_n$. It follows that $\xi$ is an upper bound of $A$. If there is a smaller upper bound $\sigma$ of $A$ then there is a binary rational $b=k\cdot2^{-n}$ with $\sigma<b<\xi\leq z_n$, again contradicting the definition of $z_n$. It follows that $\xi$ is in fact the smallest upper bound of $A$.$\quad\square$

Proof of $(1)\Rightarrow(2)$: From $(1)$ it immediately follows that monotone bounded real sequences are convergent.

Let a Cauchy sequence $(x_k)_{k\geq0}$ in ${\mathbb R}$ be given. It is well known that such a sequence is bounded. Define the numbers $$a_n:=\inf_{k\geq n}x_k,\quad b_n:=\sup_{k\geq n}x_k\qquad(n\geq0)\ .$$ Then $a_n\leq b_n$ for all $n$, the $a_n$ form a bounded increasing sequence with $\lim_{n\to\infty}a_n=\alpha$, and the $b_n$ form a bounded decreasing sequence with $\lim_{n\to\infty}b_n=\beta\geq\alpha$.

Let an $\epsilon>0$ be given. Then there is an $n$ with $x_l-x_k\leq \epsilon$ for all $k$, $l\geq n$. It follows that $$\beta-\alpha\leq b_n-a_n=\sup_{l\geq n}x_l-\inf_{k\geq n} x_k=\sup_{k,\>l\geq n}(x_l-x_k)\leq\epsilon\ .$$Since $\epsilon>0$ was arbitrary this implies that in fact $\alpha=\beta$. From $$a_n\leq x_k\leq b_n\qquad(k\geq n)$$ it then easily follows that $\lim_{k\to\infty} x_k=\alpha$ as well.$\quad\square$

(Of course these things are proven in most textbooks on real analysis.)