We now define the inverse of a binary relation and the composition of binary relations.
Inverse of a Binary Relation
Definition 1 Let $R$ be a binary relation. The inverse of $R$, denoted by $R^{-1}$, is the binary relation consisting of all $(y,x)$ such that $(x,y)\in R$. The set $R^{-1}(X)$ is called the preimage of $X$. If $R^{-1}=R$, then $R$ is said to be symmetric.
Explicitly, $R^{-1}$ is the set satisfying the condition
\[(x,y)\in R\iff (y,x)\in R^{-1}\]The set $R^{-1}(X)$ may be viewed either as the preimage of $X$ under the binary relation $R$, or as the image of $X$ under the inverse relation $R^{-1}$. By the definition of $R^{-1}$, however, both perspectives yield the same set, so there is no ambiguity.
Proposition 2 The inverse of $R^{-1}$ is $R$. Moreover, $\pr_1R^{-1}=\pr_2R$ and $\pr_2R^{-1}=\pr_1R$.
Proof
The first claim follows immediately from
\[(x,y)\in R\iff (y,x)\in R^{-1}\iff (x,y)\in (R^{-1})^{-1}\]For the second claim, if $x\in\pr_1R^{-1}$, then there exists some $y$ such that $(x,y)\in R^{-1}$. Since $(y,x)\in R$, we have $x\in\pr_2R$. Reversing this argument establishes $\pr_2R\subset\pr_1R^{-1}$.
The case $\pr_2R^{-1}=\pr_1R$, not yet shown, follows by substituting $R^{-1}$ for $R$ in the claim just proven.
For given sets $A,B$, the product $A\times B$ is the largest binary relation having $A$ as source and $B$ as target. Thus from the two equations
\[\pr_1(A\times B)^{-1}=\pr_2(A\times B)=B,\qquad \pr_2(A\times B)^{-1}=\pr_1(A\times B)=A\]we obtain $(A\times B)^{-1}\subseteq B\times A$. Conversely, if $(y,x)\in B\times A$, then $x\in A$ and $y\in B$, whence $(x,y)\in A\times B$, and therefore $(y,x)\in (A\times B)^{-1}$. Thus $(A\times B)^{-1}=B\times A$.
Composition of Binary Relations
Definition 3 Let $R_1$ and $R_2$ be binary relations. The composition $R_2\circ R_1$ of these two binary relations is the set of ordered pairs $(x,z)$ for which there exists $y$ with $(x,y)\in R_1$ and $(y,z)\in R_2$.
One may naturally ask how the composition of binary relations relates to the inverse defined earlier.
Proposition 4 Let $R_1$, $R_2$ be binary relations. Then the inverse of $R_2\circ R_1$ is $R_2^{-1}\circ R_1^{-1}$.
Proof
$(z,x)\in (R_2\circ R_1)^{-1}$ is equivalent to $(x,z)\in R_2\circ R_1$. This in turn is equivalent to
Furthermore, the composition of binary relations is associative.
Proposition 5 The composition of binary relations is associative. That is, for binary relations $R_1,R_2,R_3$,
\[(R_3\circ R_2)\circ R_1=R_3\circ(R_2\circ R_1)\]holds.
Proof
It suffices to show that for any $(x,w)$, membership in $(R_3\circ R_2)\circ R_1$ is equivalent to membership in $R_3\circ(R_2\circ R_1)$.
Now $(x,w)\in (R_3\circ R_2)\circ R_1$ is equivalent to
Thus the common result $(R_3\circ R_2)\circ R_1=R_3\circ(R_2\circ R_1)$ may be written unambiguously as $R_3\circ R_2\circ R_1$ without parentheses.
The remaining propositions concern how the image of a set transforms under the inverse and composition of binary relations defined above.
Proposition 6 Let $R_1$, $R_2$ be binary relations and let $A$ be a set. Then
\[(R_2\circ R_1)(A)=R_2(R_1(A))\]holds.
Proof
We proceed as in the previous proposition.
For any $z$, $z\in (R_2\circ R_1)(A)$ is equivalent to
Proposition 7 Let $(R,A,B)$ be a binary relation, and let $X\subseteq A$ and $Y\subseteq B$. Then
- $R^{-1}(R(X))\supset X\cap\pr_1R$
- $R(R^{-1}(Y))\supset Y\cap\pr_2R$
hold.
Proof
Before proceeding with the proof, note that since the two equations above must hold for all $R$, they must also hold when $R^{-1}$ is substituted for $R$. Thus once 1 is established, 2 follows immediately from Proposition 2.
Now let $x\in X\cap\pr_1R$. From $x\in\pr_1R$, there exists some $y$ such that $(x,y)\in R$, and since $x\in X$, this $y$ satisfies $y\in R(X)$. Now since $(y,x)\in R^{-1}$, we have $x\in R^{-1}(R(X))$.
Proposition 8 Let $R_1$, $R_2$ be binary relations. Then the following equations hold:
\[\pr_1(R_2\circ R_1)=R_1^{-1}(\pr_1R_2),\quad \pr_2(R_2\circ R_1)=R_2(\pr_2R_1).\]Proof
This follows immediately from the chain of implications:
\[\begin{aligned} x\in\pr_1(R_2\circ R_1)&\iff \exists z\big((x,z)\in R_2\circ R_1\big)\\ &\iff\exists y,z\big(((x,y)\in R_1)\wedge((y,z)\in R_2)\big)\\ &\iff\exists y\big(((x,y)\in R_1)\wedge(y\in\pr_1R_2)\big)\\ &\iff x\in R_1^{-1}(\pr_1 R_2). \end{aligned}\]The second equation is established similarly.
Finally, we introduce a special binary relation.
Definition 9 For a set $A$, $\Delta_A$ denotes the binary relation
\[\Delta_A=\{(x,x)\mid x\in A\}.\]This is called the diagonal of $A\times A$.
By definition, $\pr_1\Delta_A=\pr_2\Delta_A=A$, so we may regard this as the binary relation
\[\left(\Delta_A,A,A\right).\]In the next post, we shall see that this relation is a function, called the identity function on the set $A$. For a binary relation $R_1$ having $A$ as source, or a binary relation $R_2$ having $A$ as target, the equations
\[R_1\circ\Delta_A=R_1,\qquad \Delta_A\circ R_2=R_2\]always hold, so the terminology of calling $(\Delta_A,A,A)$ the identity function is natural.
References
[Bou] N. Bourbaki, Theory of Sets. Elements of mathematics. Springer Berlin-Heidelberg, 2013.
댓글남기기