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

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 ?

• Possibly useful – Michael Lee Oct 9 '17 at 15:52
• @MichaelLee It is definitely useful :), thanks. – onurcanbektas Oct 9 '17 at 15:57
• If I remember correctly, the real numbers are both the unique Cauchy-complete, Archimedean ordered field, and the unique Dedekind-complete ordered field. The additional assumption of Archimedean is necessary to add to Cauchy completeness in order to uniquely specify the real numbers, and obtain Dedekind completeness. But I could be mis-remembering! – Theo Bendit Oct 9 '17 at 15:58
• Consider (2') Every monotonic Cauchy sequence converges. – anomaly Oct 11 '17 at 6:28
• @anomaly and your point is ... ? – onurcanbektas Oct 11 '17 at 6:31

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.

• What exactly do you mean by "$x$ exceeds only a finite number of members of $S$" ? I mean do you mean for any element of S ? or for the maximal element ? etc. – onurcanbektas Oct 13 '17 at 15:20
• @onurcanbektas: the sentence is self explanatory as far the English wording is concerned, but in case you want to be formal it means that the set $$B = \{s\mid s \in S, s < x\}$$ is a finite set and it may be empty also. – Paramanand Singh Oct 13 '17 at 16:27
• Do you mean $B = \{x | s \in S, s < x \}$ ? – onurcanbektas Oct 13 '17 at 16:50
• But then every upper bound of $S$ does not have to be an upper bound of $A$, in this case $B$. Of course, $A$ will be bounded above but for the time being, I'm just pointing out the problematic part in the sentence "Then A is bounded above (any upper bound of S is also an upper bound of A )" – onurcanbektas Oct 13 '17 at 17:04
• @onurcanbektas: the set $B$ is used only to explain the statement "$x$ exceeds only a finite number of members of $S$". It does not have use in the proof. And my comment about $B$ is correct without typo. If $K$ is an upper bound for $S$ and suppose $a\in A$ exists such that $a>K$. Then $a$ is upper bound for $S$ and hence exceeds all the infinite number of members of $S$ which contradicts $a\in A$. Hence we must have $a\leq K$ and thus $K$ is an upper bound for $A$. – Paramanand Singh Oct 13 '17 at 17:33

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

• What if the set of all upper bounds of $A$ is an uncountable set, then can we still pick the minimum element of it ? – onurcanbektas Oct 11 '17 at 5:21
• I have deleted my comment, I realised the problem in my argument. – onurcanbektas Oct 11 '17 at 7:14
• I'm having trouble to understand why $0\leq z_n-z_{n+1}\leq 2^{-(n+1)}$. I mean if we say $z_n = k_n 2^{-n}$, then $z_n - z_{n-1} = (2 k_n - k_{n+1}) 2^{-(n+1)}$ – onurcanbektas Oct 11 '17 at 7:20
• Correction: it should be $z_n - z_{n+1}$. (As a explanation), how can we assure ourselves that $2k_n - k_{n+1} < 1$ ? – onurcanbektas Oct 11 '17 at 10:39
• After 8 hours, I still don't get it why $$0\leq z_n-z_{n+1}\leq 2^{-(n+1)}$$. I mean it is just algebra, but I don't see the result. – onurcanbektas Oct 11 '17 at 15:28