Relations Problem 2


Proof: Let (a,b) and (c,d) be elements of \(\mathbb{Z}^2\). Suppose that \((a,b) \ll (c,d)\) and \((c,d) \ll (a,b)\).

By the definition of \(\ll\), \((a,b) \ll (c,d)\) means that \(a < c\) or else \(a=c\) and \(b \leq d\). Similarly \((c,d) \ll (a,b)\) means that \(c < a\) or else \(c=a\) and \(d \leq b\).

There are four cases:

  1. \(a < c\) and \(c < a\)
  2. \(a < c\), and also \(c=a\) and \(d \leq b\).
  3. \(a=c\) and \(b \leq d\), and also \(c < a\)
  4. \(a=c\) and \(b \leq d\), and also \(c=a\) and \(d \leq b\).

Of these four cases, the first three are internally inconsistent. So the only viable possibility is the fourth case, i.e. \(a=c\) and \(b \leq d\), and also \(c=a\) and \(d \leq b\).

We know that \(a=c\). Since \(b \leq d\) and \(d \leq b\), we also have that \(b=d\). So (a,b)=(c,d), which is what we needed to show.


At the start of your proof, did you declare your 2D point variables and state your assumptions? Did you actually state the conclusion (a,b)=(c,d) at the end of the proof?

Did you handle all four cases?