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: How many binary relations in a set of 8

  1. Dec 6, 2006 #1
    Hello everyone. This problem has a few parts, and i'm on the last part and i'm having troubles and im' guessing my way is not the correct method. But here is the question.


    Let A be a set with 8 elements.
    a. how many binary relations are there on A?

    answer: A binary relation is any subset of AxA and AxA has 8^2 = 64 elements. So there are 2^64 binary relations on A.

    b. how many binary relations on A are reflexive?
    There are exactly 8x, so you have 8 of the 64 results of AxA so you have 2^(64-8) = 2^56 reflexive relations.

    c. HOw many binary relations on A are symmetic?
    Form a symmetric relation by a 2 step process:
    1. Pick a set of pairs of elements of the form (a,a) (there are 8 such elements , so 2^8 sets);
    2. Pick a set of pairs of elements of the ofrm (a,b) and (b,a) where a != b (there are (64-8)/2 = 28 such pairs os 2^28 such sets. So the answer by the multiplicaiton rule is 2^8 * 2^28 = 2^36.

    Now this is the one i can't get:
    d. How many binary relations on A are both reflexive and symmetric?
    I was thinking i could add parts c and b, and get
    2^56 + 2^36...but that seems to easy, or am i allowed? I have no idea what process i would go about figuring this out if thats incorrect, nay help would be great.


    Thanks.
     
  2. jcsd
  3. Dec 6, 2006 #2

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    Use a similar counting argument as in c

    d.1 A reflexive relation includes ALL the elements (a,a)
    d.2 Same as c.2
     
  4. Jan 31, 2012 #3
    For a relation to be called as reflexive, it must contain all the pairs (a,a) if a belongs to A. Such 8 pairs are possible over A. And all of those must be included.

    A relation is symmetric if it contains
    a. set of pairs of elements of the form (a,a)--> We have already included all such pairs while selecting reflexive relations. So, here, we don't have any choice.
    b. set of pairs of elements of the ofrm (a,b) and (b,a) where a != b (there are (64-8)/2 = 28 such pairs and hence 2^28 such sets.

    By product rule, it counts to be 1*2^28=2^28.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook