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.
댓글남기기