Proof that the dictionary order is an order relation

941 Views Asked by At

Say that we have the following relation on Q:

(a,b) < (c,d) if a < c OR a = c and b < d

I want to prove that this is an order relation. I've seen these conditions defined somewhat differently, but going by Rudin, I need to show (i) trichotomy and (ii) transitivity.

I have successfully proven (ii) by using four cases. I'd be very curious if anyone knew another, more elegant way to prove this, but at the moment I'll omit this since I'm fairly confident in my answer. I am somewhat confused on (i), notwithstanding the fact that it appears rather obvious.

So, say we take (a,b) < (c,d). There are two possibilities here: either (1) a < c for any ordering of b and d or (2) a = c and b < d. In case (1), by definition (c,d) < (a,b) cannot hold because c is not greater than or equal to a. In case 2, we also can say that (c,d) < (a,b) doesn't hold because d is not less than b.

Thus, I can easily prove that the relation is asymmetric. I could also establish that it is irreflexive, i.e. that (a,b) < (a,b) doesn't hold because though a = a, b is not less than b. But, using Rudin's terminology, this is somewhat confusing because equality, i.e. (a,b) = (a,b) isn't defined on this relation. So I could prove, for example, that (a,b) < (a,b) and (a,b) > (a,b) certainly don't hold, and that asymmetry doesn't hold (based on the above example), but I can't define a case where two pairs are "equal" because it seems like a jump to define equality.

Could someone clear this up?