Results 1 to 5 of 5

Math Help - Discrete Relations

  1. #1
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1

    Discrete Relations

    Relations can be composed just as functions are composed (for instance g~ o~ f).. note that the "o" is meant to be the "of" symbol but didn't know how to do it in latex.

    For each of the following below, either prove or provide a counterexample:

    a.) If R is reflexive and if S is reflexive, then S~o~R is reflexive.

    b.) If R is symmetric and S is symmetric, then S~o~R is symmetric.

    c.) If R is transitive and S is transitive, then S~o~R is transitive.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1
    Quote Originally Posted by fifthrapiers View Post
    Relations can be composed just as functions are composed (for instance g~ o~ f).. note that the "o" is meant to be the "of" symbol but didn't know how to do it in latex.
    For each of the following below, either prove or provide a counterexample:
    a.) If R is reflexive and if S is reflexive, then S~o~R is reflexive.
    b.) If R is symmetric and S is symmetric, then S~o~R is symmetric.
    c.) If R is transitive and S is transitive, then S~o~R is transitive.
    We assume that these are all relations on the same set.
    Recall that (x,y) \in g \circ f \Leftrightarrow \quad \left( {\exists z} \right)\left[ {(x,z) \in f \wedge (z,y) \in g} \right]

    For (a) \left( {\forall z} \right)\left[ {\left( {z,z} \right) \in f \wedge (z,z) \in g} \right] \Rightarrow \left[ {(z,z) \in g \circ f} \right]

    Consider f = \left\{ {\left( {a,b} \right),\left( {b,a} \right)} \right\},\,\,g = \left\{ {\left( {b,c} \right),\left( {c,b} \right)} \right\}\,\mbox{ but }\,g \circ f = \left\{ {\left( {a,c} \right)} \right\}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1
    Quote Originally Posted by Plato View Post
    We assume that these are all relations on the same set.
    Recall that (x,y) \in g \circ f \Leftrightarrow \quad \left( {\exists z} \right)\left[ {(x,z) \in f \wedge (z,y) \in g} \right]

    For (a) \left( {\forall z} \right)\left[ {\left( {z,z} \right) \in f \wedge (z,z) \in g} \right] \Rightarrow \left[ {(z,z) \in g \circ f} \right]

    Consider f = \left\{ {\left( {a,b} \right),\left( {b,a} \right)} \right\},\,\,g = \left\{ {\left( {b,c} \right),\left( {c,b} \right)} \right\}\,\mbox{ but }\,g \circ f = \left\{ {\left( {a,c} \right)} \right\}.
    I forgot to add that we let R and S be binary relations on the set A. Not sure if this changes it.

    I'm assuming that, based on your results, S\circ R still wouldn't be reflexive.

    For b, showing if its symmetric,

    Suppose A = \{1,2,3\}, \mbox{then} R = \{1,2\}, \{2,1\}, \{1,3\}, \{3,1\}, \{2,3\}, \{3,2\}. Also, S would also equal that if they're both symmetrical. So then the composition of R and S would be symmetrical?

    And for c, transitivity is a little harder since we know if A = B, and B = C, then A = C. So I'd have to set up 3 different subsets? Perhaps drawing digraphs would help?

    Thanks Plato.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1
    No I proved the if each of R & S is reflexive then RoS is reflexive.

    The example shows that if each of R & S is symmetric then RoS need not be.

    You can use a similar example to disprove part c.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1
    Quote Originally Posted by Plato View Post
    We assume that these are all relations on the same set.
    Recall that (x,y) \in g \circ f \Leftrightarrow \quad \left( {\exists z} \right)\left[ {(x,z) \in f \wedge (z,y) \in g} \right]

    For (a) \left( {\forall z} \right)\left[ {\left( {z,z} \right) \in f \wedge (z,z) \in g} \right] \Rightarrow \left[ {(z,z) \in g \circ f} \right]

    Consider f = \left\{ {\left( {a,b} \right),\left( {b,a} \right)} \right\},\,\,g = \left\{ {\left( {b,c} \right),\left( {c,b} \right)} \right\}\,\mbox{ but }\,g \circ f = \left\{ {\left( {a,c} \right)} \right\}.
    Ahh I see why I was confused.

    For (a) \left( {\forall z} \right)\left[ {\left( {z,z} \right) \in f \wedge (z,z) \in g} \right] \Rightarrow \left[ {(z,z) \in g \circ f} \right]

    That's for a, and then you did b too, which was

    Consider f = \left\{ {\left( {a,b} \right),\left( {b,a} \right)} \right\},\,\,g = \left\{ {\left( {b,c} \right),\left( {c,b} \right)} \right\}\,\mbox{ but }\,g \circ f = \left\{ {\left( {a,c} \right)} \right\}.

    I thought the above was for part a, and I knew that that wasn't symmetrical, not reflexive. Ok, got it.
    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: November 13th 2011, 01:20 PM
  2. Replies: 1
    Last Post: September 19th 2011, 02:09 PM
  3. Discrete Math Relations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 24th 2009, 07:38 PM
  4. Relations help!!
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 27th 2008, 07:19 PM
  5. Relations
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 26th 2008, 01:18 PM

Search Tags


/mathhelpforum @mathhelpforum