Find all relations on A that are both reflexive and antisymmetric This is the only question on my homework that still gives me a headache, I have to find out how many relations there are on $A = \{1,2,3,...,7\}$ that are both reflexive and antisymmetric.
So far all I've gotten is the following:
For antisymmetry alone, there are $7$ distinct pairs $(a,a)$ and $21$ distinct pairs $(a,b)$ with $a < b$.
The pairs $(a,a)$ are either contained within the relation or not, while the pairs $(a,b)$ can be contained, not be contained, or be inversed as $(b,a)$. This results in $2^7 \times 3^{21}$ antisymmetric possible relations, ignoring the fact that the relation should also be reflexive.
However, since both criteria need to be met, I need to find a way to incorporate the reflexive argument as well. This implies that if $(a,b)$ is contained, there is also a corresponding $(a,a)$, but I don't see any way to continue from here.
In retrospect, I feel as though my approach wasn't great to begin with, but I am now at a point where I have absolutely no idea what else to do, so any assistance would be greatly appreciated.
 A: Reflexivity means that for each $a$, you have to include the pair $(a,a)$ into relation. We have no freedom here. So, all the pairs $(1,1)$, ..., $(7,7)$ must be included in any such relation.
Now go on to antisymmetry property. By definition, it means that if both pairs $(a,b)$ and $(b,a)$ are included, then $a=b$. Let's reformulate that using contraposition: if $a \neq b$, then at least one of pairs $(a,b)$ or $(b,a)$ must not be included (may be both of them).
So, for each (unordered) pair $\{a,b\}$ where $a \neq b$, we have exactly 3 opportunities:

*

*include only $(a,b)$ but not $(b,a)$;

*include only $(b,a)$ but not $(a,b)$;

*include none of them.

For each such pair, we can choose one of these opportunities independently from choices for other pairs. We have in total $\frac{7 \cdot 6}{2}=21$ such pairs, and so in total we have $3^{21}$ possibilities.
Note once again that for pairs of kind $(a,a)$ we have no choice, they all must be included. And this does not affect our choices for pairs $(a,b)$ with $a\neq b$.
So, the answer is $3^{21}$.
