Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Let $X$ = {$a,b,c,d,e$}. Let us call a binary relations $R$ on $X$ special if it satisfies all of the following conditions: (i) $R$ is reflexive, (ii) $R$ is symmetric and (iii) $R$ contains the pair ($a,b$). Find the number of special binary relations on $X$ you need not simplify your answer.

What I want to know is that why the number of reflexive relation is not $1$? As I know only {$(a,a),(b,b),(c,c),(d,d),(e,e)$} is reflexive. So one.. I know it must be wrong. Is there anybody to let me know?

And also I think the relation must contain {{$(a,a),(b,b),(c,c),(d,d),(e,e),(a,b),(b,a)$} I do know know how to solve it from here.

share|cite|improve this question
The number of reflexive relations is not 1 because, any other relation that contains the set you have written out is also reflexive. – user21436 Jan 13 '12 at 12:48
Have you in your class proved that the number of reflexive relations on a set of cardinality $n$ is $2^{n^2-n}$? – user21436 Jan 13 '12 at 12:57
Such a relation is basically completely determined by a subset of the nine element set $\{(a,c),(a,d),(a,e),(b,c),(b,d),(b,e),(c,d),(c,e),(d,e)\}$. So the total should be $2^9$. – Thomas Andrews Jan 13 '12 at 14:42

Start by writing the biggest full relation on $X$.

After that, determine the total number of possible relations (subsets of the full relation).

Think about these points (written in the order of increasing hardness):

  • How does fixing the pair $(a, b)$ change the count you got above.
  • How does fixing any number of pairs change the count.
  • How does fixing that the relation is reflexive change the count.
  • Finally (and relatively trickiest) think about how the symmetry of the relation changes the set (hint: you can forget about approximately half the pairs in the full relation).

Since this is a homework problem, I won't reveal more, may be I can give more hints if you want.

share|cite|improve this answer

Your final statement is correct: any such relation must include all of the pairs $(a,a),(b,b)$, $(c,c),(d,d)$, and $(e,e)$ just in order to be reflexive, it must include $(a,b)$ to satisfy (iii), and once it contains $(a,b)$, it must contain $(b,a)$ in order to be symmetric. Call this relation $R_0$: $$R_0=\{(a,a),(b,b),(c,c),(d,d),(e,e),(a,b),(b,a)\}\;.$$ It is indeed special according to the definition, but it’s not the only special relation on $X$. For instance, we could add the pairs $(a,c)$ and $(c,a)$ to get the relation $$\{(a,a),(b,b),(c,c),(d,d),(e,e),(a,b),(b,a),(a,c),(c,a)\}\;,$$ which (as you can easily check) is also special. In fact you can add any pair to $R_0$ provided that you also add the reversed pair, so that you preserve the symmetry of the relation. In other words, if $\{x,y\}$ is any pair of distinct members of $X$ other than $\{a,b\}$, you can add the pairs $(x,y)$ and $(y,x)$ to $R_0$ and still have a special relation, but you have to add both of these pairs or neither.

  1. How many pairs $\{x,y\}$ of distinct members of $X$ are there besides the pair $\{a,b\}$?

  2. Let $P$ be the collection of all pairs of the kind that you counted in (1). If $S$ is any subset of $P$, you can add $(x,y)$ and $(y,x)$ to $R_0$ for every pair $\{x,y\}$ in $S$ and get a special relation on $X$, and every special relation on $X$ can be obtained in this way. This means that you can count special relations on $X$ by counting subsets of $P$. How many different subsets of $P$ are there? You’ll need your answer from (1) in order to answer this.

share|cite|improve this answer

Your Answer


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.