# Existence of an inverse relation for $R \subseteq A \times A$.

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$?

Edit

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.

• 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. Jun 23 '16 at 20:18
• 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. Jun 24 '16 at 8:01