Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Least upper bound axiom

  1. Jan 5, 2010 #1
    1) "Least upper bound axiom:
    Every non-empty set of real numbers that has an upper bound, has a least upper bound."

    Why does it have to be non-empty? Is there an upper bound for the empty set?


    2) "It can be proved by induction that: every natural number "a" is of the form 2b or 2b+1 for some b in N U{0}. "
    The base case is clearly true, but how can we go from the induction hypothesis to the case for k+1?

    Thanks for any help!
     
  2. jcsd
  3. Jan 5, 2010 #2

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    I suppose the definition of an upper bound B for a set S is, that x <= B for all x in S.
    So in that sense, any number is an upper bound for the empty set (the statement "for all x in S, x is smaller-or-equal to some arbitrary number is vacuously true). However, the problem is that there is no smallest upper bound.

    Isn't that like, really obvious?
    If k is of the form 2b, then k + 1 is 2b + 1 and you are done.
    Otherwise, it is of the form 2b + 1 and you can write k + 1 as 2c where c = b + 1.
     
  4. Jan 6, 2010 #3
    1) OK, now my only problem is: why is there an upper bound for the EMPTY set when there is actually NO element in the set? Why is 1 an upper bound? Why is -5 an upper bound?
    The definition for upper bound is x<=b for all x in the set, but for the empty set there is no element, so does it even make sense to talk about upper bounds?

    2) OK, now I see how we can prove the statement by induction. But the statement itself looks really really obvious to me (it's like saying every natural number is either odd or even), why do we even need "proofs" for such things?

    Thanks!:)
     
  5. Jan 6, 2010 #4
    Sometimes it is useful to consider its contrapositive. That is you probbably know that the following are logicaly equivalent(essentially they have the same truth table)

    p->q equivalent to {not q}->{not p}

    If B is the least upper bound for S, like mentoned above, by def. x=<B, for all x in S.

    Let,

    p:x=<B, for all x in S and q: B=supS

    Now, its contrapositive would be:

    not q : B is not a least upper bound for S, and not p: there exists some x in S, such that x>B.

    Now, since this is a def. it works both ways, that is p<->q, so for our purpose take q->p, so the contrapositive for this case would be:

    not q->not p, but for S the empty set, not q is false, so the statement not q->not p, is true by default(or as ComuChip said vacuously true).

    Cheers!
     
  6. Jan 6, 2010 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Logicially, if you have a statement of the form "if p the q" and p is false then the entire statement is true, no matter what q is.

    The definition of upper bound is that "a" is an upper bound for the set A if and only if the statement "if x is a member of A, the [itex]x\le a[/itex]". If A is empty, then the hypothesis "x is a member of A" is false so the entire statement is true.

    Are you suggesting the "looking really obvious" is sufficient to be certain it is true? How do you know that there is not some number, say larger than 10000000000000000000000000000 that is neither even nor odd? Have you tested all of them?

     
  7. Jan 6, 2010 #6

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    If you want to know more about 1) then you can also check out this Wikipedia page.

    Vacuous truth is often useful because it makes statements about the empty set true, without us having to include the empty set as a special case in our theorems. In this case, the theorem is not true for the empty set, so we have to mention it explicitly.
    However, in the statement "any finite subset of the real numbers has an upper bound" we can omit the word "non-empty".
     
  8. Jan 8, 2010 #7
    1) Fact: Peter is a man.
    statement 1: If Peter is a woman, then Peter's weight>250kg
    statement 2: If Peter is a woman, then Peter's weight≤250kg
    statement 3: If Peter is a woman, then Peter's weight=250kg
    statement 4: If Peter is a woman, then Peter's weight=2550kg

    So in this case, are all 4 statements correct?? But e.g. statements 1 and 2 seem to contradict each other?

    It's a little weird to me talking about things that don't even exist...is vacuous truth just a "convention" in logic and math?
     
  9. Jan 8, 2010 #8
    They are all correct. Statement 1 and 2 only contradict each other if there is a possibility that Peter is a woman. This is how we define it in logic and mathematics, but in everyday contexts people often use "if ..., then ..." statements in a different way. For instance to explain a hypothetical scenario "If I were president, I would do X". From a logical point of view that statement is meaningless (unless you were president) because you weren't so you can state anything you like about what you would have done, but in the real world people doesn't always use "if then" for logical implication.
     
  10. Jan 8, 2010 #9

    Landau

    User Avatar
    Science Advisor

    Ex falso sequitur quodlibet.
     
    Last edited: Jan 8, 2010
  11. Jan 8, 2010 #10
    If you think they are false, produce a counterexample. You'll find you'll be unable to do so because Peter is not a woman, so you have nothing going for you. That is the logic behind such statements.

    For all x in the empty set, x is a green-eyed lion. This is a true statement. Why? Well, give me a counterexample. There are none simple because there are no members in the empty set.

    I could say for all x in the empty set, there exists an n-ball of some radius r>0 centered at x such that the n-ball is completely within the empty set. Is it false? Give me a counter example. There exist none as there are no members. So the empty set is open.

    I could also say for all x in the empty, there does not exist an n-ball of some radius r > 0 centered at x that is completely within the empty. Is this false? Once again, I ask for a counterexample. It is impossible to produce one. Therefore the empty is closed.

    You can get all sorts of crazy statements with the empty set.
     
  12. Jan 8, 2010 #11
    Are you saying that a set A is closed iff for all x in A, there does not exist r>0 such that [tex]B(x;r) \subset A[/tex]? If so, this is not correct.

    Take [0,1] for instance, which is closed in [tex]\mathbb{R}[/tex]. Choose [tex]x=1/2[/tex] and [tex]r=1/4[/tex]. Then [tex] B\left(1/2;1/4\right) \subset [0,1][/tex], and by this definition, is not closed.

    The definition you are looking for is that a set A is closed in a metric space X iff [tex]A = \bar{A}[/tex], where [tex] \bar{A} = \left\{ x \in X \mid \forall r>0 \left( B\left(x;r\right) \cap A \neq \emptyset \right) \right\}[/tex]. Or, in other words, the set coincides with its own closure.

    Using the proper definition, it is immediately apparent why the empty set must be closed.
     
  13. Jan 8, 2010 #12
    My bad. This is what I get for not actually using quantifiers and negating them. What I meant to say was that a set A is closed iff there exist an x in A such that for all r > 0, B(x; r) is not completely within set A. But yeah, your method works as well.
     
  14. Jan 8, 2010 #13
    No, that's still not correct. It's important to note that the definition of closed is NOT the negation of open. They are not opposite notions. You can have sets that are both open and closed ([tex]\mathbb{R}[/tex] for example), or neither open nor closed (like [tex](0,1][/tex]). The definition of open concerns interior points, while the definition of closed concerns adherent points (or limit points, depending on your text).

    Using your new definition, [tex] \left(0,1\right) \cup \left\{2\right\} [/tex] would be closed in [tex]\mathbb{R}[/tex]. But it's not.
     
  15. Jan 8, 2010 #14
    Hmm true, I was thinking compliments instead of negations. But you are right. I always forget things can be neither open nor closed. It's like that dumb topology joke about the difference between a door and a set, how the former can only be open or closed while the latter can be open, closed, both open or both closed.

    In any case, thank you for the correction!
     
  16. Jan 9, 2010 #15

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    "Both open or both closed", since you are talking about a single set, makes no sense! You mean that a set can be open, closed, neither open nor closed, or both open and closed.
     
  17. Jan 10, 2010 #16
    I learned a closed set to be a set that contains all of its accumulation points. Wheras, an open set, A, to be one such that for any x in A,
    B(x,r) would be contained in A, for some choice of r>0.
     
  18. Jan 10, 2010 #17
    Indeed, that is an equivalent definition. I prefer to use adherent points because that's what I was first introduced to when I studied metric spaces. Apparently they are not as common in literature...?
     
  19. Jan 10, 2010 #18
    Probbably! At least in my experience, i've always seen it reffered to as 'accumulation point'.
     
  20. Jan 10, 2010 #19
    We're getting a bit off topic, but oh well...

    Adherent points and accumulation/limit points ARE different. Note my definition of closure from earlier. Accumulation points are adherent, but the converse is not always true.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Least upper bound axiom
  1. Least upper bound (Replies: 5)

Loading...