Proving least upper bound property implies greatest lower bound property

[schlynn]

Homework Statement

Prove if an ordered set A has the least upper bound property, then it has the greatest lower bound property.

Homework Equations

Definition of the least upper bound property and greatest lower bound property, set theory.

The Attempt at a Solution

Ok, I think that my main problem with this proof is knowing exactly what I'm allowed to do while constructing proofs. I have to prove that the least upper bound property implies the greatest lower bound property, and to start out with this I tried to write out some definitions and see what I can come up with and see if that gives me any insight to how one implies the other, I know that A has the least upper bound property if and only if it has the greatest lower bound property, that's given by the book. So to start constructing this I tried something like this:

Let A₀ ⊂ A, and A₀≠∅, so here I'm defining a restriction of the set A, calling it A₀ and saying that it is not empty.

Then I tried this:

Let S be the set of all upper bounds b, b|b∈A and b≥x for every x∈A₀, so here I'm trying to make the set of all upper bounds, call it the set S, and say that every element of the set S is greater than or equal to x∈A₀, but this is as far as I can get, after this I'm lost. Like I said, I'm not even sure if I'm "allowed" to do what I did. Is there something I'm missing from this? I think that next I would try to show that there is a inf A₀, but I don't know how to get that out of the construction that I've made.

 

[HallsofIvy]

It looks to me like you cannot use "A has the least upper bound property if and only it has the greatest lower bound property" because what you are asked to prove, "If A has the least upper bound property, then it has the greatest lower bound property" is part of that.

But the upper bound property is "if a set has an upper bound then it has a least upper bound" and the lower bound property is "if a set has a lower bound then it has a greatest lower bound". It makes no sense to me to say "a set has the least upper bound property". Rather a number system has the least upper bound property- the set of all real numbers has that property, the set of all rational numbers does not.

So what you want to do is start "if A has a lower bound, a," and then use the "least upper bound property" to conclude "A has a greatest lower bound". You don't know whether or not A has an upper bound so you cannot apply the least upper bound property to A itself. Instead, let $B= -A= {-x | x \in A}$. If A has lower bound, a, then $$a\le x$$ for all x in A. From that $$-a\ge -x$$ so that -a is an upper bound for B.

 

[schlynn]

It looks to me like you cannot use "A has the least upper bound property if and only it has the greatest lower bound property" because what you are asked to prove, "If A has the least upper bound property, then it has the greatest lower bound property" is part of that.

But the upper bound property is "if a set has an upper bound then it has a least upper bound" and the lower bound property is "if a set has a lower bound then it has a greatest lower bound". It makes no sense to me to say "a set has the least upper bound property". Rather a number system has the least upper bound property- the set of all real numbers has that property, the set of all rational numbers does not.

So what you want to do is start "if A has a lower bound, a," and then use the "least upper bound property" to conclude "A has a greatest lower bound". You don't know whether or not A has an upper bound so you cannot apply the least upper bound property to A itself. Instead, let $B= -A= {-x | x \in A}$. If A has lower bound, a, then $$a\le x$$ for all x in A. From that $$-a\ge -x$$ so that -a is an upper bound for B.

Ok, this makes more sense as a way to approach the proof. But as far as using the property in the proof, my construction was trying to show that any non-empty set of A will have the property, and in the book I'm working from it says that these properties can be generalized to any ordered set, is that not true? And the book continues with some axioms later in the chapter showing that was we are working towards is creating a continuum from the reals. Correct my if I'm wrong, but this does help me a lot with the proof, thank you.

 

[Fredrik]

I would start like this: Let B be an arbitrary subset of A that's bounded from below. (Your goal is now to prove that B has a greatest lower bound). Let C be the set of all lower bounds of B. (What can you say about C?)

...we are working towards is creating a continuum from the reals.

You're working towards a definition of the real numbers. The definition of "field" covers the properties of the addition and multiplication operations. The definition of "ordered field" also includes the properties of the order. The way to proceed from there is to prove that all ordered fields that have the least upper bound property are isomorphic. Since they are isomorphic, it doesn't matter which one of them we call $\mathbb R$.

 

[schlynn]

I would start like this: Let B be an arbitrary subset of A that's bounded from below. (Your goal is now to prove that B has a greatest lower bound). Let C be the set of all lower bounds of B. (What can you say about C?)You're working towards a definition of the real numbers. The definition of "field" covers the properties of the addition and multiplication operations. The definition of "ordered field" also includes the properties of the order. The way to proceed from there is to prove that all ordered fields that have the least upper bound property are isomorphic. Since they are isomorphic, it doesn't matter which one of them we call $\mathbb R$.

