# Thread: More Relations on A

1. ## More Relations on A

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

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

Let $aR^2b$ in R. Therefore, $(a,x)\in R \ \mbox{and} \ (x,b)\in R$. By the symmetric hypothesis, $(b,x)\in R$. Thus, we have $(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 $R^2$ is symmetric.

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

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

Let $(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 $(a,b)\in R \ \mbox{and} \ (b,a)\in R$ but R is asymmetric. Therefore, we have reached a contradiction and $R\cap R^{-1}=\phi$.

Are this all logically correct?

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

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

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

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

Let $(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 $(a,b)\in R \ \mbox{and} \ (b,a)\in R$ but R is asymmetric. Therefore, we have reached a contradiction and $R\cap R^{-1}=\phi$.
(Hint: $\emptyset$ is typed \emptyset.)