Let A be A set of n Distinct Elements.

[nowimpsbball]

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 doesn't 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 don't 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.

 

[Mathdope]

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.

 

[HallsofIvy]

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

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?

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 doesn't 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 don't 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.