1

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?

Brian M. Scott
  • 616,228
George
  • 43

3 Answers3

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?

Brian M. Scott
  • 616,228
  • it's 2^(n^2-n)? – George Nov 22 '12 at 03:48
  • @George: It is indeed. – Brian M. Scott Nov 22 '12 at 03:51
  • I'm confused on why it's $2^{n^2-n}$. If there are $2^n$ elements on the diagonal that make it reflexive then why is the final answer the entries that are not on the diagonal? – stumped Apr 20 '16 at 17:02
  • 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. – Brian M. Scott Apr 20 '16 at 21:22
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?

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
-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$)

Priyanshu
  • 134