How many symmetric and antisymmetric relations are there in a set of 4 elements?

Question

the answer to the above is 15, but I can only get 12. Say the set A = {1,2,3,4}

I can only get {(1,1), ..., (1,1,1), ..., (1,1,1,1)} which gives me 12.

Where is my reasoning faulty?

Thank you

Answer 1

You are thinking along the right lines, but you're getting confused. You are correct in that if the relation is both symmetric and anti-symmetric, the only pairs in the relation must be of the form $(a,a)$ with $a\in\{1,2,3,4\}$ However, triples and quadruples play no part; a binary relation is a set of ordered pairs. So, the questions is how many different sets are there whose only elements are of the required form?

Here are some examples: $$\{(1,1)\}\\\{(1,1),(2,2)\}$$

Can you find the others? Although your source says $15$, the right answer is $16$.