Thread: Set Theory - Total vs Partial Orderings

1. 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?

2. 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 or ( $x_1=x_2$ and ( $y_1 < y_2$ or ( $y_1 = y_2$ and $z_1 < z_2$))).

3. 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.

4. 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 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)$.

5. 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?

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

$(x_1,y_1,z_1)<(x_2,y_2,z_2)$ iff $x_1 or ( $x_1=x_2$ and ( $y_1 < y_2$ or ( $y_1 = y_2$ and $z_1 < z_2$))).

6. 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?

7. 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.

8. 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.

9. Re: Set Theory - Total vs Partial Orderings

Originally Posted by Deveno
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

10. 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.

Originally Posted by vandrop
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
Then you run into the same problems as in post #4.

11. 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.