I'm stuck with the following problem:

Given the set $A = \{1,2,3,4,5\}$, construct a relation $R \subseteq A \times A$ such $$ R \circ R^{-1} = \triangle_A = \{(a,a) \hspace{5pt} | \hspace{5pt} a \in A\}$$ and $$R^{-1} \circ R = \{(a,a)\};$$ that is, the set that consists of all the ordered pairs in $A \times A$ where both elements are equal, and a set that consists of only one point.

Now, here's where I've got so far:

Let $R = \{(1,1), (1,2) , (1,3) , (1,4) , (1,5) \}$, so that $R^{-1} = \{(1,1), (2,1) , (3,1) , (4,1) , (5,1) \}$. Then, $$R^{-1} \circ R = \{ (1,1)\} $$ But, as you can see, taking $R \circ R^{-1}$, gives back all of $R$. I've taken similar choices of $R$ and none of them work.

Now, for example, for the set that contains all ordered pairs with equal entries let $R = \{ (1,2),(2,3),(3,4),(4,5), (5,1) \}$, then $ R^{-1} = \{ (2,1) , (3,2), (4,3) , (5,4) , (5,1)\}$. Taking the composition from either side yields $\triangle_A$.

My guess is that there is no such $R$: in order to get $\triangle_A$, our relation must be in a way that $R \circ R^{-1} = R^{-1} \circ R$, which would imply that the other condition cannot be met.

So, provided I'm not wrong, lets say $X= \{ R \subseteq A \times A \hspace{5pt} | \hspace{5pt} R \circ R^{-1} = \triangle_A\}$, that is, the set of all appropriate choices of $R$ such that $R \circ R^{-1} = \triangle_A$, and in a similar way, let $Y = \{ R \subseteq A \times A \hspace{5pt} | \hspace{5pt} R \circ R^{-1} = \{(a,a)\} \hspace{5pt} \text{for some} \hspace{5pt} a \in A\}$.

How would I prove that $X \cap Y = \varnothing$?


If we arrange all the members of $A \times A$ in the following matrix/array, we can make the following conclusions:

$$ \left( \begin{array}{[ccccc} (1,1) &(1,2)&(1,3)&(1,4)&(1,5)\\ (2,1)&(2,2)&(2,3)&(2,4)&(2,5)\\ (3,1)&(3,2)&(3,3)&(3,4)&(3,5)\\ (4,1)&(4,2)&(4,3)&(4,4)&(4,5)\\ (5,1)&(5,2)&(5,3)&(5,4)&(5,5)\\ \end{array} \right) $$

Let $R_{(n,n)} = \{ (n,n)\}$.

Define $R_{(n,a_i)} = \{ (n,a_i) \hspace{5pt} | \hspace{5pt} a_i \in A \hspace{5pt} \text{for} \hspace{5pt} i = 1, ... ,5 \}$, this is represented as the $n$-th row in the matrix.

Similarly, $R_{(a_i,n)} = (R_{(n,a_i)})^{-1}$, is the $n$-th column in the matrix.

Now, if we want to choose a relation on $A$ such that $ R \circ R^{-1} = \triangle_A $ contains all the ordered pairs with equal entries in $A \times A$, and $R_{(n,n)}$ is possible, then we have only five options, namely, the five rows of the matrix. Since none of those rows is an appropriate choice of $R$, then we can conclude that there does not exist any relation on $A$ that has the properties requested.

Does this count as a proof or does it lack something?


Let $R$ be a relation on set $A$ such that $R^{-1}\circ R=\left\{ \left\langle a,a\right\rangle \right\} $ for some $a\in A$ and $R\circ R^{-1}=\triangle_{A}$.

Then $\left\langle x,b\right\rangle \in R\implies\left\langle x,x\right\rangle \in R^{-1}\circ R\implies x=a$ .

So $R=\left\{ a\right\} \times S$ where $S$ is a non-empty subset of $A$.

Based on that we find that $S\times S\subseteq R\circ R^{-1}$.

But then $R\circ R^{-1}=\triangle_{A}$ implies that $S$ must be a singleton and we end up with $R=\left\{ \left\langle a,a\right\rangle \right\} $ and consequently $R\circ R^{-1}=\left\{ \left\langle a,a\right\rangle \right\} $.

So, then $\triangle_{A}$ is a singleton and consequently $A$ is a singleton.

Proved is now the conditions on $R$ can only be satisfied if $A$ is a singleton.

  • $\begingroup$ I'm having trouble understanding why $R\circ R^{-1}=\triangle_{A}$ implies that $S$ must be a singleton, could you elaborate a little more? Thanks, for your answer. $\endgroup$
    – Eduardo M.
    Jun 23 '16 at 20:18
  • 1
    $\begingroup$ Suppose $S$ is not a singleton. Also $S\neq\varnothing$ so $S$ will contain two distinct elements $a,b$ then. But then $\langle a,b\rangle\in S\times S\subseteq\triangle_A$. A contradiction. $\endgroup$
    – drhab
    Jun 24 '16 at 8:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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