[Math] Proving a relation is anti-symmetric and transitive

discrete mathematicsrelations

$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?

Have I answered questions correctly?

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.

Best Answer

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?
Related Question