9.2.4 Binary Intersections of Relations

    Let $A$ and $B$ be sets and let $R$ and $S$ be relations from $A$ to $B$.

    Definition 9.2.4.1.1 ▶ Binary Intersections of Relations

    The intersection of $R$ and $S$1 is the relation $R\cap S$ from $A$ to $B$ defined as follows:

    • •

      Viewing relations from $A$ to $B$ as subsets of $A\times B$, we define2

      \[ R\cap S\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ (a,b)\in B\times A\ \middle |\ \text{we have $a\sim _{R}b$ and $a\sim _{S}b$}\right\} . \]
    • •

      Viewing relations from $A$ to $B$ as functions $A\to \mathcal{P}(B)$, we define

      \[ [R\cap S](a)\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}R(a)\cap S(a) \]

      for each $a\in A$.

    1. 1Further Terminology: Also called the binary intersection of $R$ and $S$, for emphasis.
    2. 2This is the same as the intersection of $R$ and $S$ as subsets of $A\times B$.

    Proposition 9.2.4.1.2 ▶ Properties of Binary Intersections of Relations

    Let $R$, $S$, $R_{1}$, and $R_{2}$ be relations from $A$ to $B$, and let $S_{1}$ and $S_{2}$ be relations from $B$ to $C$.

  • 1.

    Interaction With Converses. We have

    \[ (R\cap S)^{\dagger } = R^{\dagger }\cap S^{\dagger }. \]
  • 2.

    Interaction With Composition. We have

    \[ (S_{1}\mathbin {\diamond }R_{1}) \cap (S_{2}\mathbin {\diamond }R_{2}) = (S_{1}\cap S_{2}) \mathbin {\diamond }(R_{1}\cap R_{2}). \]

    • Proof of Proposition 9.2.4.1.2.

    Item 1: Interaction With Converses
    Clear.

    Item 2: Interaction With Composition
    Unwinding the definitions, we see that:

    • •

      The condition for $(S_{1}\mathbin {\diamond }R_{1})\cap (S_{2}\mathbin {\diamond }R_{2})$ is:

      • •

        There exists some $b\in B$ such that:

        • •

          $\require{color}{\color[rgb]{0.835294117647059,0.368627450980392,0.000000000000000}{a\sim _{R_{1}}b}}$ and $\require{color}{\color[rgb]{0.000000000000000,0.447058823529412,0.698039215686274}{b\sim _{S_{1}}c}}$;

        and

        • •

          $\require{color}{\color[rgb]{0.835294117647059,0.368627450980392,0.000000000000000}{a\sim _{R_{2}}b}}$ and $\require{color}{\color[rgb]{0.000000000000000,0.447058823529412,0.698039215686274}{b\sim _{S_{2}}c}}$;

    • •

      The condition for $(S_{1}\cap S_{2})\mathbin {\diamond }(R_{1}\cap R_{2})$ is:

      • •

        There exists some $b\in B$ such that:

        • •

          $\require{color}{\color[rgb]{0.835294117647059,0.368627450980392,0.000000000000000}{a\sim _{R_{1}}b}}$ and $\require{color}{\color[rgb]{0.835294117647059,0.368627450980392,0.000000000000000}{a\sim _{R_{2}}b}}$;

        and

        • •

          $\require{color}{\color[rgb]{0.000000000000000,0.447058823529412,0.698039215686274}{b\sim _{S_{1}}c}}$ and $\require{color}{\color[rgb]{0.000000000000000,0.447058823529412,0.698039215686274}{b\sim _{S_{2}}c}}$.

    These two conditions agree, and thus so do the two resulting relations on $A\times C$.

Up

View Item 1 as PDF
1 tag refers to this tag
Statistics Cite

Noticed something off, or have any comments? Feel free to reach out!

You can also use the contact form below: