Results 1 to 3 of 3

Thread: Smallest Symmetric Relation

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    53

    Smallest Symmetric Relation

    I have this question for my homework, and I have absolutely no idea how to prove how a "smallest" relation exist. Any help is appreciated. Below is the question:


    "Let X be any set. Let R be a relation on X. Prove there is a smallest symmetric relation that contains R."
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    22
    Quote Originally Posted by TitaniumX View Post
    I have this question for my homework, and I have absolutely no idea how to prove how a "smallest" relation exist. Any help is appreciated. Below is the question:


    "Let X be any set. Let R be a relation on X. Prove there is a smallest symmetric relation that contains R."
    Let $\displaystyle \mathcal{M}=\left\{\mathcal{R}:\mathcal{R}\text{ is a symmetric relation on }X\text{ and }R\subseteq\mathcal{R}\right\}$. The question is $\displaystyle \bigcap_{M\in\mathcal{M}}M$ a symmetric relation on $\displaystyle X$? It is trivially easy to prove that it's a relation, to see that it's symmetric merely note that if $\displaystyle (x,y)\in\bigcap_{M\in\mathcal{M}}M$ then $\displaystyle (x,y)\in N$ for all $\displaystyle N\in\mathcal{M}$ but since each $\displaystyle N$ is symmetric this implies $\displaystyle (y,x)\in N$ for all $\displaystyle N\in\mathcal{M}$ and thus $\displaystyle (y,x)\in\bigcap_{M\in\mathcal{M}}M$. Now it is clear that $\displaystyle \bigcap_{M\in\mathcal{M}}M\supseteq R$ and it is clear that it's the smallest, for if $\displaystyle R\subseteq K$ is a symmetric relation then $\displaystyle K\in\mathcal{M}\implies \bigcap_{M\in\mathcal{M}}M\subseteq K$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    Alternatively, you can form a relation $\displaystyle R'$ like this: for every $\displaystyle (x,y)\in R$ put $\displaystyle (x,y)$ and $\displaystyle (y,x)$ in $\displaystyle R'$. Then show that $\displaystyle R\subseteq R'$, $\displaystyle R'$ is symmetric, and if any other symmetric relation contains $\displaystyle R$, it contains $\displaystyle R'$ as well.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Relation that is 1-1, reflexive, but not symmetric
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Nov 16th 2011, 01:13 PM
  2. Symmetric Relation question
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Nov 20th 2010, 02:43 AM
  3. Replies: 2
    Last Post: Nov 13th 2010, 07:27 AM
  4. Symmetric relation v.s. symmetric matrix
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Oct 14th 2010, 11:37 PM
  5. Relation, reflexive, symmetric and trasitive
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: Sep 27th 2009, 11:19 AM

Search Tags


/mathhelpforum @mathhelpforum