2

Let $A$ be a set of size $4$. How many reflexive relations are on $A$?

Let $n = |A| = 4$

Number of reflexive relations = $ 2^n $

Is that correct?

I think so because I imagine I only want to calculate the number of relations in the diagonal of the set matrix. And there are $4$ elements in the diagonal.

Stefan Hansen
  • 25,582
  • 7
  • 59
  • 91
user1766555
  • 553

1 Answers1

1

A reflexive relation matrix is such as there are four "true" in the diagonal. The other fields are free. There are $16 - 4 = 12$ other fields.

So the number of reflexive relations is $2^{12}$ ($2^{n^2-n}$ in the general case).

Arnaud
  • 1,242
  • But the other entries that are not in the diagonal are not reflexive, correct? – user1766555 Apr 22 '13 at 08:32
  • 1
    A relation is reflexive if for all $x$, $x$ is in relation with $x$. This is the only constraint. In order to satisfy it, we have to put $1$ (or true) in the diagonal. If $x \neq y$, $x$ could be in relation with $y$. Not always, but sometimes. So the non-diagonal entries are $0$ or $1$, as you want. – Arnaud Apr 22 '13 at 08:38
  • Must all the diagonal entries be 1? Also for $2^{n^2-n}$

    I see it being that you count all the relations that aren't apart of the diagonal. It's very confusing.

    Why are we counting the other fields when the question is asking how many reflexive relations there are?

     – user1766555 Apr 22 '13 at 08:41
  • 1
    Yes, all the diagonal entries must be $1$. It is precisely for this that we count the other fields : the other fields are free, we can choose $0$ or $1$ for their values. So we have $2$ choices for each other field, and only $1$ choice for diagonal entries. – Arnaud Apr 22 '13 at 08:48