how to prove that a relation is antisymmetric?

1.4k Views Asked by At

I have this question that I didn't know how to prove it and need your help. $R$ is a transitive and not reflexive relation on $A$. Prove that $R$ is antisymmetric.

I tried to apply the definition of the transitive and reflexive and antisymmetric but I didn't get any result.

and thank you in advance for your help

1

There are 1 best solutions below

0
On BEST ANSWER

Do you mean "irreflexive" instead of "not reflexive"?

  • A relation is reflexive if $\forall x\in A, xRx$.

  • It's irreflexive if $\forall x\in A, \neg (xRx)$.

  • However, if it's not reflexive, you only know that $\exists x \in A, \neg(xRx)$.


I ask, because the result you have to prove is wrong.

Take a relation on the set $A=\{x,y,z\}$ with

$\neg (xRx), \neg(yRx),\neg(zRx),xRy, yRy,zRy,xRz,yRz,zRz$

That is, for $(a,b) \in A^2$, $aRb$ is true whenever $b\neq x$.

You may represent $R$ by the following table

$$\begin{matrix} & x & y & z \\ x & F & T & T \\ y & F & T & T \\ z & F & T & T \\ \end{matrix}$$

Then $R$ is transitive, but is neither reflexive nor irreflexive, and is not antisymmetric since you have $yRz$ and $zRy$ but not $y=z$.

It's transitive because for $(a,b,c)\in A^3$, if $aRb$ and $bRc$, then necessarily $c\neq x$, so $aRc$ is certainly true.


However, if you assume that $R$ is irreflexive, you can conclude, since by transitivity you have that if $aRb$ and $bRa$, then $aRa$, which is always false, hence one of $aRb$ or $bRa$ is always false, and the implication $aRb \wedge bRa \implies a=b$ is thus vacuously true.