# Thread: More Relations on A

1. ## More Relations on A

Def:
R is irreflexive iff. $\displaystyle a\nsim a \ \forall a\in A$
Not irreflexive iff. $\displaystyle \exists a\in A \ni a\sim a$
R is asymmetric iff. if $\displaystyle a\sim b$, then $\displaystyle b\nsim a$
Not asymmetric iff. $\displaystyle \exists a\sim b$ and $\displaystyle b\sim a$
R is anti-symmetric iff. if $\displaystyle a\sim b \ \mbox{and} b\sim a$, then $\displaystyle a=b$.
Not anti-symmetric iff. $\displaystyle \exists a\sim b \ \mbox{and} \ b\sim a \ \mbox{and} \ a\neq b$
$\displaystyle \bigtriangleup ={(a,a)|a\in A}$

Proofs:
R is symmetric implies that $\displaystyle R^2$ is symmetric.

Let $\displaystyle aR^2b$ in R. Therefore, $\displaystyle (a,x)\in R \ \mbox{and} \ (x,b)\in R$. By the symmetric hypothesis, $\displaystyle (b,x)\in R$. Thus, we have $\displaystyle (b,x)\in R \ \mbox{and} \ (x,a)\in R$. We now have a path of length from b to x to a in R and $\displaystyle R^2$ is symmetric.

If R is asymmetric, then $\displaystyle R\cap R^{-1}=\phi$

By contraction: Suppose R is asymmetric and $\displaystyle R\cap R^{-1}\neq\phi$

Let $\displaystyle (a,b)\in R\cap R^{-1}\rightarrow (a,b)\in R \ \mbox{and} \ (a,b)\in R^{-1}\leftrightarrow (b,a)\in R$. Now, we have $\displaystyle (a,b)\in R \ \mbox{and} \ (b,a)\in R$ but R is asymmetric. Therefore, we have reached a contradiction and $\displaystyle R\cap R^{-1}=\phi$.

Are this all logically correct?

2. Originally Posted by dwsmith
R is symmetric implies that $\displaystyle R^2$ is symmetric.

Let $\displaystyle aR^2b$ in R. Therefore, $\displaystyle (a,x)\in R \ \mbox{and} \ (x,b)\in R$ for some x in A. By the symmetric hypothesis, $\displaystyle (b,x)\in R$ and $\displaystyle (x,a)\in R$. We now have a path of length 2 from b to x to a in R and therefore $\displaystyle R^2$ is symmetric.

If R is asymmetric, then $\displaystyle R\cap R^{-1}=\phi$

By contraction: Suppose R is asymmetric and $\displaystyle R\cap R^{-1}\neq\phi$

Let $\displaystyle (a,b)\in R\cap R^{-1}\rightarrow (a,b)\in R \ \mbox{and} \ (a,b)\in R^{-1}\leftrightarrow (b,a)\in R$. Now, we have $\displaystyle (a,b)\in R \ \mbox{and} \ (b,a)\in R$ but R is asymmetric. Therefore, we have reached a contradiction and $\displaystyle R\cap R^{-1}=\phi$.
(Hint: $\displaystyle \emptyset$ is typed \emptyset.)