1. Limited time only! Sign up for a free 30min personal 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!

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.

  2. jcsd
  3. Dec 6, 2006 #2


    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