Question

The number of symmetric relations defined on the set {1, 2, 3, 4} which are not reflexive is _____.

Answer 1

Define symmetric relations: A relation $R$ is symmetric if $(a, b) \in R \implies (b, a) \in R$. A relation is reflexive if $(a, a) \in R$ for all $a$.

Count total relations:

$\text{Total relations} = 2^{n^2} \text{ for } n = 4.$

$\text{Total relations} = 2^{4^2} = 2^{16} = 65536.$

Count reflexive relations: Reflexive pairs: $(1, 1), (2, 2), (3, 3), (4, 4)$ (4 pairs). Remaining symmetric pairs: $(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)$ (6 pairs).

$\text{Total reflexive relations} = 2^6 = 64.$

Count symmetric relations:

$\text{Symmetric relations} = 2^{\binom{n}{2} + n} = 2^{6 + 4} = 2^{10} = 1024.$

Non-reflexive symmetric relations:

$\text{Non-reflexive symmetric relations} = \text{Total symmetric relations} - \text{Reflexive symmetric relations} = 1024 - 64 = 960.$

Thus, the answer is: 960