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: Dictionary order and least upper bound property

  1. Jun 29, 2011 #1
    1. The problem statement, all variables and given/known data
    Does [itex][0,1] \times [0,1][/itex] in the dictionary order have the least upper bound property?

    2. Relevant equations
    Dictionary Order. (on [itex]\mathbb{R}^2[/itex]) Let [itex]x , y \in \mathbb{R}^2[/itex] such that [itex]x=(x_1 , x_2)[/itex] and [itex]y = (y_1 , y_2)[/itex]. We say that [itex]x < y[/itex] if [itex]x_1 < y_1[/itex], or if [itex]x_1 = y_1[/itex] and [itex]x_2 < y_2[/itex].

    Def'n. An ordered set [itex]A[/itex] is said to have the least upper bound property if every nonempty subset [itex]A_0 \subseteq A[/itex] that is bounded has a least upper bound.

    Assume that the real line has the least upper bound property.

    3. The attempt at a solution

    I'm not sure if I am proving this correctly. Here's my proof.

    I want to show that every subset [itex]A_0 \subseteq [0,1] \times [0,1][/itex] that is nonempty and bounded has the lub property. Suppose that [itex]\mathbb{R}[/itex] has the lub property. Let [itex]A_0[/itex] be an nonempty subset of [itex][0,1] \times [0,1][/itex]. Since [itex][0,1] \times [0,1][/itex] is bounded, it follows that every subset of [itex][0,1] \times [0,1][/itex] is bounded. We will consider two forms of [itex]A_0[/itex], that is, when either [itex]A_0 = [i,j] \times [k, \ell][/itex], or [itex]A_0 = (i,j) \times (k, \ell)[/itex], where [itex]0 \leq i, j, k, \ell \leq 1[/itex].

    If [itex]A_0 = [i,j] \times [k, \ell][/itex], then [itex]\forall x \in A_0[/itex], we can always find a least upper bound, say [itex]y[/itex] by letting [itex]y=x[/itex]. So that case is settled.

    Instead, suppose that [itex]A_0 = (i,j) \times (k, \ell)[/itex]. Then [itex]\forall x \in A_0[/itex], we can still always find a least upper bound which we will again call [itex]y[/itex] such that [itex]y = (y_1 , y_2)[/itex] by letting [itex]y_1 = j[/itex] and [itex]y_2 = k[/itex].

    In a similar manner, we can show that subsets that have both closed and open ends (e.g. [itex](i,j] \times (k, \ell][/itex]) always have a least upper bound.

    Therefore I have shown that every subset of [itex][0,1] \times [0,1][/itex] that is nonempty and bounded has the lub property and therefore the set [itex][0,1] \times [0,1][/itex] has the lub property.

    How does this look?
  2. jcsd
  3. Jun 29, 2011 #2


    User Avatar
    Science Advisor
    Homework Helper

    Hi Samuelb88! :smile:

    But you're only proving it for open and closed squares

    what about open and closed triangles, and more complicated regions?
  4. Jun 29, 2011 #3
    Okay, given [itex]A_0[/itex] [itex]\exists i, j, k, \ell \in \mathbb{N}[/itex] such that [itex]A_0 \subseteq [i,j] \times [k,\ell][/itex]. In words, I'm claiming that there exists a box with dimensions [itex]|j-i|[/itex] and [itex]|\ell - k|[/itex] such that the region of [itex]A_0[/itex] lies entirely inside the box. Would this help? I'm not allowed to use the concept of a border of a region so I'm not sure how to explain how we can fit the box about either an open or closed region so that the border of the box coincides with the "border" of the region (By "border" of the region, I mean the line that encloses it, whether it be dashed (open region) or solid (closed region)).

    What if I let [itex]b \in [i,j] \times [k,\ell][/itex] such that [itex]b = (k,\ell)[/itex]. Then [itex]b[/itex] is an upperbound in the dictionary order for the region of [itex]A_0[/itex]. Now look at the set of all such upper bounds of the region [itex]A_0[/itex], that is, [itex]\{ b \in [i,j] \times [k,\ell] : \forall x \in A_0 \, \, x \leq b\}[/itex]. Denote this set of upper bounds by [itex]U_{A_0}[/itex]. Now in [itex]U_{A_0}[/itex] there will be a an element, say [itex]b_0[/itex], such that [itex]b_0 \leq b[/itex] [itex]\forall b \in [i,j] \times [k,\ell][/itex] in the dictionary order. Basically I want to let [itex]b_0 = \min(U_{A_0})[/itex], but I am not sure if I'm using the min function correctly. At any rate, this [itex]b_0[/itex] is the lub of the set [itex]A_0[/itex]. Therefore (since [itex]A_0[/itex] was arbitrary) each subset of [itex][0,1] \times [0,1][/itex] has the lub property in the dictionary order and therefore by our proposition stated in my original post, [itex][0,1] \times [0,1][/itex] has the lub property in the dictionary order.
    Last edited: Jun 29, 2011
  5. Jun 29, 2011 #4
    Well, of course such a box exists, take

    [tex][i,j]\times[k,l]=[0,1]\times [0,1][/tex]

    but that won't help us.

    Given a set A0. Can you prove that

    [tex]\{x~\vert~\exists y:~(x,y)\in A_0\}[/tex]

    has an upper bound? I.e., when you project the set onto the x-axis, does it have an upper bound then?
  6. Jun 29, 2011 #5

    If I am understanding your question correctly, then [itex]x=1[/itex] is one such upper bound for the set [itex]\{ x : \exists y : (x,y) \in A_0 \}[/itex], which I will denote as [itex]U_{A_0}[/itex]. So then can I look at the set of all upper bounds of [itex]U_{A_0}[/itex] and take the [itex]\min(U_{A_0})[/itex] to show that it has a least upper bound?
  7. Jun 29, 2011 #6
    Indeed, so [itex]U_{A_0}[/itex] has a least upper bound [itex]x_0[/itex]. Can you use this to find an upper bound of [itex]A_0[/itex]?? Maybe look at [itex]\{y~\vert~(x_0,y)\in A_0\}[/itex].
  8. Jun 29, 2011 #7
    Okay, letting [itex]x_0[/itex] be the least upper bound of [itex]U_{A_0}[/itex]. I can play the same game with the set [itex]V = \{ y : (x_0 , y) \in A_0 \}[/itex]. I know that one such upper bound of the set [itex]V[/itex] is [itex]y=1[/itex]. Thus looking at the set of all upper bounds of [itex]V[/itex], I will again take the minimum of that set and have found an upper bound, say [itex]y_0[/itex]. Thus I have found an upper bound of [itex]A_0[/itex], that is [itex](x_0 , y_0)[/itex].
  9. Jun 29, 2011 #8
    And can you show that [itex](x_0,y_0)[/itex] is the least upper bound?
  10. Jun 29, 2011 #9
    Well it seems to me from our construction of [itex]x_0[/itex] and [itex]y_0[/itex] that [itex](x_0,y_0)[/itex] is the least upper bound of [itex]A_0[/itex] is it not?
  11. Jun 29, 2011 #10
    Well, if it's obvious to you, then the proof is finished! :smile:
  12. Jun 29, 2011 #11
    Great! Thanks, micromass! Always appreciated. :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook