How many binary relations in a set of 8

[mr_coffee]

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.

 

[AlephZero]

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

 

[FalseFact]

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.