1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Binary relations and sets

  1. Feb 27, 2009 #1
    1. The problem statement, all variables and given/known data
    Let A = {a, b, c} be a set with 3 elements.
    (a) How many binary relations are there on A?
    (b) How many binary relations on A are reflexive?
    (c) How many relations on A are symmetric?
    (d) How many binary relations on A are both symmetric and reflexive?

    2. Relevant equations


    3. The attempt at a solution
    a) There are 2^9 = 512 binary relations on A.

    b) Therere are 2^(9-3)=8 relations that are reflexive.

    c) Here's where I got a bit stuck, not sure if this one's right.
    (i) Sets with elements of the form (x,x) 2^3 = 8
    (ii) Pairs with elements of the form (x,y) (y,x) (where x /= y): (9-3)/2 = 3. Sets with these elements: 2^3 = 8.
    Is that right? And how do I get the number of relations which are symmetric from that? Is it just 8x8?

    d) Completely confused, I don't get any of this part.

    Any help would be appreciated!
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. Feb 27, 2009 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Draw a three by three grid hence having 9 pairs. You are good for the first one. There are nine possible choices of {true,false} to fill in for those 9 pairs. So 2^9=512 looks ok. But I start losing you at b). If it's reflexive then the three pairs along the diagonal must all be true. That leaves you only 9-3=6 pairs to fill in with your choice of {true,false}. But 2^6 is not equal to 8.
     
  4. Feb 27, 2009 #3
    Sorry, typo. I meant 2^6=64 reflexive relations, but I'm still not sure about (c). Is the way I did it right? Because it doesn't feel right...
     
  5. Feb 27, 2009 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes, I think. If it's symmetric you get to make an arbitrary choice of {true,false} along the diagonal (x,x) and (x,y) for y<x. That's 6 choices. 2^6=64. Right. If it's reflexive and symmetric you lose the choice along the diagonal. Now you only have three free choices to make, right?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Binary relations and sets
  1. Binary Relations (Replies: 11)

  2. Binary Relations (Replies: 2)

Loading...