Results 1 to 10 of 10

Math Help - Well Ordering

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    306

    Well Ordering

    Define a well-ordering relation R on the set of rationals: S = \{x = \frac{3^n \times 7^m}{11^t} \text{for integers n, m, t} \ge 1\}

    So using the definition of well-ordering from wikipedia, "a well-order relation on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering"

    In other words we need to ensure that the relation is transitive, antisymmetric and total and that every non empty subset of S has a least element.

    I am stuck on how to define such a relation... any help would be appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,539
    Thanks
    778
    Question: why does regular order \le on S not work?

    One option that does work is the following. Let us define T as a set of triples \{(n,m,t)\in\mathbb{Z}^3\mid n,m,t\ge 1\} and f:T\to S as a function f(n,m,t)=(3^n\times 7^m)/11^t. Since 3, 7, and 11 are pairwise relatively prime, f is a bijection. Thus, any well-order R' on T gives rise to a well-order R=\{(f(w_1),f(w_2))\mid w_1,w_2\in T, (w_1,w_2)\in R'\} on S.

    Now, one can take the lexicographical order on T (see the remark about well-orders in the link).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2009
    Posts
    306
    Thanks emakarov.

    Say we had S = \{\frac{3 \times 7}{11}, \frac{3^2 \times 7}{11}, \frac{3^3 \times 7}{11}, \frac{3 \times 7^2}{11}\}<br />

    So a well ordered relation on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering.

    So (x, y) \in R if x \le y

    R = \{\left(\frac{3 \times 7}{11}, \frac{3^2 \times 7}{11}\right), \left(\frac{3 \times 7}{11}, \frac{3^3 \times 7}{11}\right), \left(\frac{3 \times 7}{11}, \frac{3 \times 7^2}{11}\right), \left(\frac{3^2 \times 7}{11}, \frac{3^3 \times 7}{11}\right), \left(\frac{3^2 \times 7}{11}, \frac{3 \times 7^2}{11}\right), \left(\frac{3^3 \times 7}{11}, \frac{3 \times 7^2}{11}\right), \left(\frac{3 \times 7}{11}, \frac{3 \times 7}{11}\right), \left(\frac{3^2 \times 7}{11}, \frac{3^2 \times 7}{11}\right), \left(\frac{3^3 \times 7}{11}, \frac{3^3 \times 7}{11}\right), \left(\frac{3 \times 7^2}{11}, \frac{3 \times 7^2}{11}\right)\}

    R is a total order on S since it is transitive, total and antisymmetric.

    But what I don't get is "with the property that every non-empty subset of S has a least element in this ordering", this has nothing to do with the relation R whatsoever?? If we take any non-empty subset of S then the subset must has a least element, what's the point of creating a relation that is a total order on S?

    Thanks again.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,539
    Thanks
    778
    Hint: the definition of "least" involves R.

    To get a better idea, I recommend finding out why the regular order <= is not a well-order on S.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Apr 2009
    Posts
    306
    Hmm sorry I've thought about it and I still can't really understand why.

    I still don't get why we have a define a relation that is a total order on S because if we take any non-empty set of S it must have a least element anyway.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,539
    Thanks
    778
    Hmm sorry I've thought about it and I still can't really understand why.
    If you think that the standard order is a well-order on S, then what is the least element in S?

    If we take any non-empty subset of S then the subset must has a least element, what's the point of creating a relation that is a total order on S?
    I see two things that need clarification. First, not every set with a total order (or partial order) has the least element. Second, the definition of "least" is relative to the order. One can have a regular \le-least element or an R-least element for some completely different order relation R.

    Therefore, if S does not have the least element with respect to the standard order \le, in order to make S a well-ordered set, one has to come up with some other order R so that S, as well as every proper subset of S, have the R-least element.

    By the way, a total order on a finite set is always a well-order. This is because for each element x, either x is the least, or you can find a smaller element; however, you can't find smaller and smaller elements forever because the set is finite. So, your example with finite S and R above does not show everything that is going on.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Sep 2010
    Posts
    47
    So you are saying that the well-ordering R is:
    R = \{\left(\frac{3 \times 7}{11}, \frac{3^2 \times 7}{11}\right), \left(\frac{3 \times 7}{11}, \frac{3^3 \times 7}{11}\right), \left(\frac{3 \times 7}{11}, \frac{3 \times 7^2}{11}\right), \left(\frac{3^2 \times 7}{11}, \frac{3^3 \times 7}{11}\right), \left(\frac{3^2 \times 7}{11}, \frac{3 \times 7^2}{11}\right), \left(\frac{3^3 \times 7}{11}, \frac{3 \times 7^2}{11}\right), \left(\frac{3 \times 7}{11}, \frac{3 \times 7}{11}\right), \left(\frac{3^2 \times 7}{11}, \frac{3^2 \times 7}{11}\right), \left(\frac{3^3 \times 7}{11}, \frac{3^3 \times 7}{11}\right), \left(\frac{3 \times 7^2}{11}, \frac{3 \times 7^2}{11}\right)\}
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,539
    Thanks
    778
    Quote Originally Posted by Nguyen View Post
    So you are saying that the well-ordering R is:
    \textstyle R = \{\left(\frac{3 \times 7}{11}, \frac{3^2 \times 7}{11}\right), \left(\frac{3 \times 7}{11}, \frac{3^3 \times 7}{11}\right), \left(\frac{3 \times 7}{11}, \frac{3 \times 7^2}{11}\right), \left(\frac{3^2 \times 7}{11}, \frac{3^3 \times 7}{11}\right), \left(\frac{3^2 \times 7}{11}, \frac{3 \times 7^2}{11}\right), \left(\frac{3^3 \times 7}{11}, \frac{3 \times 7^2}{11}\right), \left(\frac{3 \times 7}{11}, \frac{3 \times 7}{11}\right), \left(\frac{3^2 \times 7}{11}, \frac{3^2 \times 7}{11}\right), \left(\frac{3^3 \times 7}{11}, \frac{3^3 \times 7}{11}\right), \left(\frac{3 \times 7^2}{11}, \frac{3 \times 7^2}{11}\right)\}
    Well-ordering on what set? On the finite S consisting of four elements, yes. As I said, any total order on that finite set is a well-order. On the original infinite S, no. It is not even a total order.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Sep 2010
    Posts
    47
    Quote Originally Posted by emakarov View Post
    Well-ordering on what set? On the finite S consisting of four elements, yes. As I said, any total order on that finite set is a well-order. On the original infinite S, no. It is not even a total order.
    I mean what are you saying that the well-ordering relation R on the set of rationals: S = \{x = \frac{3^n \times 7^m}{11^t} \text{for integers n, m, t} \ge 1\} is???

    I don't seem to understand what answer you are giving usagi_killer.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,539
    Thanks
    778
    As for the answer to the original question, namely, a well-order on the infinite set S, I described it in my first reply. What we've been discussing after that was why the standard order is not a well-order on S, which implies the need for a different order R.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help with well ordering principle
    Posted in the Discrete Math Forum
    Replies: 17
    Last Post: May 23rd 2011, 02:40 PM
  2. well ordering principle
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: August 18th 2009, 02:18 PM
  3. well-ordering
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 10th 2009, 10:24 AM
  4. Well-Ordering
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 15th 2008, 08:13 AM
  5. well ordering
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 17th 2008, 10:16 AM

Search Tags


/mathhelpforum @mathhelpforum