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: Let A be A set of n Distinct Elements.

  1. Jan 25, 2008 #1
    Let A be a set of n distinct elements. There is a one to one correspondence between binary relations on the set A and subsets R<= A x A
    a. Computer the number of binary realtions on A
    b. A binary relation R is said to be symmetric if for every (a,b) in R, (b,a) is also in R. Compute the number of symmetric binary relations on A.
    c. A binary relation R is said to be antisymmetric if for every (a,b) in R (a doesnt equal b), (b,a) is not in R. Compute the number of antisymmetric binary relations on A

    Really no equations to my knowledge, a Discrete Math course.

    I am really having a hard time getting off the ground on this one, and I dont know why...I am thinking/hoping this problem is easier than I am making it out to be...I tend to over think a lot

    Thanks, any hints/suggestions/solutions would be greatly appreciated.
  2. jcsd
  3. Jan 25, 2008 #2
    They are just asking you to compute the number of subsets of A X A in 3 different ways. The first specifiies no condition, the 2nd and 3rd give you some restrictions.
  4. Jan 25, 2008 #3


    User Avatar
    Science Advisor

    You are told that "there is a one to one correspondence between the collection of binary relations and the collection of subsets of A- there are the same number. Okay, do you know a (simple) formula for the number of subsets? If not think about it this way: The empty set has 1 subset: itself. set with exactly one element, {a}, has two subsets: {a} and {}. A set with 2 elements, {a,b}, has {}, {a}, {b}, {b}: four subsets. A set with 3 elements {a, b, c} has.... Instead of listing them all, think of it this way: if we remove c, we have two elements, a, b, left and we know that has 4 subsets. Okay, those subsets are also subsets of {a,b,c}. Any other subset must contain c: and, in fact, is exactly a subset without to which we have added c: there are, again, 4 of those: the set {a,b,c} has 4 subsets that contain c and 4 that do not: it has 4+ 4= 8 subsets. What about {a,b,c,d}? Again, every subset either contains d or does not. Removing d, we have 3 elements left- there are 8 such subsets. Every subset that does contain d, is just one of those that do not contain d, with d added! There are, again, 8 of those: {a,b,c,d} has 8+ 8= 16 elements. Do you see how we are doubling each time?

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook