1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving least upper bound property implies greatest lower bound property

  1. Nov 8, 2014 #1
    1. The problem statement, all variables and given/known data
    Prove if an ordered set A has the least upper bound property, then it has the greatest lower bound property.

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

    3. 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 A0 ⊂ A, and A0≠∅, so here I'm defining a restriction of the set A, calling it A0 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∈A0, 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∈A0, 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 A0, but I don't know how to get that out of the construction that I've made.
     
  2. jcsd
  3. Nov 9, 2014 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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 [itex]B= -A= {-x | x \in A}[/itex]. If A has lower bound, a, then [tex]a\le x[/tex] for all x in A. From that [tex]-a\ge -x[/tex] so that -a is an upper bound for B.
     
  4. Nov 9, 2014 #3
    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.
     
  5. Nov 10, 2014 #4

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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##.
     
    Last edited: Nov 10, 2014
  6. Nov 11, 2014 #5
    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.
     
  7. Nov 11, 2014 #6

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  8. Nov 11, 2014 #7

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.

    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.
     
  9. Nov 11, 2014 #8
    Took a break from the problem for a day, came back to it and this is what I have now.

    Let A0 be a non-empty subset of A, A0 is bounded above and has the least upper bound property, such that b≥x for any x∈A0, and b is the least upper bound, sup A0=b. B is the set of all bounds y such that y≥b≥x∈A0. 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?
     

    Attached Files:

    Last edited: Nov 11, 2014
  10. Nov 12, 2014 #9

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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##.
     
    Last edited: Nov 12, 2014
  11. Nov 12, 2014 #10
    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.
     
  12. Nov 12, 2014 #11
    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.
     
  13. Nov 12, 2014 #12

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

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

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

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

    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.
     
  14. Nov 12, 2014 #13
    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.

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

    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##.
     
  15. Nov 12, 2014 #14

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  16. Nov 12, 2014 #15
    Now I'm really confused, you said...

    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?
     
    Last edited: Nov 12, 2014
  17. Nov 13, 2014 #16

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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##.
     
    Last edited: Nov 13, 2014
  18. Nov 13, 2014 #17
    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.
     
    Last edited: Nov 13, 2014
  19. Nov 14, 2014 #18

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  20. Nov 14, 2014 #19
    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##.
     
    Last edited: Nov 14, 2014
  21. Nov 15, 2014 #20

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.

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

    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.

    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##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proving least upper bound property implies greatest lower bound property
  1. Upper bound of a limit (Replies: 5)

  2. Least Upper Bounds (Replies: 31)

Loading...