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!

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

    HallsofIvy

    User Avatar
    Staff Emeritus
    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?

     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Let A be A set of n Distinct Elements.
  1. Elements of a set. (Replies: 9)

Loading...