This is Velleman's exercise 4.3.9.a:
Suppose $A$ and $B$ are two sets. Show that for every relation $R$ from $A$ to $B$, $R \circ i_A = R$.
"$i_A$" in the book is defined as $\{(x, y) ∈ A × A | x = y\}$ i.e. the identity relation.
Here's my proof of the forward direction:
Proof.
($\rightarrow$) Let $(x, z)$ be an arbitrary element of $R \circ i_A$. Then by the definition of composition there must be some $y$ such that $(x, y) ∈ i_A$ and $(y, z) ∈ R$. From the definition of $i_A$ we can conclude that $x = y$, so $(y, y) ∈ i_A$ and considering $(y, z) ∈ R$, we'll get $(y, z) ∈ R \circ i_A$. Then again by the definition of composition there must be some $x$ such that $(y, x) = (y, y) ∈ i_A$ and $(x, z) ∈ R$. Since $(x, z)$ was arbitrary then $R \circ i_A \subseteq R$.
Now here are my questions:
Is my proof of the forward direction correct?
How should I start proving the backward direction?
Thanks a lot.
So based on the helpful comments, I'm gonna answer my own question:
Proof.
($\rightarrow$) Let $(x, z)$ be an arbitrary element of $R \circ i_A$. Then by the definition of composition there must be some $y$ such that $(x, y) ∈ i_A$ and $(y, z) ∈ R$. From the definition of $i_A$ we can conclude that $x = y$ and substituting $x$ in "$(y, z) ∈ R$" for y, we get $(x, z) ∈ R$. Since $(x, z)$ was arbitrary then we can conclude that $R \circ i_A \subseteq R$.
($\leftarrow$) Let $(x, y)$ be an arbitrary element of $R$. Then $(x, x) ∈ i_A$. From $(x, y) ∈ R$ and $(x, x) ∈ i_A$, by the definition of composition we'll have $(x, y) ∈ R \circ i_A$. Since $(x, y)$ was arbitrary then we can conclude that $R \subseteq R \circ i_A$.
From ($\rightarrow$) and ($\leftarrow$), we get $R \circ i_A = R$.