Results 1 to 2 of 2

Thread: More Relations on A

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    10

    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?
    Last edited by dwsmith; Nov 20th 2010 at 11:46 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    Quote Originally Posted by dwsmith View Post
    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.)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Relations and Functions - Inverse Relations Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 13th 2011, 12:20 PM
  2. Replies: 1
    Last Post: Sep 19th 2011, 01:09 PM
  3. Relations help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Feb 19th 2009, 03:18 PM
  4. help with relations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Dec 6th 2008, 03:56 PM
  5. Can someone please help me with relations?
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: Mar 21st 2008, 07:28 PM

/mathhelpforum @mathhelpforum