So I am to determine the number of both symmetric and reflexive relations on an n-element set. I've read various explanations (yes, Number of relations that are both symmetric and reflexive too) but I still don't quite get it.
If the relations are to be both symmetric and reflexive, why isn't the answer the same as for the reflexive? I mean – when we have some 25-element set, represent it as 5×5 grid, no other points can be symmetric and reflexive at the same time than the diagonal from (1,1) to (5,5). We can choose many symmetric ones apart from those too, but neither will be reflexive.
What do I not understand?
Best Answer
Your assumption that the number of (symmetric and reflexive) relations equals the number of (purely reflexive) relations is wrong.
Let me explain: Say, $A=\{1,2\}$
Reflexive relations on $A$ are
$\{(1,1),(2,2)\}$,
$\{(1,1),(2,2),(1,2)\}$,
$\{(1,1),(2,2),(2,1)\}$,
$\{(1,1),(2,2),(1,2),(2,1)\}$
Thus the number of reflexive relations equals 4 ($2^{n(n-1)}$ in general).
But the number of reflexive and symmetric relations equals $2^{\frac{n(n-1)}{2}}$ as is already described in the link you've provided.
The number of reflexive relations is always greater than the number of reflexive and symmetric relations.
And in your example, it's not just the principle diagonal. You've neglected the symmetric pairs that can exist along with the ordered pairs necessary to make the relation a reflexive one, i.e $\{(1,1),(2,2),(3,3),(4,4),(5,5),(1,2),(2,1)\}$ is also both reflexive and symmetric.