Find the symmetric subsets of $B = \{1,2,3,4\}$

Question

I came across this weird question in a question paper :

$B =\lbrace1,2,3,4\rbrace . \text{ A set } S\subseteq B\times B \text{ is called symmetric set iff, for all x,y } \in S \\ \qquad\qquad\qquad\qquad\qquad\qquad (x,y) \in S \Rightarrow (y,x) \in S $ .

Find the number of symmetric sets of B.

At first , I thought the answer is $4.\quad[(1,1),(2,2),(3,3),(4,4,)]$.

Now the question begs if an empty set "$\emptyset$" can be included to the list?

What is the answer?

Answer 1

Notice there are $16$ elements $(a,b)$.

For every element $(a,b)$ and every Symmetric set $S\subset B\times B$ we have two options: either $(a,b) \in S$ or .... $(a,b) \not \in S$. But if $(a,b) \in S$ then $(b,a) \in S$. And if $(a,b) \not \in S$ then $(b,a) \not \in S$.

If we didn't have the condition of Symmetry we could state that there are $2^{16}$ subsets $M \subset B\times B$ by simply noting that for each subset $M$ and each element $(a,b)$ we have two options and as to whether $(a,b)$ is or is not in $M$ and those there are $2^{16}$ possible subsets that can be constructed by simply going through the $16$ elements and either choosing to put it in or not put it in each subset we construct.

For a symmetric set we can only make the choice an one of the elements $(a,b)$. Once we make the choice whether $(a,b)$ is or is not in $S$ then we have no choice but to make the exact same choice for whether $(b,a)$ is or is not in $S$.

So the number of symmetric sets is $2^k$ where $k$ is the number of distinct elements $(a,b)$ that we are allowed to make distinct choices on.

What is $k$? Well, $k < 16$. But ... how do we count of the $(a,b)$s but then omit the $(b,a)$s?

Well.... There are $16$ $(a,b)$. There are $4$ $(a,b; a = b)$ so there are $16-4 = 12$ $(a,b; a\ne b)$ and there $6=\frac {12}2$ $(a,b; a < b)$ and $6$ $(a,b; a > b)$. And there are $6 + 4 = 10$ $(a,b; a \le b)$.

For each of the $10$ $(a,b; a\le b)$ we have two options as to whether we will allow it to be an element of symmetric $S$. For each of the $6$ $(b, a; b > a)$ the chose as to whether we will allow it to be an element of symmetric $S$ will have already been made when we made a decision for $(a,b)$.

So $k = 10$ and there are $2^{10} = 1024$ symmetric subsets.

(You did not consider such subsets as $\{ (1,3), (2,4), (3,3),(3,1), (4,2)\}$ or $\{(1,2), (2,3), (1,4), (2,1), (3,2),(4,1)\}$....)

.....

If we list the 16 elements in order:

$(1,1), \color{blue}{(1,2),(1,3),(1,4)}$

$\color{red}{(2,1)} ,(2,2), \color{blue}{(2,3),(2,4)}$

$\color{red}{(3,1),(3,2)} ,(3,3), \color{blue}{(3,4)}$

$\color{red}{(4,1),(4,2),(4,3)},(4,4)$

The six blue pairs on the top are in one to one corespondence with the six red pairs on the bottom.

In constructing a symmetric set $S$ we can make a choice for every blue or black pair as to whether or not to include that element in $S$. However once we make the decision for a blue pair we must make the exact same decision for the coresponding red pair.

There are $10$ distinct independent pairs the we can choose or not choose to put in $S$ so there are $2^{10} $ such symmetric sets we may construct

Answer 2

Any symmetric set we can write as $M\cup N\cup N^T$, where $M$ is a subset of $$\{(1,1),(2,2),...(n,n)\}$$ and $N$ is a subset of (uper diagonal if you draw a matrix of $n\times n$) $$\{(1,2),(1,3),...(1,n),(2,3),(2,4)...(n-1,n)\}$$ Note that $N^T$ is defined by: $(x,y)\in N \iff (y,x)\in N^T$ and is therefore uniqely detrmined by $N$.

So there is $$2^n\cdot 2^{n(n-1)\over 2}= 2^{n(n+1)\over 2}$$ symmetric relations.