7
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\begingroup$ Possibly useful $\endgroup$ – Michael Lee Oct 9 '17 at 15:52
  • $\begingroup$ @MichaelLee It is definitely useful :), thanks. $\endgroup$ – onurcanbektas Oct 9 '17 at 15:57
  • 2
    $\begingroup$ 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! $\endgroup$ – Theo Bendit Oct 9 '17 at 15:58
  • $\begingroup$ Consider (2') Every monotonic Cauchy sequence converges. $\endgroup$ – anomaly Oct 11 '17 at 6:28
  • $\begingroup$ @anomaly and your point is ... ? $\endgroup$ – onurcanbektas Oct 11 '17 at 6:31
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – onurcanbektas Oct 13 '17 at 15:20
  • $\begingroup$ @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. $\endgroup$ – Paramanand Singh Oct 13 '17 at 16:27
  • $\begingroup$ Do you mean $B = \{x | s \in S, s < x \}$ ? $\endgroup$ – onurcanbektas Oct 13 '17 at 16:50
  • $\begingroup$ 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 )" $\endgroup$ – onurcanbektas Oct 13 '17 at 17:04
  • $\begingroup$ @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$. $\endgroup$ – Paramanand Singh Oct 13 '17 at 17:33
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What if the set of all upper bounds of $A$ is an uncountable set, then can we still pick the minimum element of it ? $\endgroup$ – onurcanbektas Oct 11 '17 at 5:21
  • $\begingroup$ I have deleted my comment, I realised the problem in my argument. $\endgroup$ – onurcanbektas Oct 11 '17 at 7:14
  • $\begingroup$ 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)} $ $\endgroup$ – onurcanbektas Oct 11 '17 at 7:20
  • $\begingroup$ Correction: it should be $z_n - z_{n+1}$. (As a explanation), how can we assure ourselves that $2k_n - k_{n+1} < 1$ ? $\endgroup$ – onurcanbektas Oct 11 '17 at 10:39
  • $\begingroup$ 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. $\endgroup$ – onurcanbektas Oct 11 '17 at 15:28

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.