Symmetric and antisymmetric binary relations

Question

I would like to ask you for an advice.

I need to find all binary relations on set A ⊆ N which are symmetric and antisymmetric.

Am I right when I thing that result pairs could be just pairs on diagonal so count of its is 2^n?

Thanks a lot.

Answer 1

If a relation $R$ is both simmetric and antisimetric it means if $(a,b)$ is in $R$ then $(b,a)$ is in $R$ by symmetry, but then it meas $a=b$ by antisymmetry.

So the relations you are looking for are exactly those which only have elements of the form $(a,a)$.

So given a set $A$ with $n$ elements how many of these relations are there? well, for each element $a$ we need to select whether $(a,a)$ is in $R$ or not. since we need to make this choice $n$ times it is $2^n$