Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook