Results 1 to 5 of 5

Math Help - Relations Question

  1. #1
    dre
    dre is offline
    Newbie
    Joined
    Dec 2009
    Posts
    1

    Relations Question

    Let A be the set {a, b, c, d, e, 1, 2, 3, 4, 5, x, y, z, w}

    How many different reflexive relations are there and how many different symmetric relations are there? I know the total would be 2^196 because of the power set rule but how can I figure out how many reflexive and symmetric relations there are?

    Please help
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1582
    Awards
    1
    Quote Originally Posted by dre View Post
    Let A be the set {a, b, c, d, e, 1, 2, 3, 4, 5, x, y, z, w}
    How many different reflexive relations are there and how many different symmetric relations are there?
    The set of pairs \Delta _A  = \left\{ {\left( {\alpha ,\alpha } \right):\alpha  \in A} \right\} is known a the diagonal from the table of ordered pairs.
    There are 14^2 pairs in that table so \left| {\Delta _A } \right| = 14
    Therefore there are 14^2-14 off diagonal pairs.
    Any reflexive relation on A must contain {\Delta _A }.
    So any reflexive relation is the union of {\Delta _A } with any subset of off diagonal pairs.
    How many of those are there?

    Any symmetric relation on A, \mathcal{S}, has the property that \mathcal{S}=\mathcal{S}^{-1}.
    There are \frac{(14)(15)}{2} pairs either on the diagonal or above it.
    Any subset of those pairs corresponds to a symmetric relation.
    Just take that subset and unite it with its inverse.
    How many are there?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241
    Quote Originally Posted by Plato View Post
    The set of pairs \Delta _A = \left\{ {\left( {\alpha ,\alpha } \right):\alpha \in A} \right\} is known a the diagonal from the table of ordered pairs.
    There are 14^2 pairs in that table so \left| {\Delta _A } \right| = 14
    Therefore there are 14^2-14 off diagonal pairs.
    Any reflexive relation on A must contain {\Delta _A }.
    So any reflexive relation is the union of {\Delta _A } with any subset of off diagonal pairs.
    How many of those are there?

    Any symmetric relation on A, \mathcal{S}, has the property that \mathcal{S}=\mathcal{S}^{-1}.
    There are \frac{(14)(15)}{2} pairs either on the diagonal or above it.
    Any subset of those pairs corresponds to a symmetric relation.
    Just take that subset and unite it with its inverse.
    How many are there?
    Thank you for this explanation, but I am still confused about something in ROSEN: I understand that the number of subsets from A with n elements is 2^n, I can see that the diagonal of the cartesian product will contain n elements and that all other elements will total n^2 - n. But I don't see why the number of reflexive relations equal 2^q where q = n^2 - n ? Why isn't the number of reflexive relations just equal to 2^r where r = n^2?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1582
    Awards
    1
    Quote Originally Posted by oldguynewstudent View Post
    Thank you for this explanation, but I am still confused about something in ROSEN: I understand that the number of subsets from A with n elements is 2^n, I can see that the diagonal of the cartesian product will contain n elements and that all other elements will total n^2 - n. But I don't see why the number of reflexive relations equal 2^q where q = n^2 - n ? Why isn't the number of reflexive relations just equal to 2^r where r = n^2?
    If you will give me the exact reference in Rosen's book I will look at it.

    As for your other concern, if |A|=n then how many subsets of A\times A contain \Delta_A?

    Do you understand that \left|(A\times A)\setminus \Delta_A\right|=n^2-n?

    How many subsets of A\times A\setminus \Delta_A are there?

    Uniting any of those with \Delta_A we get a reflexive relation on A
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    I think I get it now

    Quote Originally Posted by Plato View Post
    If you will give me the exact reference in Rosen's book I will look at it.

    As for your other concern, if |A|=n then how many subsets of A\times A contain \Delta_A?

    Do you understand that \left|(A\times A)\setminus \Delta_A\right|=n^2-n?

    How many subsets of A\times A\setminus \Delta_A are there?

    Uniting any of those with \Delta_A we get a reflexive relation on A
    Thanks for your patience. We skipped the combinatorics chapters. The reference is on p 525 6th edition, example 16. So because there are n members in the diagonal we have by the product rule these n combined with the n - 1 other (rows or columns in the matrix) to give n(n - 1) ways to combine. Then we raise 2 to that power to get the number of relations.

    I still have to think it over further to solidify the concept. But at least now I can follow the reasoning.

    Happy Holidays!
    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, 12:20 PM
  2. Replies: 1
    Last Post: September 19th 2011, 01:09 PM
  3. Relations Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 18th 2009, 07:06 AM
  4. Relations question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 16th 2009, 11:03 PM
  5. Relations question....please help!!!
    Posted in the Business Math Forum
    Replies: 1
    Last Post: December 5th 2007, 09:50 AM

Search Tags


/mathhelpforum @mathhelpforum