How many reflexive binary relations there are on a finite countable set? 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!?
 A: 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.
A: 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.
A: 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).
