In few days I'm having an exam from Formal Logic and Set Theory and would like to confirm if my method of proving partial orders is correct. The task:
For $(n, m), (p, q) \in \mathbb{N}_{+}^{2}$, $$(n, m) \preceq (p, q) \Leftrightarrow (n, m) = (p, q) \vee (n < p \wedge n - m \leq p - q).$$ Prove that $\preceq$ is a partial order.
Here is my idea for the proof:
1) Reflexive
(a, b) $ \preceq $ (a, b)
$(a, b) = (a, b) \vee (a < a \wedge (a - b) \leq (a - b))$
The first part is true, so it's reflexive.
2) Antisymmetric
$ (a, b) \preceq (c, d) \wedge (c, d) \preceq (a, b) \Rightarrow (a, b) = (c, d) $
My idea was to write above condition using actual rules given in the task:
$ [(a, b) = (c, d) \vee ((a < c) \wedge (a - b) \leq (c - d))] \wedge [(c, d) = (a, b) \vee ((c < a) \wedge (c - d) \leq (a - b))] $
If we mark every part in brackets divided with $ \vee $ with letters p, q, r, s, we can see that distribution of p and r will give us:
$ [(a, b) = (c, d) \wedge (c, d) = (a, b))] $
And that's what we were looking for. So antisymmetry is true.
3) Transitive
$ (a, b) \preceq (c, d) \wedge (c, d) \preceq (e, f) \Rightarrow (a, b) \preceq (e, f) $
I used the similar procedure to what I did above. Mainly I wrote the conditions:
$ [(a, b) = (c, d) \vee ((a < c) \wedge (a - b) \leq (c - d))] \wedge [(c, d) = (e, f) \vee ((c < e) \wedge (c - d) \leq (e - f))] $
I once again used p, q, r, s notation and distributed. Again, distribution of p and r gives us:
$ [(a, b) = (c, d) \wedge (c, d) = (e, f)] $
Which should prove the last part, because that's the condition of partial order in the task. Is that the correct way of proving partial orders? I will be very thankful for tips and answers, because they will help me pass the course.
I would use a different approach in your proofs of anti-symmetry and transitivity.
This way, you don't need distribution.
Anti-symmetry. The second branch of the definitions doesn't apply, since that would include $a<c$ and $c<a$, a contradiction.
Thus, you get immediatelly $(a,b) = (c,d)$ (by definition), which is what was to be proven.
Transitivity. It's a similar situation.
If $(a,b) = (c,d)$, then $(a,b) \leq (e,f)$ because $(c,d) \leq (e,f)$; the same happens if $(c,d) = (e,f)$.
So the only non-trivial situation is if $$a<c<e$$ and $$a-b < c-d < e-f,$$ from which it follows that $a < e$ and $a-b< e-f$ (it turns out to be rather trivial too).