# Thread: binary relations , no of symmetric, reflexive relations

1. ## binary relations , no of symmetric, reflexive relations

Let X = {a; b; c; d; e}. Let us call a binary relation 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.

2. ## Re: binary relations , no of symmetric, reflexive relations

To satisfy (iii), R must contain (a,b). To satisfy (ii), R must contain (b,a). To satisfy (i), R must contain (a,a) and (b,b). That is the base. Now, let's consider some other pairs:

We can add (c,c) without needing to add any additional pairs. We can add (d,d) without adding any additional pairs. We can add (e,e) without adding any additional pairs. So, for each of those pairs, R either has it or it does not. For any pair of the form (x,y) where $x \neq y$, we also need to add the pair (y,x), (x,x), and (y,y). So, let's count pairs that we can add. We will only consider elements of the pair in alphabetical order. So, we will consider (a,c), but not (c,a), because if we add (a,c), we also add (c,a). With (c,c), we can add (a,c) or (b,c) without needing to add (d,d) or (e,e). With (d,d), we can add (a,d) or (b,d) without needing to add (c,c) or (e,e). If we add (c,c) and (d,d), we can add (c,d) without needing to add (e,e). So, for any two pairs among (c,c), (d,d), or (e,e), we can add none of them, which gives 1 possibility. We can add one of them and the associated (a,*), (b,*), which gives $3\cdot 2^2$ possibilities. We can add two of them, which gives $3\cdot 2^5$ possibilities. We can add all three of them, which gives us the possibility of adding (a,c), (a,d), (a,e), (b,c), (b,d), (b,e), (c,d), (c,e), or (d,e), which is $2^9$ possibilities.

So, all told, there are $1+3\cdot 2^2 + 3\cdot 2^5+2^9$ different possible special binary relations on X.

3. ## Re: binary relations , no of symmetric, reflexive relations

Originally Posted by ritz
Let X = {a; b; c; d; e}. Let us call a binary relation 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.
Suppose that $\mathscr{T}=\{(a,a),(b,b),(c,c),(d,d),(e,e),(a,b) ,(b,a)\}$ is the minimal relation satisfying the basic requirements for such a relation on $\mathscr{X}$.

The set $\mathscr{S}=\{(a,c),(a,d),(a,e),(b,c),(b,d),(b,e) ,(c,d),(c,e),(d,e)\}$ is such that $\mathscr{V}=\mathscr{S}\cup\mathscr{S}^{-1}$ is the set of all pairs not in $\mathscr{T}$

If $\mathscr{Y}\subseteq \mathscr{S}$ then $\mathscr{S'}=\mathscr{T}\cup\mathscr{Y}\cup \mathscr{Y}^{-1}$ is a unique required relation on $\mathscr{X}$.

So there are $2^9$ such relations.