Question

(a)To find the number of relations on the set \(\{ a,b,c,d\} \).

(b)To find the number of relations on the set \(\{ a,b,c,d\} \) contain the pair \((a,a)\).

Short answer

(a)The number of relations on the set\(\{ a,b,c,d\} \)is 65536.

(b)The number of relations on the set \(\{ a,b,c,d\} \) contain the pair \((a,a)\) is 32768.

Step-by-step solution

 Given

A relation on a set \(A\) is a subset of \(A \times A\).

The Concept of inverse relation

Concept used: A relation on a set\(A\)is a subset of\(A \times A\).

Because\(A \times A\)has\({n^2}\)elements when\(A\)has\(n\)elements and a set with\(m\)elements has\({2^m}\)subsets.

Then the set\(A \times A\)has\({2^{{n^2}}}\)subsets.

Thus, there are\({2^{{n^2}}}\)relations on a set with\(n\)elements

Determine the relation

A relation on a set\(A\)is a subset of\(A \times A\).

Let \({\mathop{\rm set}\nolimits} A = \{ a,b,c,d\} \) here \(n = 4\)

\(A \times A = \{ a,b,c,d\} \times \{ a,b,c,d\} ,{n^2} = {4^2} = 16\)elements

\( = \left\{ {\begin{array}{*{20}{l}}{(a,a),(a,b),(a,c),(a,d)}\\{(b,a),(b,b),(b,c),(b,d)}\\{(c,a),(c,b),(c,c),(c,d)}\\{(d,a),(d,b),(d,c),(d,d)}\end{array}} \right\}\)

Set \(A \times A\) with 16 elements has \({2^{16}} = 65536\) subsets.

\(\therefore \) The number of relations on the set \(\{ a,b,c,d\} \) is 65536.

Determine the relation

A relation on a set\(A\)is a subset of\(A \times A\).

Let\({\mathop{\rm set}\nolimits} A = \{ a,b,c,d\} \)here\(n = 4\)

\(A \times A = \{ a,b,c,d\} \times \{ a,b,c,d\} ,{n^2} = {4^2} = 16\)elements

\( = \left\{ {\begin{array}{*{20}{l}}{(a,a),(a,b),(a,c),(a,d)}\\{(b,a),(b,b),(b,c),(b,d)}\\{(c,a),(c,b),(c,c),(c,d)}\\{(d,a),(d,b),(d,c),(d,d)}\end{array}} \right\}\)

So, number of subsets that contain\((a,a)\)is\({2^{{n^2} - 1}}\)

Here\({2^{{4^2} - 1}} = {2^{15}} = 32768\)

If we always include\((a,a)\)remaining\({n^2} - 1\)ordered pairs of the type\((x,y)\)in\(A \times A\)

Therefore, the number of relations on the set \(\{ a,b,c,d\} \) contain the pair \((a,a)\) is 32768.