Results 1 to 3 of 3

Math Help - 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
    21
    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 \mathcal{M}=\left\{\mathcal{R}:\mathcal{R}\text{ is a symmetric relation on }X\text{ and }R\subseteq\mathcal{R}\right\}. The question is \bigcap_{M\in\mathcal{M}}M a symmetric relation on X? It is trivially easy to prove that it's a relation, to see that it's symmetric merely note that if (x,y)\in\bigcap_{M\in\mathcal{M}}M then (x,y)\in N for all N\in\mathcal{M} but since each N is symmetric this implies (y,x)\in N for all N\in\mathcal{M} and thus (y,x)\in\bigcap_{M\in\mathcal{M}}M. Now it is clear that \bigcap_{M\in\mathcal{M}}M\supseteq R and it is clear that it's the smallest, for if R\subseteq K is a symmetric relation then 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,559
    Thanks
    785
    Alternatively, you can form a relation R' like this: for every (x,y)\in R put (x,y) and (y,x) in R'. Then show that R\subseteq R', R' is symmetric, and if any other symmetric relation contains R, it contains 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: November 16th 2011, 02:13 PM
  2. Symmetric Relation question
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 20th 2010, 03:43 AM
  3. Replies: 2
    Last Post: November 13th 2010, 08:27 AM
  4. Symmetric relation v.s. symmetric matrix
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 15th 2010, 12:37 AM
  5. Relation, reflexive, symmetric and trasitive
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: September 27th 2009, 12:19 PM

Search Tags


/mathhelpforum @mathhelpforum