3
$\begingroup$

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!?

$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.