Thread: 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?

You can compare ordered triples lexicographically as follows:

iff or ( and ( or ( and ))).

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.

The lexicographic order is total, but if you define if regardless of and , then the resulting order is not total. Indeed, if , then the following three statements are all false: , and .

If you define nonstrict order if , then it would not be antisymmetric: if , then and , but .

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:

iff or ( and ( or ( and ))).

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?

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.

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.

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?

iff

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?

iff

Then you run into the same problems as in post #4.

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.