Number of reflexive relations on the set {1,2,...,n}

Question

I am solving questions of a bachelors exam and was unable to solve this question and i am looking for help!!

Find Number of reflexive relations on the set {1,2,...,n}.

I know that R is called reflexive if for every a $\in $R a R a. But when I used it here 1 got that there would be only 1 reflexive relation ie each element goes to itself but that's wrong according to answers.

I don't have any idea on how too approach the question .

Waiting for your reply!

Answer 1

As the set $S=\{1,2,\ldots, n\}$ has $n$ elements, the set of all pairs of elements in $S$ (i.e. $S\times S$) has $n^2$ elements.

Out of those, $n$ pairs are of the form $(x,x)$ for $x\in S$. Those pairs must belong to a reflexive relation $R$. As for the remaining $n^2-n$ pairs, each of them may or may not belong to the relation $R$, so the number of potential candidates for $R$ is $2^{n^2-n}$.

Answer 2

But you can have whatever relation you want for $aRb$ with $a\neq b.$ Show that there are $2\binom{n}{2}$ of them. And either they are there or not. Giving a total of $2^{2\binom{n}{2}}.$