How many reflexive binary relations there are on a finite countable set?

Question

We know that binary relation is subset of Cartesian product made by set on to itself.
let's say we have a set with two elements $A=\{0,1\}$
So Cartesian product is $C=A\times A = \{(0,0),(0,1),(1,0),(1,1)\}$
Then we should write down all subsets of this product to get all binary relations. Right?

$1. \ \ \ \ ∅$
$2. \ \ \ \ \{(0,0)\}$
$3. \ \ \ \ \{(0,1)\}$
$4. \ \ \ \ \{(1,0)\}$
$5. \ \ \ \ \{(1,1)\}$
$6. \ \ \ \ \{(0,0),(0,1)\}$
$7. \ \ \ \ \{(0,0),(1,0)\}$
$8. \ \ \ \ \{(0,0),(1,1)\}$
$9. \ \ \ \ \{(0,1),(1,0)\}$
$10. \ \ \{(0,1),(1,1)\}$
$11. \ \ \{(1,0),(1,1)\}$
$12. \ \ \{(0,0),(0,1),(1,0)\}$
$13. \ \ \{(0,0),(0,1),(1,1)\}$
$14. \ \ \{(0,0),(1,0),(1,1)\}$
$15. \ \ \{(0,1),(1,0),(1,1)\}$
$16. \ \ \{(0,0),(0,1),(1,0),(1,1)\}$

We know that there are only 4 reflexive binary relations.
those are: 8, 13, 14, 16
because they satisfied reflexive property: for all $x ∈ A, \rightarrow (x,x)∈ R.$

But what if we have a set with $n$ elements?
How many reflexive binary relations there should be?
I know that it might be $2^{n^2-n}$ but I don't know how to prove it?
Should I use induction method?
How to prove it?
Anyone help me!?

Answer 1

Consider the set $A \times A$ which has $n^2$ elements. The requirement that your relation $R$ be reflexive says that $(a,a) \in R$ for all $a$. So out of the $n^2$ elements of $A \times A$, $n$ of them are required to be in $R$. What remains is $n^2-n$ elements of $A \times A$, each of which may or may not be in the relation. The subsets of these $n^2-n$ elements correspond one-to-one with all reflexive binary relations, and there are $2^{n^2-n}$ such subsets.

Answer 2

There are $2^{n^2}$ subsets of $S\times S$ if $|S|=n$.

You're looking for subsets which contain the diagonal, $\Delta(S) = \{(s,s): s\in S\}\subseteq S\times S$.

So this is just a matter of choosing which other sets are a part of your relation, i.e. any other collection of sets can be thrown in, off-diagonal, which is to say: subsets of $$S\times S\setminus\Delta(S)$$

which has cardinality $n^2-n$, so you have $2^{n^2-n}$ such relations.

Answer 3

Suppose $S$ has $n$ elements. Then $S \times S$ has $n^2$ many elements. But to be reflexive, it should contain all diagonal elements $(s,s)$, for $s \in S$, so there are $n^2 - n$ many elements of $S \times S$ that we can either put in a reflexive relation or not.

So we have $2^{n^2 - n}$ many such relations, because every subset of $S \times S \setminus \Delta(S)$ gives us a different reflexive relation (we add $\Delta(S)$ to it).