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?

  • 1
    $\begingroup$ You first ask about proving trichotomy, but then we don't see that again. Your last paragraph is about asymmetry and irreflexivity, but is really about how you define equality. Equality of $(a,b)$ with itself is automatic as a basic property of equality. What is your question? $\endgroup$ – Ross Millikan Aug 7 '17 at 1:06
  • $\begingroup$ There shouldn't be confusion with equality, when you define ordered pair, it is immediately verified that $(a,b) = (c,d)$ if and only if $a = c$ and $b = d$ and has nothing to do with dictionary order. Then to verify trichotomy of dictionary order, you use trichotomy on each component breaking it into cases. $\endgroup$ – Ennar Aug 7 '17 at 1:15
  • $\begingroup$ Thank you for these comments, and I apologize for the confusion. As I understood it, proving both asymmetry and irreflexivity was akin to proving trichotomy. I also was confused on whether the idea of a relation defining an order was distinct from the structure of the ordered pairs since that relation itself only defines <, but not =. If I understand this correctly now, proving trichotomy would boil down to assuming all possible relationships amongst the elements a, b, c, and d and proving that only one of <, > or = hold. Is this correct? $\endgroup$ – Matt.P Aug 7 '17 at 1:24
  • $\begingroup$ Proving asymmetry and irreflexivity is akin to proving trichotomy because it simplifies verification. Please see what I mean at Wikipedia. Since you don't have any other definition of equality, this is simply equality of sets. $\endgroup$ – Ennar Aug 7 '17 at 1:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.