- #1
mr_coffee
- 1,629
- 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 that's incorrect, nay help would be great.
Thanks.
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 that's incorrect, nay help would be great.
Thanks.