9.3.4 Binary Intersections of Relations

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

Definition 9.3.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\{ \webleft (a,b\webright )\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}\webleft (B\webright )$, we define

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

    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.3.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. 1.

    Interaction With Converses. We have

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

    Interaction With Composition. We have

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

Proof of Proposition 9.3.4.1.2.

Item 1: Interaction With Converses
Clear.

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

  • •

    The condition for $\webleft (S_{1}\mathbin {\diamond }R_{1}\webright )\cap \webleft (S_{2}\mathbin {\diamond }R_{2}\webright )$ 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 $\webleft (S_{1}\cap S_{2}\webright )\mathbin {\diamond }\webleft (R_{1}\cap R_{2}\webright )$ 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
Next

View Definition 9.3.4.1.1 as PDF
Statistics Cite

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

You can also use the contact form below: