Relations Problem 1

Solution

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

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 (e,f)\) means that \(c < e\) or else \(c=e\) and \(d \leq f\).

There are now four cases:

  1. \(a < c\) and \(c < e\): Then \(a < e\). So \((a,b) \ll (e,f)\).
  2. \(a < c\), and also \(c=e\) and \(d \leq f\). Then \(a < e\). So \((a,b) \ll (e,f)\).
  3. \(a=c\) and \(b \leq d\), and also \(c < e\). Then \(a < e\). So \((a,b) \ll (e,f)\).
  4. \(a=c\) and \(b \leq d\), and also \(c=e\) and \(d \leq f\). Then \(a=e\) and \(b \leq f\). So \((a,b) \ll (e,f)\).

In all four cases, \((a,b) \ll (e,f)\), which is what we needed to show.

Self-check

At the start of your proof, did you declare the three points? Did you state the two assumptions \((a,b) \ll (c,d)\) and \((c,d) \ll (e,f)\)?

Did your proof end at \((a,b) \ll (e,f)\)? (A common mistake is to end one step before the conclusion.)

Did the middle of your proof address all four cases? In particular, did you consider cases 2 and 3?

It can be ok to merge two cases together, to shorten the proof. If you did this, does your merged case cover both possibilities? Will it be obvious to the reader that you covered all possibilities?