Solution to (a) Find the number of relations on the set S={a, b, c, d, e}? (b) … - Sikademy
Author Image

Archangel Macsika

(a) Find the number of relations on the set S={a, b, c, d, e}? (b) How many relations are there on the set S={a, b, c, d, e} that contain (a, a) and (b, b)?

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

We shall use the fact that the number of all subsets of n-element set is 2^n.


(a) Let S=\{a,b,c,d,e\}. By defenition, a biniry relation \rho on a set S is a subset of a Cartesian square S\times S. Since |S\times S|=5\cdot 5=25, there are 2^{25}=33,554,432 binary relations on the set S=\{a,b,c,d,e\}.


(b) Let us find the number of binary relations \rho on the set S=\{a,b,c,d,e\} that contain (a, a) and (b, b). Since elements of a relation \rho\setminus\{(a,a),(b,b)\} can be arbitrary elements of S\times S\setminus\{(a,a),(b,b)\}, the number of binary relation on S that contain (a, a) and (b, b) is equal to the number of binary relations R\subset S\times S\setminus\{(a,a),(b,b)\}. Since |S\times S\setminus\{(a,a),(b,b)\}|=25-2=23 , there are 2^{23}=8,388,608 binary relations on the set S=\{a,b,c,d,e\} that contain (a, a) and (b, b).


Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-3534-qpid-2233