Results 1 to 11 of 11

Math Help - Set Theory - Total vs Partial Orderings

  1. #1
    Newbie
    Joined
    Oct 2011
    Posts
    9

    Set Theory - Total vs Partial Orderings

    This is a sort of applied set theory question. If I create a class of objects (as in programming) defined as Equilateral, which use three parameters - base size, and the x and y coordinates of the base, how can I define a total order for this class?

    EDIT: Also, what is lexicographic ordering in regards to shapes?
    Last edited by vandrop; October 11th 2011 at 06:05 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: Set Theory - Total vs Partial Orderings

    You can compare ordered triples lexicographically as follows:

    (x_1,y_1,z_1)<(x_2,y_2,z_2) iff x_1<x_2 or ( x_1=x_2 and ( y_1 < y_2 or ( y_1 = y_2 and z_1 < z_2))).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2011
    Posts
    9

    Re: Set Theory - Total vs Partial Orderings

    Thanks. But couldn't you also just compare them using only the z components? I realize that what you gave and this are practically the same, but they differ a little and I'm curious as to why.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: Set Theory - Total vs Partial Orderings

    The lexicographic order is total, but if you define (x_1,y_1,z_1)<(x_2,y_2,z_2) if z_1<z_2 regardless of x_i and y_i, then the resulting order is not total. Indeed, if x_1\ne x_2, then the following three statements are all false: (x_1,y,z)<(x_2,y,z), (x_1,y,z)=(x_2,y,z) and (x_2,y,z)<(x_1,y,z).

    If you define nonstrict order (x_1,y_1,z_1)\le(x_2,y_2,z_2) if z_1\le z2, then it would not be antisymmetric: if x_1\ne x_2, then (x_1,y,z)\le (x_2,y,z) and (x_2,y,z)\le (x_1,y,z), but (x_1,y,z)\ne (x_2,y,z).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2011
    Posts
    9

    Re: Set Theory - Total vs Partial Orderings

    Understood, thanks. I still am unclear why this is total though -- wouldn't this imply x-coord of the center of the base of one triangle was less than another, the former would precede the latter? What about a small triangle that is further to the right that a larger triangle?

    Quote Originally Posted by emakarov View Post
    You can compare ordered triples lexicographically as follows:

    (x_1,y_1,z_1)<(x_2,y_2,z_2) iff x_1<x_2 or ( x_1=x_2 and ( y_1 < y_2 or ( y_1 = y_2 and z_1 < z_2))).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: Set Theory - Total vs Partial Orderings

    Your question is unclear. First, you did not say if "x and y coordinates of the base" means the center of the base, the left end, etc. Second, coordinates of the base center and a base length are not sufficient to define a segment unless it is horizontal.

    I still am unclear why this is total though
    By this you mean lexicographic order?

    wouldn't this imply x-coord of the center of the base of one triangle was less than another, the former would precede the latter?
    What exactly do you mean by "this"? Do you mean

    if "the center of the base of one triangle was less than another, then the former would precede the latter"

    or

    "the center of the base of one triangle was less than another, and the former would precede the latter"?

    Finally, how do you order the base length and the coordinates?

    Could you word the question more clearly?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Oct 2011
    Posts
    9

    Re: Set Theory - Total vs Partial Orderings

    I'm just referring directly to the solution you gave in your first reply. Directly after the "iff" you say x1 < x2 OR (....)

    So if x1 < x2 is true, the full iff statement is true.

    But x1 and x2 refer to the x-coords of the bases of two triangles. My question is, if you use the ordering you gave, in your first reply, would a smaller triangle which had an x-coordinate greater than another larger triangle would precede the larger triangle in the ordering? Is this how your ordering works? I'm just trying to figure out a sort of English equivalent to your initial answer.

    EDIT: Sorry if I hadn't specified they were the coordinates of the center of the base, but yes, this is the case.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Set Theory - Total vs Partial Orderings

    a lexicographic ordering might not correspond well to an ordering by "size", or total area, or height, etc.

    think of lexicographic ordering as "dictionary" ordering where the words are alphabetized, except you're using numbers instead of letters.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Oct 2011
    Posts
    9

    Re: Set Theory - Total vs Partial Orderings

    Quote Originally Posted by Deveno View Post
    a lexicographic ordering might not correspond well to an ordering by "size", or total area, or height, etc.

    think of lexicographic ordering as "dictionary" ordering where the words are alphabetized, except you're using numbers instead of letters.
    So... might I order it by y-coords like so?

    (x_1,y_1,z_1)<(x_2,y_2,z_2) iff y_1<y_2
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: Set Theory - Total vs Partial Orderings

    If you order your three numbers like this: (x-coordinate, y-coordinate, base length), then the lexicographic ordering works as follows. Let A and B be the middle of the bases. If A is left of B, then the first triangle is smaller. If A and B are on the same vertical line, but A is lower, then the first triangle is smaller. Finally, if A = B and the first triangle has a smaller base, then the first triangle is smaller. If all three numbers are equal, then the triangles are equal; otherwise, the second triangle is smaller.

    Quote Originally Posted by vandrop View Post
    So... might I order it by y-coords like so?

    (x_1,y_1,z_1)<(x_2,y_2,z_2) iff y_1<y_2
    Then you run into the same problems as in post #4.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Set Theory - Total vs Partial Orderings

    yes, but that's not "total", because if the y-coordinates are the same, you don't know how to assign which one is "bigger".

    a total ordering means one (and only one) of 3 things is always true:

    1) A < B
    2) B < A
    3) A = B

    if you just order by y-coordinates, then (1,0,4) < (2,0,5) is not true (because 0 is not less than 0), and (2,0,5) < (1,0,4) is not true, but neither is (1,0,4) = (2,0,5) true.

    that is, we can't make a "line" with every triangle on it's own unique place in line, we have instead an ordering of "blocks" of triangles (by y-coordinate),

    and each "block" has different triangles who all share the same y-ccordinate, but there's no sub-ordering amongst them.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Compactness Theorem and partial orderings
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 2nd 2011, 01:35 PM
  2. Addition and Multiplication of Well Orderings
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 01:32 AM
  3. Linear Orderings
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 15th 2008, 05:10 AM
  4. partial vs total derivative
    Posted in the Calculus Forum
    Replies: 0
    Last Post: August 26th 2008, 03:42 PM
  5. Equivalence Relations and Partial Orderings
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2007, 11:13 PM

Search Tags


/mathhelpforum @mathhelpforum