Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 5 down vote accepted

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?

share|cite|improve this answer
    
it's 2^(n^2-n)? – George Nov 22 '12 at 3:48
    
@George: It is indeed. – Brian M. Scott Nov 22 '12 at 3: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 at 17:02
    
@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 at 21:22

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?

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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