Results 1 to 6 of 6

Math Help - Proof with Supremum, Infimum, and Well ordering principle

  1. #1
    Newbie
    Joined
    Nov 2010
    Posts
    3

    Proof with Supremum, Infimum, and Well ordering principle

    1. The problem statement, all variables and given/known data

    We just started learning about supremums and infimums in my math proofs class. I am having trouble with the following question:

    Let x, y be real numbers with y - x > 1. Prove that there exists an integer n such that x < n < y. Hint--use the well ordering principle.


    2. Relevant equations

    Well-ordering principle: a nonempty set S of real numbers is said to be well-ordered if every nonempty subset of S has a least element. This is proved using induction.

    Upper bound: a real number m is called an upper bound of S if for every s in S, s <= m.
    Lower bound: a real number m is called an lower bound of S if for every s in S, m <= s.
    Maximum: If m is an upper bound of S and m is in S, then we call m the maximum of S.
    Minimum: If m is a lower bound of S and m is in S, then we call m the minimum of S.

    Supremum: least upper bound
    Infimum: greatest lower bound


    3. The attempt at a solution

    I am unsure of how to incorporate the well ordering principle into my proof. I was thinking of writing something like, "y - x > 1 <==> y > x + 1 <==> x < x + 1 < y. So there is an integer z such that x <= z < x + 1 or x < z <= x + 1." And then show the rest with ceiling and floor... but I'm sure this is incorrect, as we are supposed to use the well ordering principle.

    Please let me know if extra clarification is needed.

    Any help would be GREATLY appreciated!

    Thanks in advance,

    Kendra
    Last edited by magic88; November 24th 2010 at 10:19 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771
    Thank you for providing all relevant information.

    Consider \{n\in\mathbb{Z}\mid y\le n\} (where \mathbb{Z} is the set of integers). If you know that this set is nonempty, then you can apply the well-ordering principle to it. To show that it is nonempty, assume the contrary and consider the supremum of all integers.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    If you have proved that the floor function exists, then this proof is easy.
    Notice that \left\lfloor x \right\rfloor  \leqslant x < \left\lfloor x \right\rfloor  + 1 \leqslant x + 1 < y.

    The integer \left\lfloor x \right\rfloor  + 1 is between x~\&~y.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2010
    Posts
    3
    Thanks so much for your quick replies!

    Plato--Thank you very much. I really wish I could use the floor function in my proof! It's good to know that I was on to something when I thought of using it



    emakarov--

    I don't think I fully understand why to use the set {z \epsilon Z | y <= z}. I did the proof, though:
    We will prove that set A = {z \epsilon Z | y <= z} (where y is a real number) is nonempty. Assume to the contrary that A is empty. Then for every z \epsilon Z, z > y. Then y is the supremum of Z. This is a contradiction because Z has no largest element, and thus does not have any upper bounds (or least upper bounds), and so the supremum of Z does not exist. Thus A cannot be empty, so A is nonempty.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771
    Then for every z \epsilon Z, z > y.
    You mean, z < y.

    Then y is the supremum of Z.
    Strictly speaking, it only follows that y is some upper bound of Z, not necessarily the least upper bound. However, it follows from the axioms of reals that a nonempty set with an upper bound has the least upper bound. (I am not sure whether reals were introduced axiomatically in your course and, if yes, what axioms were used. For example, the fact above is one of the axioms in Wikipedia.)

    This is a contradiction because Z has no largest element, and thus does not have any upper bounds (or least upper bounds),
    If a set does not have the largest element, it does not follow in general that it does not have an upper bound or supremum. For example, \{1-1/n\mid n\in\mathbb{Z},n>0\} does not have a maximum, but its supremum is 1.

    You probably could say that the existence of an upper bound of \mathbb{Z} leads to a contradiction without an explanation, but here it is if you need it. Let y_0 be the supremum of \mathbb{Z}. By the definition of supremum, y_0-1 is not an upper bound, so there exists a z\in\mathbb{Z} such that z>y_0-1. Integers are closed under addition, so z+1 is still an integer. However, z+1>y_0, a contradiction.

    I don't think I fully understand why to use the set {z \epsilon Z | y <= z}.
    Let A=\{z\in\mathbb{Z}\mid y\le z\}. You must have been shown in class that a nonempty subset of integers bounded from below is well-ordered. Once you prove that A is nonempty, you know it has the least element, say z_0. In particular, z_0 - 1\notin A, i.e., z_0 - 1 < y and so z_0 < y + 1. Thus, x + 1 < y\le z_0 < y + 1, so x < z_0 - 1 < y.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2010
    Posts
    3
    Quote Originally Posted by emakarov View Post
    You mean, z < y.
    Oops, yes. Sorry, I suppose that was a typo.

    We will prove that set A = {z \epsilon Z | y <= z} (where y is a real number) is nonempty. Assume to the contrary that A is empty. Then for every z \epsilon Z, z < y. Then y is some upper bound of Z. By Completeness, since Z has an upper bound, Z has a supremum, a contradiction. [Thanks so much for your proof to show Z has no supremum!] Thus, A is nonempty.

    Since A is a nonempty subset of integers bounded below by y, we know it has a least element, say a. Since a is a least element, a-1 is not an element of A, i.e. a-1<y and so a<y+1. Thus x+1<a \le y+1, so x<a-1<y. Since a-1 is an integer, there exists an integer such that x < n < y.

    Thank you so much for your help. This make so much more sense now!
    Last edited by magic88; November 25th 2010 at 12:00 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Infimum and supremum
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: February 9th 2010, 04:57 PM
  2. [SOLVED] supremum and infimum proof
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: November 6th 2009, 12:25 PM
  3. analysis : infimum/supremum proof
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: February 23rd 2009, 07:19 PM
  4. infimum and supremum proof
    Posted in the Calculus Forum
    Replies: 1
    Last Post: October 5th 2008, 02:57 PM
  5. Supremum and Infimum
    Posted in the Calculus Forum
    Replies: 3
    Last Post: September 10th 2008, 09:49 AM

Search Tags


/mathhelpforum @mathhelpforum