Answer to Question #146304 in Discrete Mathematics for Promise Omiponle

Question

(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)?

Answer 1

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)$.