# Find the number of binary relations.

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.

-
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.

-

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.

-