Ok, so I'm trying to prove that the set you call C has a property that implies the result?

This is a topology book, and it has a list of axioms, 8 total, and says the first 6 form a field, which is reminiscent of vector spaces that I studied in linear algebra, and then the last two axioms showed that the reals had completeness, I think is how they worded it, am I getting the general idea wrong? I can site the book specifically, but this wasn't really related to the question at hand.

 

[PeroK]

Ok, so I'm trying to prove that the set you call C has a property that implies the result?

This is a topology book, and it has a list of axioms, 8 total, and says the first 6 form a field, which is reminiscent of vector spaces that I studied in linear algebra, and then the last two axioms showed that the reals had completeness, I think is how they worded it, am I getting the general idea wrong? I can site the book specifically, but this wasn't really related to the question at hand.

I think it is your inexperience in doing formal proofs that is making this difficult. What I would do is talk myself thru the problem:

What am I given?

1) A is an ordered set.
2) A has the least upper bound property.

What does 2) actually mean?

3) It means that if C is a subset of A and C has an upper bound, then C has a least upper bound.

[Now, repeat 3) to yourself until you really understand what it means.]

What do I have to prove?

4) I have to prove that A has the greatest lower bound property.

What does 4) actually mean?

5) It means that if C is a subset of A and C has a lower bound, then C has a greatest lower bound.

So, in summary, what do I have to do?

I have to show that 3) implies 5).

One more thing: are we assuming A is a field? No. A is simply an ordered set.

Now, you can try to follow Fredrik's advice for how to prove this.

 

[Fredrik]

Ok, so I'm trying to prove that the set you call C has a property that implies the result?

I think I will have to wait for you to show us an attempt to try to use my hint before I can give you another one. For now I'll just say that you must use the assumption that A has the upper bound property, so what you should ask yourself is how you can use it.

This is a topology book, and it has a list of axioms, 8 total, and says the first 6 form a field, which is reminiscent of vector spaces that I studied in linear algebra, and then the last two axioms showed that the reals had completeness, I think is how they worded it, am I getting the general idea wrong? I can site the book specifically, but this wasn't really related to the question at hand.

6 axioms for a field? It's 10 when I write them down. (four for addition, four for multiplication, and the left and right distributive laws). The definition of "ordered field" has two more, both for the < relation. The final axiom that takes us to the real numbers is the upper bound property.

 

[schlynn]

Took a break from the problem for a day, came back to it and this is what I have now.

Let A₀ be a non-empty subset of A, A₀ is bounded above and has the least upper bound property, such that b≥x for any x∈A₀, and b is the least upper bound, sup A₀=b. B is the set of all bounds y such that y≥b≥x∈A₀. B contains at least b, the least upper bound, if so b is the smallest element of the set B. If B contains more than just b, then all the elements in B must be greater than or equal to b, and b bounds all elements of B from below, and as I just showed, b is the least element in B, done.

Right?

 

[Fredrik]

Let A₀ be a non-empty subset of A, A₀ is bounded above and has the least upper bound property, such that b≥x for any x∈A₀, and b is the least upper bound, sup A₀=b.

Adding the word "non-empty" was a good idea. I made a mistake when I didn't include it in my hint). Then things get weird. When you say "$A_0$ is bounded above", is that part of your assumption about $A_0$, or a statement about $A_0$? If it's the latter, it's wrong. (To see this, consider e.g. $A_0=\mathbb Z$). So I guess it's the former. You wanted to say something like: Let $A_0$ be an arbitrary non-empty subset of $A$ that's bounded from above.

(Note that my first step was to introduce an arbitrary set that's bounded from below. You seem to have ignored that part of my hint).

So is "...and has the least upper bound property" also a part of your assumption about $A_0$, or is it a statement about $A_0$? Somewhere around this part, your sentence becomes too hard to follow. You should break the argument up into shorter sentences. (Where you trying to define "upper bound" in the same sentence that stated either an assumption or a conclusion about $A_0$? That's not a good idea. If you want to state the definitions to show that you know them, do it before the proof. Also, there's no need to say that $A_0$ has the least upper bound property. It's sufficent to know that $A$ has the least upper bound property.

Your attempt is a bit disorganised. This is how you should be thinking:

1. What am I supposed to prove? That $A$ has the greatest lower bound property.
2. What does that statement mean? Every non-empty subset of $A$ that's bounded from below has a greatest lower bound.
3. How do I prove that? Let $B$ be an arbitrary non-empty subset of $A$ that's bounded from below. Now we need to use the fact that $A$ has the least upper bound property to prove that $B$ has a greatest lower bound. To use that fact, we will have to introduce a subset of $A$ that's bounded from above. My suggestion is to use the set of lower bounds of $B$.

 

[schlynn]

Adding the word "non-empty" was a good idea. I made a mistake when I didn't include it in my hint). Then things get weird. When you say "$A_0$ is bounded above", is that part of your assumption about $A_0$, or a statement about $A_0$? If it's the latter, it's wrong. (To see this, consider e.g. $A_0=\mathbb Z$). So I guess it's the former. You wanted to say something like: Let $A_0$ be an arbitrary non-empty subset of $A$ that's bounded from above.

(Note that my first step was to introduce an arbitrary set that's bounded from below. You seem to have ignored that part of my hint).

So is "...and has the least upper bound property" also a part of your assumption about $A_0$, or is it a statement about $A_0$? Somewhere around this part, your sentence becomes too hard to follow. You should break the argument up into shorter sentences. (Where you trying to define "upper bound" in the same sentence that stated either an assumption or a conclusion about $A_0$? That's not a good idea. If you want to state the definitions to show that you know them, do it before the proof. Also, there's no need to say that $A_0$ has the least upper bound property. It's sufficent to know that $A$ has the least upper bound property.

Your attempt is a bit disorganised. This is how you should be thinking:

1. What am I supposed to prove? That $A$ has the greatest lower bound property.
2. What does that statement mean? Every non-empty subset of $A$ that's bounded from below has a greatest lower bound.
3. How do I prove that? Let $B$ be an arbitrary non-empty subset of $A$ that's bounded from below. Now we need to use the fact that $A$ has the least upper bound property to prove that $B$ has a greatest lower bound. To use that fact, we will have to introduce a subset of $A$ that's bounded from above. My suggestion is to use the set of lower bounds of $B$.

Ok, first, thank you, this is exactly the type of help needed. I'm not very experienced with these types of proofs, I've done proofs in the past, but mostly number theory and typical geometry stuff, and the subject matter is much different, and using these concepts in the right order in the right way is entirely foreign to me. The American educational system only really puts emphasis on HOW to solve math problems, not WHY the solutions are what they are or anything past mechanical solving of equations. At least in my experiences.

To address your first concern, in the problem statement it says that A has the least upper bound property, and that applies to any non-empty subset of A, I think that I see where I went wrong, I missed your hint about using the lower bound. I haven't reworked the proof or anything yet, as I'm replying first, but it seems like, the least upper bound property, almost implies an order to the set, and the subsets are just sections of the real line for example, and deciding where the actual cuts for the sections are doesn't matter. I'll have another attempt done here soon.

 

[schlynn]

Ok, I think I have it now.

Let $B$ be a non-empty subset of $A$ that's bounded below, such that b≤ any x∈$B$.
Let $C$ be the set of all lower bounds for $B$ such that for any y∈C, y≤b≤ any x∈$B$.
We know that $A$ has the least upper bound property, so $C$ also has a least upper bound, call it α, this means that α≥any y∈$C$.
And if the set of all lower bounds for $B$ has a largest element, which it does, we call it α, that element is called the greatest lower bound, of infimum.
This completes the proof now?

This seems closer, at least.

 

[Fredrik]

Now you have the right strategy. So let's look at the details.

Let $B$ be a non-empty subset of $A$ that's bounded below, such that b≤ any x∈$B$.

The sentence should end after "below". You shouldn't explain what "bounded below" means in the middle of the proof, especially not inside a sentence that's a key part of the proof. Perhaps you meant the end of the sentence to say something like "Let $b$ be an arbitrary lower bound of B". If such a statement is needed, then it needs to be stated clearly, in a separate sentence.

Let $C$ be the set of all lower bounds for $B$ such that for any y∈C, y≤b≤ any x∈$B$.

Similarly, this sentence should end after "for $B$". I'm not sure what the end of the sentence is saying. If $b$ is an arbitrary lower bound of B, then it's not necessarily true that $y\leq b$ for all $y\in C$.

We know that $A$ has the least upper bound property, so $C$ also has a least upper bound, call it α,

You skipped a small but important detail here. To use the least upper bound property to conclude that $C$ has a least upper bound, you must first show that $C$ has an upper bound. This isn't hard. It's sufficient to say that $B$ is non-empty and every element of $B$ is an upper bound of $C$.

And if the set of all lower bounds for $B$ has a largest element, which it does, we call it α, that element is called the greatest lower bound, of infimum.

How do you know that $C$ has a largest element? The least upper bound property only tells us that it has a least upper bound. I would define $\alpha=\sup C$. The final step is to show that the $\alpha$ defined this way is also the greatest lower bound of $B$. To do this, you have to use the definition of greatest lower bound.

 

[schlynn]

Now you have the right strategy. So let's look at the details.

The sentence should end after "below". You shouldn't explain what "bounded below" means in the middle of the proof, especially not inside a sentence that's a key part of the proof. Perhaps you meant the end of the sentence to say something like "Let bb be an arbitrary lower bound of B". If such a statement is needed, then it needs to be stated clearly, in a separate sentence.

Similarly, this sentence should end after "for BB". I'm not sure what the end of the sentence is saying. If bb is an arbitrary lower bound of B, then it's not necessarily true that y≤by\leq b for all y∈Cy\in C.

Not sure why I do that, I think it's just instinct to want to jam algebra into it where ever I can. But I can see how it makes things harder to understand, I'll try to be more direct I guess, in the definitions when doing a proof.

You skipped a small but important detail here. To use the least upper bound property to conclude that CC has a least upper bound, you must first show that CC has an upper bound. This isn't hard. It's sufficient to say that BB is non-empty and every element of BB is an upper bound of CC.

Forgot that part I guess, but the use of $B$ as an upper bound for $C$ is a neat construction.

How do you know that CC has a largest element? The least upper bound property only tells us that it has a least upper bound. I would define α=supC\alpha=\sup C. The final step is to show that the α\alpha defined this way is also the greatest lower bound of BB. To do this, you have to use the definition of greatest lower bound.

In the last two sentences I'm trying to show that since $C$ has an upper bound, it has a least upper bound, and I want to call it α. And then by definition, α is a greatest lower bound for $B$ because it's the largest element in $C$.

 

[Fredrik]

C may not have a largest element. Suppose that A is the real numbers and B is the set of non-negative real numbers. Then C is the negative real numbers. This set has a least upper bound 0, but no largest element.

 

[schlynn]

Now I'm really confused, you said...

How do you know that CC has a largest element? The least upper bound property only tells us that it has a least upper bound. I would define α=supC\alpha=\sup C. The final step is to show that the α\alpha defined this way is also the greatest lower bound of BB. To do this, you have to use the definition of greatest lower bound.

Which is what I did. It makes sense with the example you gave, but I'm at a lose now I guess.

The supremum of $C$ is the greatest lower bound for $B$ it seems like, and that's what I said right? Maybe I worded it wrong?

 

[Fredrik]

You're saying that you did what I suggested, but you didn't. I suggested that you define $\alpha=\sup C$ and then prove that $\alpha=\inf B$. What you did was to define $\alpha=\max C$ and then just say that $\alpha=\inf B$. Your definition of $\alpha$ doesn't work since $C$ may not have a maximal element. Even if it does, you would have to explain how you know that $\alpha=\inf B$.

 

[schlynn]

Well, since C is bounded above by B, and since C is a subset of A, C has the least upper bound property, and that means that the inf B is greater than every element in C right? Then the inf B is the supremum of C? This should help cover the case of the sup C not being in C.

 

[Fredrik]

Well, since C is bounded above by B, and since C is a subset of A, C has the least upper bound property, and that means that the inf B is greater than every element in C right?

inf B is greater than or equal to every element in C, but I don't follow your argument for this. To say that C has the least upper bound property is to say that every subset of C that is bounded from above has a least upper bound. This seems irrelevant, since you haven't mentioned any subsets of C.

I see now that I've made a mistake. Since inf B is the greatest lower bound of B, it's a lower bound of B. That makes it an element of C. This can be used to show that C does have a maximum element. (This is however no easier than proving the result we want to prove). My earlier counterexample to that is wrong, because if B is the set of non-negative real numbers, then C is the set of non-positive real numbers, not the set of negative real numbers.

 

[schlynn]

inf B is greater than or equal to every element in C, but I don't follow your argument for this. To say that C has the least upper bound property is to say that every subset of C that is bounded from above has a least upper bound. This seems irrelevant, since you haven't mentioned any subsets of C.

I see now that I've made a mistake. Since inf B is the greatest lower bound of B, it's a lower bound of B. That makes it an element of C. This can be used to show that C does have a maximum element. (This is however no easier than proving the result we want to prove). My earlier counterexample to that is wrong, because if B is the set of non-negative real numbers, then C is the set of non-positive real numbers, not the set of negative real numbers.

I was talking extraneously in the last part of my second sentence. But isn't this what I should be doing, I need to show that $C$ has a least upper bound, and by doing that, will show that the set of lower bounds has a supremum, and that would be by definition a greatest lower bound for $B$ right? Because $B$ has an infimum if it's set of lower bounds has a supremum, at least that's what I'm tring to say.

"An ordered set A is said to have the greatest lower bound property if every non-empty subset $B$ of $A$ that is bounded below has a greatest lower bound."

"If the set of all lower bounds contains a largest element, it is called the greatest lower bound."

What I'm trying to show about $C$ now, is that with it's least upper bound, it's least upper bound has the property of also being the greatest lower bound for $B$, because it would be ≥ any element in $C$, and ≤ any element in $B$.

 

[Fredrik]

I thought that I replied to this yesterday, but I just realized that I got distracted by something and never got around to submitting the post.

I was talking extraneously in the last part of my second sentence. But isn't this what I should be doing, I need to show that $C$ has a least upper bound, and by doing that, will show that the set of lower bounds has a supremum, and that would be by definition a greatest lower bound for $B$ right?

Not by definition. The definition of "greatest lower bound" is this:

Let E be a subset of A. Let x be an element of A. x is said to be a greatest lower bound of E if it's a lower bound of E, and for all y in A such that y is a lower bound of E, we have y≤x.​

It's easy to show that this implies that no set has more than one greatest lower bound, so if E has a greatest lower bound, it has exactly one greatest lower bound, so it makes sense to call it the greatest lower bound, and to choose a notation for it. (If a,b are both greatest lower bounds of E, we have $a\leq b$ and $b\leq a$, and therefore $a=b$).

If we define $\alpha=\sup C$, it's not immediately obvious that $\alpha=\inf B$. You have to show that $\alpha$ is a lower bound of $B$ and that for all $\beta\in A$, if $\beta$ is a lower bound for B, then $\beta\leq\alpha$.

"If the set of all lower bounds contains a largest element, it is called the greatest lower bound."

Is this how your book defines it? I'm not familiar with this definition. It looks equivalent to mine, but it takes a little bit of work to prove it.

What I'm trying to show about $C$ now, is that with it's least upper bound, it's least upper bound has the property of also being the greatest lower bound for $B$, because it would be ≥ any element in $C$, and ≤ any element in $B$.

Define $\alpha=\sup C$. Yes, we have $\alpha\geq c$ for all $c\in C$. This is by definition equivalent to saying that $\alpha$ is an upper bound of C. We also have $\alpha\leq b$ for all $b\in B$, but this is slightly less trivial. I think it deserves a comment like this: Let $b\in B$ be arbitrary. Since $b$ is an upper bound of $C$, and $\alpha$ is the least upper bound of $C$, we have $\alpha\leq b$.

 

[schlynn]

If we define α=supC\alpha=\sup C, it's not immediately obvious that α=infB\alpha=\inf B. You have to show that α\alpha is a lower bound of BB and that for all β∈A\beta\in A, if β\beta is a lower bound for B, then β≤α\beta\leq\alpha.

Ok, so now all I need to show is that all the other lower bounds are ≤ sup $C$?

Let b∈Bb\in B be arbitrary. Since bb is an upper bound of CC, and α\alpha is the least upper bound of CC, we have α≤b\alpha\leq b.

Your constructions are a lot more elegant than mine, I assume this comes with practice? I can also take what you said here, and then say, c ≤ α ≤ b must be true. Which to me means that any element from $C$ must be ≤ any element of $B$ due to transitivity. It seems like this is essentially sandwiching α between $C$ and $B$. This equality also means that any other bound for $B$ is ≤ α, which it what I'm pretty sure was the last step.

 

[Fredrik]

Yes, that finishes the proof*, and yes, it does come with practice. I've had a lot of practice carefully writing out proofs, and then looking at them again an hour later to see if there's something I can improve. This approach is highly recommended. You will be surprised by how many times you will find your own statements too difficult to follow, and by how many times you can make significant improvements to your proof.

*) Our goal was to show that $\alpha$ is the greatest lower bound of B. We have already proved that it's a lower bound of B. Let $\beta$ be an arbitrary lower bound of B. By definition of C, we have $\beta\in C$. This implies that $\beta\leq\sup C=\alpha$.

 

[schlynn]

Ok, thank you, I understand the types of proof now. Going to also look into some books on set theory proofs and examples. Thanks again for all the help.