Prove that a relation R on A is antisymmetric if and only if $R∘R^{-1} \subseteq I_A$

209 Views Asked by At

If: I tried to take some element $(a,b)∈R∘R^{-1}$ and show that we have some $c∈A$ s.t. $(a,c)∈R^{-1}$ and $(c,b)∈R$, and use the fact that $R∘R^{-1} \subseteq I_A$ which gives that $a=b$. I then tried to show that $(b,c)∈R$ with $b≠c$ and find a contradiction but couldn't get anything.

I didn't get to the only if yet because I've been very stuck. Any help is appreciated.

Also note we have our standard definition of antisymmetry: A relation $R$ on a set $A$ is said to be antisymmetric if, for all $x∈A$ and $y∈A$, whenever $(x,y)∈R$ and $(y,x)∈R$, then $x=y$.

1

There are 1 best solutions below

3
On

I think you really want to prove the correct

The relation $R$ on $A$ is antisymmetric iff $R \cap R^{-1} \subseteq I_A$.

So not composition of relations, but intersection!

To show the original statement is false, let $R$ be $\le$ on $A=\mathbb{N}$, say (classically antisymmetric). Then $(1,2) \in R$, $(3,1) \in R^{-1}$ so $(3,2) \in R \circ R^{-1}$ but $(3,2) \notin I_A$.

The corrected statement is really a restatement of the definition of antisymmetricity of $R$, try it.