1
$\begingroup$

Given a set with $n$ elements

I know that there is $2^{n^2}$ relations, because there are $n$ rows and $n$ columns and it is either $1$ or $0$ in each case, but I don't know how to compute the number of reflexive relation. I am very dumb. Can someone help me go through the thought process?

3 Answers 3

7

A relation is reflexive if and only if every entry on the main diagonal of its matrix is $1$; that’s the only restriction. Fill in $1$’s on the diagonal, and you can put either $0$ or $1$ freely into every other entry in the matrix and have the matrix of a reflexive relation. Thus, the number of reflexive relations on a set of $n$ elements is $2^m$, where $m$ is the number of entries that are not on the diagonal. There are $n^2$ entries altogether, and $n$ of them are on the diagonal, so how many are not on the diagonal? And then how many reflexive relations are there?

  • 1
    @stumped: There are $n$ elements on the diagonal, and since we want a reflexive relation, all of them have to be $1$: we have no choice about them. Each of the other $n^2-n$ entries, however, can be either $0$ or $1$ without affecting the reflexivity of the relation. Thus, in building the matrix we have a $2$-way choice for each of those $n^2-n$ entries and no choice at all for the other $n$ entries; there are $2^{n^2-n}$ different ways to make those choices and hence $2^{n^2-n}$ different reflexive relations.2016-04-20
0

Strange way you have to count the number of relations...A relation on a set $\,A\,$ is just a subset of the cartesian product $\,A\times A\,$, and if $\,|A|=n\Longrightarrow |A\times A|=n^2\Longrightarrow\,$ the number of subsets of $\,A\times A\,$ , i.e. $\,|P(A\times A)|\,$ , is $\,2^{|A\times A|}=2^{n^2}\,$...

Now, you need to count all the subsets of $\,A\times A\,$ that contain the diagonal $\,\Delta_A:=\{(a,a)\in A\times A\}\,$ , so...can you take it form here?

  • 0
    Would you please elaborate the reflexive count i.e $\,\Delta_A:=\{(a,a)\in A\times A\}\,$?2017-09-22
-1

A relation $R$ on $A$ is a subset of $AXA$. If $A$ is reflexive, each of the $n$ ordered pairs $(a,a)$ belonging to $A$ must be in $R$.
So the remaining $n^2-n$ ordered pairs of the type $(a,b)$ where $a!=b$ may or may not be in R.

So each ordered pair has now 2 choices, to be in $R$ or to not be in $R$.
Hence number of pairs = 2($n^2-n$)

  • 0
    Welcome to MSE. For some basic information about writing mathematics at this site see, *e.g.*, [basic help on mathjax notation](/help/notation), [mathjax tutorial and quick reference](//math.meta.stackexchange.com/q/5020), [main meta site math tutorial](//meta.stackexchange.com/a/70559) and [equation editing how-to](//math.meta.stackexchange.com/q/1773).2018-09-17