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

6

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?

  • 0
    it's 2^(n^2-n)?2012-11-22
  • 0
    @George: It is indeed.2012-11-22
  • 0
    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?2016-04-20
  • 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) for a belonging to A must be in R So the remaining n^2-n ordered pairs from (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