Still doing relation properties exercises, I'm now trying what seems to be a somewhat different type: now the relation is over a cartesian product $\mathbb{N} \times \mathbb{N}$.
I normally have no problems determining if it is reflexive or symmetric, but for the other ones that require more complex proofs I keep on hitting dead ends:
Over $\mathbb{N} \times \mathbb{N}$, $(a,b)R(c,d) \iff a -c = b -d$. Determine the properties of the relation $R$.
Reflexive
Yes. We have to prove that $\forall a,b \in \mathbb{N} : (a,b)R(a,b)$
$$(a,b)R(a,b)$$
$$a - a = b - b$$
$$0 = 0$$
Symmetric
Yes. We have to prove that $\forall a,b,c,d \in \mathbb{N} : (a,b)R(c,d) \implies (c,d)R(a,b)$:
$$(a,b)R(c,d)$$
$$a - c = b - d$$
$$-(a - c) = -(b - d)$$
$$c - a = d - b$$
$$(c,d)R(a,b)$$
Antisymmetric
We have to prove that $\forall a,b,c,d \in \mathbb{N} : (a,b)R(c,d) \land (c,d)R(a,b) \implies (a,b) = (c,d)$:
$$(a,b)R(c,d) \land (c,d)R(a,b)$$
$$(a - c = b - d) \land (c - a = d - b)$$
$$(a - c = b - d) \land [-(c - a) = -(d - b)]$$
$$(a - c = b - d) \land (a - c = b - d)$$
$$(a - c = b - d)$$
If I can prove that $a = c$ and $b = d$ I would be done - however, it seems I've hit a wall here. Maybe that's a hint that it isn't antisymmetric?
Transitive
We have to prove that $\forall a,b,c,d,e,f \in \mathbb{N} : (a,b)R(c,d) \land (c,d)R(e,f) \implies (a,b)R(e,f)$:
$$(a,b)R(c,d) \land (c,d)R(e,f)$$
$$(a - c = b - d) \land (c - e = d - f)$$
$$a - d + f - e = b - c + e - f$$
I was hoping to end up with $a - e = b - f$, but I can't get rid of those $c$ and $d$ in the equation.
Total
We have to prove that $\forall a,b,c,d \in \mathbb{N} \times \mathbb{N} : (a,b)R(c,d) \lor (c,d)R(a,b)$.
Let's suppose that $(a,b)\not R(c,d) \land (c,d)\not R(a,b)$.
$$(a,b)\not R(c,d) \land (c,d)\not R(a,b)$$
$$(a - c \not = b - d) \land (c - a \not = d - b)$$
$$(a - c \not = b - d) \land (a - c \not = b - d)$$
$$(a - c \not = b - d)$$
However, that is false, because clearly if you pass $(1,1)R(1,1)$, you would have $1 - 1 \not = 1 - 1$. Since this is a contradiction, our supposition is wrong, and therefore the relation is indeed total.
As you can observe, I require feedback for the antisymmetric and transitive proofs. Additionally the total proof is a bit fishy to me. What do you think?
For antisymmetry: Perhaps you are "stuck" because you can't establish antisymmetry. What you can do is show, by providing a counterexample, that antisymmetry fails:
E.g. Note that we have $\;(5, 4)\, R\, (3, 2)\;\land \;(3, 2) \,R \,(5, 4),\;$ but $\,(5, 4) \neq (3,2).\;$
For transitivity, you have:
Now we just need a little algebra, by isolating $c-d$ in each of the two equations above, and equating them. That way we can rid ourselves of both $c$ and $d$.
We have $$(a - c = b - d \iff {\bf c - d = a - b})\; \land (c - e = d - f \iff {\bf c - d = e - f})$$
So $$\;a-b = e-f\; \iff \;a - e = b-f$$ Hence $(a, b) R (e, f)$, as desired.
For totality, consider the ordered pairs $(5, 4), \;(1, 4)$. Then $5 - 1 \neq 4 - 4$, and $1 - 5 \neq 4 - 4$. Hence we have a counterexample in which it is not the case that $(5, 4) R (1, 4)$, nor is it the case that $(1, 4) R (5, 4)$.