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!

Homework Help: Proof for upper bounded sets

  1. Oct 9, 2008 #1
    1. The problem statement, all variables and given/known data

    x is an upper bound for the set Y. Prove that x = sup(Y) (least upper bound) if and only if for every e > 0, there is some y in Y (depending on e) such that x < y + e

    (e in this case is every positive real number)

    3. The attempt at a solution

    since for every y in Y, y <= x. hence, x - y >= 0 for each y in Y. Thus, there corresponds some positive real number for each y in Y, which can be added to y to make it greater than x. x < y + e.

    Does this make sense? sorry for the poor notation. Thank you.
  2. jcsd
  3. Oct 9, 2008 #2
    First of all, this is an if and only if statement, so you have to do two directions.

    For the first direction, assume x= sup(Y). Let [itex] \epsilon > 0 [/itex]. For the sake of contradiction assume [itex] \exists y' \in Y [/itex] such that [itex] x \geq y + \epsilon [/itex]. Why is this a contradiction to x=sup(Y)?

    For the second direction, assume [itex] \forall \epsilon >0, \exists y \in Y [/itex] such that [itex] x < y+ \epsilon [/itex]. Just off the top of my head, I would say to try defining y_n such that [itex] x - y_n < \frac{1}{n}, n \in \mathbb{N} [/itex]. And play with that.
  4. Oct 10, 2008 #3
    For the second direction, it should be easier.
    it is enough to show x is the least upper bound. suppose x is not the smallest one, then there exists an epsilon>0 such that x-epsilon is the least upper bound. but by the hypothesis, there exists a y such that y > x-epsilon. Hence x is not an upper bound, which contradicts to x is upper bound. Hence x is the least upper bound.
    BTW, I find writing x-e<y instead of x<y+e is more understandable.
  5. Oct 28, 2011 #4
    Why do you have to even say epsilon>0? You never use epsilon besides attaching it to x. I see this somewhere else too, I am confused.
  6. Oct 28, 2011 #5
    I don't understand what you're asking. Could you elaborate?
  7. Oct 28, 2011 #6
    Hey, Kreizhn.
    Sure. I don't understand why we need epsilon in the proof, seems like we never used it.
  8. Oct 28, 2011 #7
    In all honesty, I don't much like boombaby's proof and I think there is a hole in it. In particular, the fact that [itex] y > x-\epsilon [/itex] only implies that [itex] x-\epsilon [/itex] is not an upper bound, and says nothing about why x is not an upperbound. Furthermore, it is unclear to me whether the OP was allowed to assume the existence of the least upper bound (it certainly does exist for sets bounded above, but the OP may not have been able to assume that). Unless I've missed something, this means that boombaby's proof is flawed.

    However, I have a feeling your question extends beyond this choice of proof. Since we're trying to show an if and only if, we are forced to use the tools are our disposal. Earlier in the thread we discussed the proof of the [itex] \Rightarrow [/itex] direction. What boombaby is trying to show that is [itex] \Leftarrow [/itex] direction, which states that

    Hence the epsilon is important to showing this result. Does that make sense? Or have I misinterpreted your question?
  9. Oct 28, 2011 #8
    thanks, this is just a hard question for me, let me follow your work and work it out see if it makes sense to me.
  10. Oct 28, 2011 #9
    I make no promises that my method works either :P It was just a top of the head suggestion. Try it though! If it doesn't work, I'll take another look at it and see if I can't push you in the right direction.
  11. Oct 28, 2011 #10


    User Avatar
    Science Advisor

    my thought is:

    proof by contradiction:

    suppose that we have another upper bound for Y, x', with x' < x.

    let ε = x - x'.

    we know that there exists some y in Y, with x < y + ε so....

    (hopefully you can figure out the rest) :)
  12. Oct 28, 2011 #11
    I think I got it, it was that bad actually.

    Could anyone help me with this?
    If B and B' are subsets of X, A[itex]\subset[/itex]B, and A[itex]\subset[/itex]B', then A is open in B[itex]\cup[/itex]B'.

    The proof is started, but I don't understand what it is saying
    A is open in B implies A = O[itex]_{B}[/itex][itex]\cap[/itex]B for some open set O[itex]_{B}[/itex] in X.
    O[itex]_{B}[/itex] means O subscript B.

    What does "for some open set O[itex]_{B}[/itex] in X" mean? What is O[itex]_{B}[/itex] doing here? I thought A is already open? why do you need to introduce O[itex]_{B}[/itex] and take intersection? can't you just say A is open?
  13. Oct 28, 2011 #12


    User Avatar
    Science Advisor

    presumably, your topology is defined on X, not B. in the absence of other information an open set in B (under the relative topology) is DEFINED as:

    O∩B, where O is an open set in X.

    for example, the set (1/2,4) is open in the usual topology (collection of open sets) for R.

    but it is NOT an open set in [0,1], instead we have to consider the open set (1/2,1] (and yes, it's confusing that (1/2,1] is open in [0,1] but NOT open in R).
  14. Oct 28, 2011 #13
    Yes, I see what you are saying, so when I say an open set, I have to refer back to X, so the reader won't confused thinking that it is in B? But isn't open in B the same thing as open in X, since B[itex]\subset[/itex]X.

    I mean, they are kind of different since X is bigger than B. But open in B is also open in X, right?
  15. Oct 28, 2011 #14


    User Avatar
    Science Advisor

    no. the reason is, B might not be an open set (it might have "boundary points"). so if an open set O in X "crosses B's boundary", taking O∩B will result in a set open IN B, but not in X.

    look at my example again. the point 1 is a boundary point of [0,1], so when we take the open interval surrounding some point near 1, it might go "outside the boundary", and we have to chop the part that goes past 1 off. but that gives us just a half-open interval in R, which isn't open (in R).

    in other words, sets aren't "open" or "closed" all by themselves, openness or closedness isn't an intrinsic property of a set. whether or not a set is open or closed (or neither, or both) depends on:

    1) the set itself
    2) the space the set is IN
    3) the collection of open sets IN THE SPACE the set is in.

    "open in [0,1]" and "open in R" are two different things.
  16. Oct 29, 2011 #15
    yessss, that makes sense to me.

    What exactly is an open set, what is its role in all this? I have read it in Rudin and Wiki.
    It's saying...

    say, we are in some space E, we have a point y≠x such that d(x,y)<ε. Another way is to say that every open ball B(x,ε) is completely contained in E.
    Isn't that just the definition of interior point? What's the difference between open set and open ball in 2 dimensions? I know we use open ball to prove something, and open set is just a set.
    Last edited: Oct 29, 2011
  17. Oct 29, 2011 #16


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    There are several ways to define it. In the context of metric spaces, I like to define "closed" first (E is closed if the limit of every convergent sequence in E is in E). Then you can prove that for all [itex]E\subset X[/itex] (where X is the metric space), the following statements are equivalent:

    (a) [itex]E^c[/itex] is closed.
    (b) For each [itex]x\in E[/itex], there's an r>0 such that [itex]B(x,r)\subset E[/itex].
    (c) For each [itex]x\in E[/itex], there's an open ball B such that [itex]x\in B\subset E[/itex].
    (d) E is a union of open balls.

    Then you can define open by saying that a set [itex]E\subset X[/itex] is said to be open if it satisfies the equivalent conditions of this theorem. (If you haven't defined closed first, you can just drop (a) from the list).

    You're saying that if [itex]y\in B(x,\varepsilon)[/itex], then...what? E is open? I don't understand what you're trying to do.

    If you're trying to define "open", then the statement is "for all x in X, every open ball B(x,ε) is contained in E".

    A set is open if and only if every one of its members is an interior point. That's part (b) of the theorem.

    See (d) above. Note that it implies that every open ball is an open set.

    Because of the theorem above, you can replace "open ball" with "open set" in most interesting statements about metric spaces, if you want to. For example, consider the statement "x is a limit of the sequence [itex]\langle x_n\rangle[/itex] if every open ball around x contains all but a finite number of terms of [itex]\langle x_n\rangle[/itex]." It's easy to prove that this statement is equivalent to "x is a limit of the sequence [itex]\langle x_n\rangle[/itex] if every open set that contains x contains all but a finite number of terms of [itex]\langle x_n\rangle[/itex]."

    I prefer to use open sets rather than open balls in definitions and theorems, because that way most of what I do remains valid in the context of topological spaces, where there are open sets, but no such thing as an open ball. (A topological space is essentially just a set X together with a specification of what subsets of X we're going to call "open". The specification must however ensure that the sets that end up being called "open" have most of the properties of open sets in metric spaces).
    Last edited: Oct 29, 2011
  18. Oct 29, 2011 #17
    wow, that was such a long post.
    When you say an open set is a union of open balls. How do you actually write that in proof?
    For all x [itex]\in[/itex] X, there is a ε>0, such that B(x,r) is completely contained in E.

    Does this look good?
  19. Oct 29, 2011 #18


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You may not have to write it out, but if you do, you can say something like this: There exist a natural number n, points [itex]x_1,\dots,x_n[/itex] in X, and non-negative real numbers [itex]r_1,\dots,r_n[/itex], such that [itex]E=\bigcup_{k=1}^n B(x_k,r_k)[/itex]. This way of saying it is good too: There exists a set [itex]\{B_i|i\in I\}[/itex] of open balls in X such that [itex]E=\bigcup_{i\in I} B_i[/itex].

    Yes (except for the fact that you accidentally typed ε in one place and r in the other). The word "completely" seems unnecessary. I prefer to say that B(x,r) is a subset of E, or that E contains B(x,r).
  20. Oct 29, 2011 #19


    User Avatar
    Science Advisor

    the basic idea underlying all of this goes something like this:

    suppose we have a large set, which we will call "X".

    now, if that's all the structure we have, X is just a big amorphous blob, which doesn't help us navigate it very well.

    in particular, it doesn't help us know which functions f:X→X are "friendly" and well-behaved, and which functions are unpredictable.

    so we want to decide on a notion of some kind of "special" set, that helps us decide if we're "here" or "there", we want to be able to distingusih different collections of points, somehow.

    now, one way, is just to arbitrarily name a family of sets, and call it special. there are just two rules "special sets" have to follow:

    1) the union of any number of "special" sets is "special" (this will allow us to create bigger "special sets" from smaller ones). we also require that every element of X be in "some" special set, so the forces the entirety of X to also be "special".

    2) the intersection of any two "special" sets is also "special" (this means, that if we take a finite intersection, we get a "special" set).

    why only "finite" intersections? well, our guiding example, is unions of open intervals. suppose i consider the following example:

    the intersection of all intervals (a-1/n,a+1/n). well, that gives just the closed interval [a,a] (a single point). so...in allowing infinite intersections, we've somehow changed the "character" of our intervals, to where we suddenly got a hard boundary.

    now, there are a LOT of ways to do this, for a particular set X, since big sets have a LOT of subsets. so, in order to give our idea of "specialness" something of a more geometric flavor, we introduce the idea of measuring the distance between two points in X. such a way of measuring distance is called a metric.

    there are some rules we want metrics to obey:

    the distance between two points should be a real number (a distance should be a "magnitude", and we decided some time ago, that real numbers capture this idea well).

    the distance from x to itself should always be 0 (and if y isn't x, the distance isn't 0).

    the distance from x to anywhere is never negative.

    if the distance to y from x is A, the distance from x to y should also be A.

    "diagonals are short-cuts" : if the distance from x to y is A, and the distance from y to z is B, then the distance from x to z is ≤ A+B (for somewhat obvious reasons this has the "official" name of "the triangle inequality").

    if we have some notion of "distance" then we can make a more interesting definition of "special":

    for a positive real number ε, call a set B an ε-ball centered at x, if B = {y in X: d(x,y) < ε}. obviously the idea here is that we want all points "within ε" of x. then we call a set "special" if and only if, it is a union of ε-balls (with different ε's and different x's at the centers, that's ok).

    this generalizes the idea of "open interval", for two real numbers, define d(x,y) = |y-x|. this is a perfectly good "distance" function (it's the one we normally use), and for an open interval (a,b), we can take ε = b-a, and our center to be x = (b-a)/2. so we have a (b-a)-ball centered at (b-a)/2.

    it gets more interesting in 2 dimensions. then, we define d((x,y),(u,v)) to be:

    √[(x-u)2+(y-v)2] (this is the pythagorean theorem in disguise).

    then, an ε-ball centered at (x,y) is the set B = {(u,v) : (x-u)2 + (y-v)2 < ε2}, which is an open disk of radius ε, centered at (x,y).

    if you have looked closely, you will see that the difference between a "special" set, and a "anti-special" set is closely related to the difference between "<" and "≤" in the real numbers. that is "<" always gives us "a little more room", but "≤" declares a hard and fast boundary. and it is precisely this peculiarity of order on the reals, that we want to use to guide us in deciding the difference between "near" and "far", in an arbitrary (we can call it a space now) X.

    ("special" sets are usually called "open" sets, and a collection of open sets on X, is called a topology (study of space) on X).
    Last edited: Oct 29, 2011
  21. Oct 29, 2011 #20
    thanks a lot, Deveno.
    To prove an open ball B(x,r) is also closed.
    Is it ok to start like this?
    Let p be a limit point of B(x,r). If p[itex]\notin[/itex]B(x,r), then, p[itex]\in[/itex]B[itex]^{c}[/itex](x,r).

    Where I said "let p be a limit point of B(x,r)." I though limit point only existed in closed balls, but B(x,r) denotes open ball, so how can there be a limit point?

    Edit: actually this prove is for ultrametric, maybe that's why it works.
    Last edited: Oct 29, 2011
  22. Oct 29, 2011 #21


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Open balls are usually not closed. For example, in ℝ with the standard metric, no open balls are closed. So you have to consider some "weird" disconnected space to find an open ball that's closed.

    Regarding your suggested start of a proof, you need to consider the possibility that your B(x,r) doesn't have any limit points. (Consider the set of integers with the metric d defined by d(n,m)=|n-m| for all integers n,m). If it doesn't, you can't say "let p be a limit point of B(x,r)". But it's obviously true that any point that's not a member of B(x,r) is a member of its complement.

    You may need to look at the definition of "limit point" again. In ℝ with the standard metric, all x with |x|≤1 are limit points of B(0,1).

    OK, I just looked up "ultrametric" on Wikipedia and I was redirected to "ultrametric space". Are you dealing with an ultrametric space?
  23. Oct 29, 2011 #22
    hey, Fredrik. I figured it out. Yes, this is the ultrametric space. Thanks, just wanted to know I am thinking right.

    For the standard metric. If I have a closed ball, is the interior point same the limit point? I mean the definition of interior point is, open ball B(x,r) is contained in the space E, or another way of saying that is, ALL of the points in the ball is in E. While limit point only requires that you have a point different from x that is contained in E.

    In a sense, interior point has a stricter requirement than limit point, right? can I call interior point a limit point in closed ball?
    Last edited: Oct 29, 2011
  24. Oct 30, 2011 #23
    Why is limit point called a limit point? does it have to do with limits? I know if you talk intervals on a real line in 1-d, you can talk convergence.
    But when we talk about 2-d, like open balls, why are we calling it limit point, even the definition of a limit point does not mention anything about convergence, it just says you can another point in the open ball.
  25. Oct 30, 2011 #24


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I don't know if you mean that we're talking about metric spaces again, or if you mean that we're talking about the standard metric on a set that has a standard metric.

    Consider ℝ with the standard metric. [0,1] is a closed ball. 0 is a limit point but not an interior point.

    That definition is clearly incomplete.

    You are really sloppy with your definitions. If you have understood the definition, why are you writing down incomplete versions of it?

    Again, incomplete.

    x is a limit point of E if every open ball around x contains a y in E such that y≠x.

    x is an interior point of E if there's an open ball around x that's a subset of E.

    Not in general. Consider the set of integers with the metric defined by d(n,m)=|n-m|. {n:|n-0|≤1/2} is a closed ball around 0. 0 is an interior point of that set, but not a limit point.

    Yes. x is a limit point of a set E if and only if there's a sequence [itex]\langle x_n\rangle[/itex] such that [itex]x_n\rightarrow x[/itex] and every [itex]x_n\neq x[/itex]. (To prove that the first statement implies the second, choose [itex]x_n\in B(x,1/n)-\{x\}[/itex] for each n. The converse follows immediately from the definition of [itex]x_n\rightarrow x[/itex]).

    By the way, different books use different terms. Limit points are also called "cluster points", and "accumulation points".
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook