This post was translated from Korean by LLM (Kimi). The translation may contain errors or awkward sentences. The Korean original is the source of truth.
We now define the inverse of a binary relation, and composition of binary relations.
Inverse of Binary Relations
Definition 1 Let \(R\) be a binary relation. Then the binary relation consisting of all \((y,x)\) satisfying \((x,y)\in R\) is called the inverse of \(R\), and is denoted by \(R^{-1}\). Also, 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 such that the following formula
\[(x,y)\in R\iff (y,x)\in R^{-1}\]holds.
The set \(R^{-1}(X)\) can be viewed as the preimage of \(X\) under the binary relation \(R\), or as the image of \(X\) under the inverse relation \(R^{-1}\). However, by the definition of \(R^{-1}\), whichever viewpoint we adopt, we obtain the same set, so there is no danger of confusion.
Proposition 2 The inverse of \(R^{-1}\) is \(R\). Also, \(\pr_1R^{-1}=\pr_2R\) and \(\pr_2R^{-1}=\pr_1R\).
Proof
The first claim is immediate from the formula
\[(x,y)\in R\iff (y,x)\in R^{-1}\iff (x,y)\in (R^{-1})^{-1}\]For the second claim, suppose \(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 proves that \(\pr_2R\subset\pr_1R^{-1}\).
For the remaining equality \(\pr_2R^{-1}=\pr_1R\), it suffices to replace \(R\) by \(R^{-1}\) in the claim just proved.
For given sets \(A,B\), the product \(A\times B\) was the largest binary relation having \(A\) as source and \(B\) as target. Thus, from the two formulas
\[\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\), so \((x,y)\in A\times B\), and therefore \((y,x)\in (A\times B)^{-1}\); hence \((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 a \(y\) such that \((x,y)\in R_1\) and \((y,z)\in R_2\).
It is natural to ask what relationship exists between the composition of binary relations defined in this way and the inverse defined above.
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\). And this is again equivalent to
Moreover, composition of binary relations satisfies the associative law.
Proposition 5 Composition of binary relations satisfies the associative law. That is, for three 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)\), being an element of \((R_3\circ R_2)\circ R_1\) is equivalent to being an element of \(R_3\circ(R_2\circ R_1)\).
First, \((x,w)\in (R_3\circ R_2)\circ R_1\) is equivalent to
Thus we may express this common result \((R_3\circ R_2)\circ R_1=R_3\circ(R_2\circ R_1)\) without parentheses as \(R_3\circ R_2\circ R_1\) without any problem.
The remaining propositions deal with how the image of a set changes 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 preceding proposition.
For any \(z\), the statement \(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\), \(Y\subseteq B\). Then
- \[R^{-1}(R(X))\supset X\cap\pr_1R\]
- \[R(R^{-1}(Y))\supset Y\cap\pr_2R\]
hold respectively.
Proof
Before we begin the proof in earnest, since the two formulas above must hold for all \(R\), they must also hold when \(R^{-1}\) is substituted in place of \(R\). Therefore, once we prove 1, then 2 follows immediately from Proposition 2.
Now let \(x\in X\cap\pr_1R\). Then since \(x\in\pr_1R\), there exists some \(y\) such that \((x,y)\in R\), and because \(x\in X\), this \(y\) satisfies \(y\in R(X)\). 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 two formulas 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
The following 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}\]is immediate. The second formula can be shown 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 will show that this relation is a function, and it is called the identity function defined 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 two formulas
\[R_1\circ\Delta_A=R_1,\qquad \Delta_A\circ R_2=R_2\]always hold, so it is not awkward to call \((\Delta_A,A,A)\) the identity function.
References
[Bou] N. Bourbaki, Theory of Sets. Elements of mathematics. Springer Berlin-Heidelberg, 2013.
댓글남기기