# Set Theory - Total vs Partial Orderings

• Oct 11th 2011, 04:52 PM
vandrop
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?
• Oct 12th 2011, 03:06 AM
emakarov
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$))).
• Oct 12th 2011, 06:14 AM
vandrop
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.
• Oct 12th 2011, 06:38 AM
emakarov
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)$.
• Oct 12th 2011, 07:07 AM
vandrop
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
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$))).

• Oct 12th 2011, 07:20 AM
emakarov
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.

Quote:

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

Quote:

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?
• Oct 12th 2011, 07:47 AM
vandrop
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.
• Oct 12th 2011, 07:53 AM
Deveno
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.
• Oct 12th 2011, 07:58 AM
vandrop
Re: Set Theory - Total vs Partial Orderings
Quote:

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
• Oct 12th 2011, 08:20 AM
emakarov
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
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.
• Oct 12th 2011, 08:23 AM
Deveno
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.