9.2.6 Binary Products of Relations

    Let $A$, $B$, $X$, and $Y$ be sets, let $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ be a relation from $A$ to $B$, and let $S\colon X\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}Y$ be a relation from $X$ to $Y$.

    Definition 9.2.6.1.1 ▶ Binary Products of Relations

    The product of $R$ and $S$1 is the relation $R\times S$ from $A\times X$ to $B\times Y$ defined as follows:

    • •

      Viewing relations from $A\times X$ to $B\times Y$ as subsets of $(A\times X)\times (B\times Y)$, we define $R\times S$ as the Cartesian product of $R$ and $S$ as subsets of $A\times X$ and $B\times Y$.2

    • •

      Viewing relations from $A\times X$ to $B\times Y$ as functions $A\times X\to \mathcal{P}(B\times Y)$, we define $R\times S$ as the composition

      \[ A\times X \overset {R\times S}{\to } \mathcal{P}(B)\times \mathcal{P}(Y) \overset {\mathcal{P}^{\otimes }_{B,Y}}{\hookrightarrow } \mathcal{P}(B\times Y) \]

      in $\mathsf{Sets}$, i.e. by

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

      for each $(a,x)\in A\times X$.

    1. 1Further Terminology: Also called the binary product of $R$ and $S$, for emphasis.
    2. 2That is, $R\times S$ is the relation given by declaring $(a,x)\sim _{R\times S}(b,y)$ iff $a\sim _{R}b$ and $x\sim _{S}y$.

    Proposition 9.2.6.1.2 ▶ Properties of Binary Products of Relations

    Let $A$, $B$, $X$, and $Y$ be sets.

    1. 1.

      Interaction With Converses. Let

      \begin{align*} R & \colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}A,\\ S & \colon X\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}X \end{align*}

      We have

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

    Interaction With Composition. Let

    \begin{align*} R_{1} & \colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B,\\ S_{1} & \colon B\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}C,\\ R_{2} & \colon X\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}Y,\\ S_{2} & \colon Y\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}Z \end{align*}

    be relations. We have

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

    • Proof of Proposition 9.2.6.1.2.

    Item 1: Interaction With Converses
    Unwinding the definitions, we see that:

    • •

      We have $(a,x)\sim _{(R\times S)^{\dagger }}(b,y)$ iff:

      • •

        We have $(b,y)\sim _{R\times S}(a,x)$, i.e. iff:

        • •

          We have $b\sim _{R}a$;

        • •

          We have $y\sim _{S}x$;

    • •

      We have $(a,x)\sim _{R^{\dagger }\times S^{\dagger }}(b,y)$ iff:

      • •

        We have $a\sim _{R^{\dagger }}b$ and $x\sim _{S^{\dagger }}y$, i.e. iff:

        • •

          We have $b\sim _{R}a$;

        • •

          We have $y\sim _{S}x$.

    These two conditions agree, and thus the two resulting relations on $A\times X$ are equal.

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

    • •

      We have $(a,x)\sim _{(S_{1}\mathbin {\diamond }R_{1})\times (S_{2}\mathbin {\diamond }R_{2})}(c,z)$ iff:

      • •

        We have $a\sim _{S_{1}\mathbin {\diamond }R_{1}}c$ and $x\sim _{S_{2}\mathbin {\diamond }R_{2}}z$, i.e. iff:

        • •

          There exists some $b\in B$ such that $a\sim _{R_{1}}b$ and $b\sim _{S_{1}}c$;

        • •

          There exists some $y\in Y$ such that $x\sim _{R_{2}}y$ and $y\sim _{S_{2}}z$;

    • •

      We have $(a,x)\sim _{(S_{1}\times S_{2})\mathbin {\diamond }(R_{1}\times R_{2})}(c,z)$ iff:

      • •

        There exists some $(b,y)\in B\times Y$ such that $(a,x)\sim _{R_{1}\times R_{2}}(b,y)$ and $(b,y)\sim _{S_{1}\times S_{2}}(c,z)$, i.e. such that:

        • •

          We have $a\sim _{R_{1}}b$ and $x\sim _{R_{2}}y$;

        • •

          We have $b\sim _{S_{1}}c$ and $y\sim _{S_{2}}z$.

    These two conditions agree, and thus the two resulting relations from $A\times X$ to $C\times Z$ are equal.

Up

View Item 2 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: