Proving Completeness property of ##\mathbb{R}## using Dedekind cuts

[issacnewton]

Homework Statement

Suppose that the non-empty subset $A$ of $\mathbb{R}$ is bounded above. Then $A$
has a least upper bound in $\mathbb{R}$ i.e. lub $A$ exists.

Relevant Equations

definition of Dedekind cut

So, I have to come up with some set which is lub A. Now, A is a subset of R, so each member of A is a Dedekind left set. So, A is a set of sets. Now, I propose that the following set would be lub of $A$.

$$ \alpha = \bigcup A = \{ \beta | \exists \delta \in A (\beta \in \delta) \} $$

Actually, I have proven most of it. I am at the part, where I am trying to prove that $\alpha$ is a real number. So, for that, I will need to prove that, $\alpha$ is a Dedekind left set. So, I need to prove that $\alpha \ne \mathbb{Q}$. Which means that, there exists some $x \in \mathbb{Q}$ such that $x \notin \alpha$. This is what I need to prove. Now, I am given that $A$ is bounded above, so there is some $M \in \mathbb{R}$, such that

$$ \forall \; x \in A \; (x \leqslant M) \cdots\cdots (1) $$

Now, $M < M+1$. There is some $y \in \mathbb{Q}$ such that $M < y < M + 1$. So, it means that

$$ \forall \; x \in A \; (x < y) \cdots\cdots (2 )$$

Now, assume the negation that $y \in \alpha$. Using the definition of $\alpha$, it means that there is some $N \in A$ such that $y \in N$. Since $N \in A$, using equation 2, it follows that $N < y$. But $N$ and $y$, are sets. So, this means that, $N$ is a proper subset of $y$. $N \subset y$. Since, I have $y \in N$, it follows that $y \in y$. And here is a contradiction according to the ZF set theory. So, my assumption that $y \in \alpha$ is wrong. So, I have $y \notin \alpha$. This means that $\exists y \in \mathbb{Q}$ such that $y \notin \alpha$. This proves that $\alpha \ne \mathbb{Q}$.

Is the proof correct ? I have proven other properties here.

 

[WWGD]

Hi,
This is often taken as an axiom. I guess you have a different system , with other axioms. Can you elaborate a bit on your axioms?

 

[mathwonk]

I think he is taking as a construction the set of Dedekind cuts in the rationals, and is trying to prove that construction does satisfy the usual LUB axiom. I.e. he is not taking an axiomatic approach to the reals but a constructive approach, and trying to prove the axioms do hold for his construction.

 

[Office_Shredder]

I'm a little confused that it looks like you have a bounded set, and then are trying to prove it's not the rational numbers. Isn't it kind of obvious the rational numbers are unbounded, and hence the proof is complete?

 

[WWGD]

Im also cinfused on how, in what sense, a set itself can be considered a lower bound. This seems to assume a comparison between sets ( to see which of several set/bounds is the lowest, or that one set bounds another). Unless I am missing something here.

 

[issacnewton]

I am self studying set theory from the book "Classic Set Theory for guided independent study" by Derek Goldrei. So, before actually going for the set theory axioms, author talks about the real number construction using Dedekind cuts. And in that section, he proves the Completeness property of $\mathbb{R}$. Since I am self studying this, I wanted to prove it myself. So, all real numbers are treated as Dedekind left sets in his system. Equality and inequality of numbers is defined in terms of sets. So, he gives following definitions for equality and inequality for numbers.

Let $r$ and $s$ be Dedekind left sets.Then $r$ and $s$ are equal, written as $r =_{\mathbb{R}} s$, if they are equal as sets, i.e. for all $q$,

$$ q \in r \text{ if and only if } q \in s $$

$r$ is less than or equal to $s$, written as $r \le _{\mathbb{R}} s$, if $r \subseteq s$, i.e. for $q$,

$$ \text{if }q \in r \text{ then } q \in s $$

$r$ is less than $s$, written as $r < _{\mathbb{R}} s$, if $r \le _{\mathbb{R}} s$ and $r \ne _{\mathbb{R}} s$.

So, I used these definitions for the proof. I wanted to prove that $A$ has a least upper bound in $\mathbb{R}$. Since I claim that $\alpha$ is that lub, I should prove that $\alpha$ is a real number, which means that $\alpha$ is a Dedekind left set. I start with proving the properties of Dedekind left set. First property is that $\alpha$ is a proper, non-empty subset of $\mathbb{Q}$, so that $\varnothing \ne \alpha \ne \mathbb{Q}$. So, I am trying to prove the last part here, $\alpha \ne \mathbb{Q}$.

As WWGD pointed out, Completeness property of $\mathbb{R}$ is taken as an axiom in real analysis. But it seems that, it can be proven using Dedekind construction of the real numbers.

 

[nuuskur]

Somewhat easier to follow if you don't mention $\mathbb R$ at all. We are proving the completeness property of the set of all Dedekind cuts (which is identified with $\mathbb R$, yes, but let that be for later).

For the sake of clarity. A Dedekind cut is a subset $\alpha\subseteq \mathbb Q$ satisfying the following.

1. $\alpha \in\mathcal P(\mathbb Q) \setminus \{\emptyset, \mathbb Q\}$
2. $\forall p,q,\quad p\in \alpha\text{ and } q<p \Rightarrow q\in\alpha$
3. $\forall p\in\alpha,\exists q\in\alpha,\quad p<q$.

The set of all cuts is a poset with the natural ordering $\alpha \leqslant \beta :\Leftrightarrow \alpha\subseteq \beta$.

Claim. Every nonempty subset of Dedekind cuts which is bounded from above has a supremum.

Pf. Let $\mathcal A$ be a nonempty subset of Dedekind cuts such that it has an upper bound. That is, there exists a cut $\beta$ such that $\alpha\subseteq\beta$ for every $\alpha\in\mathcal A$. Define
$$C := \left \{ x\in\mathbb Q \mid \exists\alpha\in\mathcal A,\quad x\in\alpha \right \} = \bigcup _{\alpha\in\mathcal A} \alpha.$$
Clearly, $C\subseteq \beta$. It is a routine check that $C$ is a cut.

It is also clear that $C$ is an upper bound of $\mathcal A$. Now to show it is the supremum. Take any upper bound $\gamma$ of $\mathcal A$. Then, by definition, $C\subseteq \gamma$.

Food for thought: where does this proof fail without an upper bound for $\mathcal A$ and why does $\mathcal A$ have to be nonempty?

 

[issacnewton]

Thanks nuuskur. That's short proof. Since I am learning pure maths on my own, my proof is little longer or zig zag.

 

[nuuskur]

You are complicating things unnecessarily.

So, I have to come up with some set which is lub A. Now, A is a subset of R, so each member of A is a Dedekind left set. So, A is a set of sets. Now, I propose that the following set would be lub of $A$.

No, $A$ is a subset in the set of all Dedekind cuts. Don't identify that with $\mathbb R$, you are potentially begging the question somewhere down the line.

$$ \alpha = \bigcup A = \{ \beta | \exists \delta \in A (\beta \in \delta) \} $$

What is the union indexed over? You already said $A$ is a subset of cuts. In that case $\bigcup A=A$, there is no progress. Avoid overloading of notation.

I am trying to prove that $\alpha$ is a real number.

A Dedekind cut*

So, for that, I will need to prove that, $\alpha$ is a Dedekind left set. So, I need to prove that $\alpha \ne \mathbb{Q}$. Which means that, there exists some $x \in \mathbb{Q}$ such that $x \notin \alpha$.

Correct.

Spoiler: TeX pointers

This is what I need to prove. Now, I am given that $A$ is bounded above, so there is some $M \in \mathbb{R}$, such that

$$ \forall \; x \in A \; (x \leqslant M) \cdots\cdots (1) $$

/begin{align} formula /end{align} (replace "/" with "\") achieves a numbered formula
$$\begin{align} \text{formula}\tag{1} \end{align}$$
can change the number with /tag{}, for instance.

Now, $M < M+1$. There is some $y \in \mathbb{Q}$ such that $M < y < M + 1$. So, it means that

And now you are begging the question. You are working with Dedekind cuts and not real numbers. Do not assume a priori that the two are the same.To stay consistent we need to construct the set of all Dedekind cuts INDEPENDENTLY of $\mathbb R$ (because we don't know that $\mathbb R$ even exists) and only then show that it is a complete ordered field. Any two complete ordered fields are isomorphic. Therefore we denote the unique COF as $\mathbb R$.

Thanks nuuskur. That's short proof. Since I am learning pure maths on my own, my proof is little longer or zig zag.

The length of your proof is not relevant. What matters is whether your arguments are correct. Often we prove something in a lengthy way and find optimisations later.

 

[WWGD]

You are complicating things unnecessarily.

No, $A$ is a subset in the set of all Dedekind cuts. Don't identify that with $\mathbb R$, you are potentially begging the question somewhere down the line.

What is the union indexed over? You already said $A$ is a subset of cuts. In that case $\bigcup A=A$, there is no progress. Avoid overloading of notation.

A Dedekind cut*

Correct.

Spoiler: TeX pointers

/begin{align} formula /end{align} (replace "/" with "\") achieves a numbered formula
$$\begin{align} \text{formula}\tag{1} \end{align}$$
can change the number with /tag{}, for instance.

And now you are begging the question. You are working with Dedekind cuts and not real numbers. Do not assume a priori that the two are the same.To stay consistent we need to construct the set of all Dedekind cuts INDEPENDENTLY of $\mathbb R$ (because we don't know that $\mathbb R$ even exists) and only then show that it is a complete ordered field. Any two complete ordered fields are isomorphic. Therefore we denote the unique COF as $\mathbb R$.

Doesnt the Archimedean Property come into play? IIRC, the Reals are the unique Archimedean COF.

 

[nuuskur]

Doesnt the Archimedean Property come into play? IIRC, the Reals are the unique Archimedean COF.

Completeness implies the AP. "Reals are the unique Archimedean COF" This is true and the prefix "Archimedean" may be omitted.

 

[issacnewton]

Hello nuuskur, I have gone through your arguments in post # 7. I have now understood how $C$ is the supremum of the set $A$. But where does the proof fail if $A$ does not have an upper bound ? I never used that fact in the proof anywhere. Can you point out ?

 

[nuuskur]

But where does the proof fail if $A$ does not have an upper bound ? I never used that fact in the proof anywhere. Can you point out ?

Of course you used that fact! "Take any upper bound $\gamma$ of $\mathcal A$". If there are no upper bounds, then the argument is based on the empty set and fails.

The argument also fails if $\mathcal A$ is empty, because then $C=\emptyset$ and therefore $C$ is not a cut.

 

[mathwonk]

remark on terminology: the word "complete" in this setting has two possible definitions. The order complete definition used here (existence of lub) does imply archimedean, but the weaker, convergence of cauchy sequences, definition does not. then among all cauchy complete ordered fields, the reals are the only archimedean one. since there exist cauchy complete non Archimedean ordered fields, it seems common to use "complete ordered field" to refer to cauchy complete ones. (Lang, Algebra, p.286, Sah, Abstract Algebra, p.325)

The usage is not universal however. E.g. Mackey, on p. 11 of his Lectures on the theory of functions of a complex variable, which is based on his Harvard course from 1959-60, uses "complete" for the LUB property. Interestingly when I audited his course in about 1964, I seemed to recall he used the opposite terminology, and that it was from Mackey that I learned that the reals are characterized as the unique "complete archimedean ordered field". But now I am not entirely sure. Indeed on page 14 of his book, Mackey uses the term "complete archimedean ordered field" on line 9, in which by his convention the word "archimedean" is superfluous. He then omits it in line 17, describing the reals as the unique "complete ordered field". So maybe I learned it more fully from Van der Waerden.

Kitchen, p. 172 of Calculus of one variable, also uses "complete" to mean sup complete, as does Spivak, in Calculus, chap. 29. It seemed odd to me that the analysts use the term opposite to its usual meaning in analysis, until I realized they do not intend to discuss more general fields. Since the algebraists will do so, they apparently want the term to be available also when discussing non archimedean cases.

 

[nuuskur]

Yes, good point. The reals remain unique even if sup-completeness is relaxed to Cauchy completeness.

For the sake of completeness (pun intended) the following are equivalent for an ordered field $F$.

1. $F$ is sup-complete.
2. $F$ satisfies Archimedean property and $F$ is Cauchy complete.

 

[mathwonk]

Yes, 2 implies 1 is the theorem of Cauchy, Van der Waerden, section 67. and Spivak proves 1 implies cauchy completeness in chap. 29, reducing it to the easy case that LUB implies every bounded monotone sequence has a limit. That 1 implies archimedean is in chap. 8.

 

[MidgetDwarf]

Just to add a bit. There is a book by Ethan Bloch: The Real Numbers and Real Analysis, which starts with Peano Axioms and constructs the set of integers, then the rationals, then the reals via Dedekind Cuts.

Maybe helpful if you jumped all the way from rationals to reals, and are interested in starting from the naturals.

It also offers a bit of historical context in regards to what number meant for different people over the ages.

As an analysis text, I found the book by Abbot, to more reader friendly and better for a first exposure. I only read the first 4 chapters of Bloch text, since I wanted it only for the constructions of the real numbers. It may be a decent book to learn real analysis from.

If you like this kind of stuff, you can also look at what Surreal Numbers are, after you are done with the Dedekind Construction of R. I must admit, I never bothered with Surreal Numbers, as I am not that interested in "foundational" mathematics(I think this is the category it falls into).

 

[issacnewton]

Thanks nuuskur, finally, I understood this. MidgetDwarf, I will definitely check that book.

 

[MidgetDwarf]

Thanks nuuskur, finally, I understood this. MidgetDwarf, I will definitely check that book.

If you check around, I posted a coupon code for springer (40% off). I think you are ready to study analysis, based on your work in this thread. Give Abbot: Understanding Analysis, a try.

Although, Linear Algebra or Abstract Algebra may be an easier place to start with pure math.

There is a nice book by Sterling Berberian : Linear Algebra. The only con, would be some sections are short in exercises, but everything is lucid. It is a better explained Linear Algebra Done Right (Axler). Although Axler book is really clear, this just shows how clear an expositor Berberian is. I seen hard covers less than 20 used, and it is currently a dover book. The hardcover has nice margins.

There is also the fun, yet elementary book in number theory, by Pommersheim: An Introduction To The Theory Of Numbers. It starts slow, well explained, and exercises are a good mixture of easy to difficult. It is a bit pricey, and another book in number theory is needed at some point.

 

[issacnewton]

MidgetDwarf, thanks for all the books you mentioned. Some 6-7 years ago, I came across a book "How to prove it: A structured approach" by Daniel Velleman. This book explains basic logic and then goes on to explain how to do various kinds of proofs. Author is set theorist and so most of the examples are from set theory, but there are other examples too. I solved 80% problems at the end of the chapters. So, I am very comfortable with quantifiers and their manipulations. So, I am think, I am now ready for pure math stuff.

 

[MidgetDwarf]

MidgetDwarf, thanks for all the books you mentioned. Some 6-7 years ago, I came across a book "How to prove it: A structured approach" by Daniel Velleman. This book explains basic logic and then goes on to explain how to do various kinds of proofs. Author is set theorist and so most of the examples are from set theory, but there are other examples too. I solved 80% problems at the end of the chapters. So, I am very comfortable with quantifiers and their manipulations. So, I am think, I am now ready for pure math stuff.

Good. You are at a very good place to start learning. I strongly suggest the Abbot book. If you want to learn some analysis.

Which reminds me, I have to practice strong induction, since I started reviewing Number Theory (an area I am very weak in).