# Proving a relation is anti-symmetric and transitive

$P$ is a binary relation. $P ⊆ \mathbb{R}^2$. $P = \{(x,y): y = |x|\}$.

As I understand for relation to be transitive: $(a,b) \in P$ and $(b,c) \in P$ then $(a,c \in P)$ for this particular relation we can take $(a,b) = (-2,2)$ and $(b,c) = (2,2)$, then $(a,c) = (-2,2) \in P$, so it means that relation is transitive. Is this correct?

I'm not quite sure about antisymmetric property: for it to work for different a,b both $(a,b)$ and $(b,a)$ can't $\notin P$. For example $(-2,2) \in P$, but $(2,-2) \notin$ P. Which proves that relation is antisymmetric. Is this correct?

Update: for anti-symmetric:

By definition $\forall a,b \in P, aPb \land bPa => a=b$

let's assume that $(a,b) \in P$. Then $(b,a) \in P <=> a=b$

Relation is anti-symmetric.

Your method incorrect. You need to prove the transitivity for every $a,b,c$ satisfying $(a,b),(b,c)\in P$. You can't choose a sample and work on that. Similarly, you need to prove the antisymmetry for every $a\ne b$ satisfying $(a,b)\in P$. You can't choose a sample and work on that. In general about mathematics, you can't take a sample and work on that to prove a statement. Mathematics far from experimental.

Let me prove the transitivity for you. Let $a,b,c\in \Bbb{R}$ satisfying $(a,b),(b,c)\in P$, i.e. $a=|b|,b=|c|$.

Observe that $b=|c|\ge0$. Thus, $a=|b|=b$. So, $|c|=b=a$. Thus, $(a,c)\in P$. So, the relation is transitive.

Can you imitate this proof to work on the antisymmetry?

You can disprove a universal statement by a single counter-example, but to prove a universal statement you need much more than a few examples.   You need a guarantee that counter-examples do not exist.

The nature of a proposed counter example to a universal claim is found by negating the statement (using dual negation rules).

Reflexivity: $\forall x: x=\lvert x\rvert \\ \neg \exists x: x\neq x$

• Witness that $-1\neq \lvert -1\rvert$, so the relation is not reflexive.

Symmetry: $\forall x\,\forall y: \big(y=\lvert x\rvert ~\to~ x=\lvert y\rvert\big)\\ \neg\,\exists x\,\exists y: \big(y=\lvert x\rvert \,\wedge\, x\neq \lvert y\rvert\big)$

• Witness that $2=\lvert-2\rvert$ but $-2\neq \lvert 2\rvert$, so the relation is not symmetric.

Transitivity: $\forall x\,\forall y\,\forall z: \big(y=\lvert x\rvert\,\wedge\, z=\lvert y\rvert ~\to~ z=\lvert x\rvert\big) \\ \neg \exists x\,\exists y\,\exists z:\big(y=\lvert x\rvert\,\wedge\, z=\lvert y\rvert\,\wedge\, z\neq \lvert x\rvert\big)$

• If any $y=\lvert x\rvert$ and $z=\lvert y\rvert$ then by substitution $z=\lVert x\rVert$, proving the relation is transitive (because a counter example is impossible).

Anti-symmetry: $\forall x\,\forall y:\big(y=\lvert x\rvert\,\wedge\, x=\lvert y\rvert ~\to~ x=y\big) \\ \neg \exists x\,\exists y:\big(y=\lvert x\rvert\,\wedge\, x=\lvert y\rvert \,\wedge\, x\neq y\big)$

• So... can you either find a counter-example, or demonstrate that the premise is necessarily true?