- #1

mr_coffee

- 1,629

- 1

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.

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.