9.3.2 Binary Unions of Relations

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

Definition 9.3.2.1.1 ▶ Binary Unions of Relations

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

  • •

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

    \[ R\cup 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$ or $a\sim _{S}b$}\right\} . \]
  • •

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

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

    for each $a\in A$.

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

Proposition 9.3.2.1.2 ▶ Properties of Binary Unions 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\cup S\webright )^{\dagger } = R^{\dagger }\cup S^{\dagger }. \]
  2. 2.

    Interaction With Composition. We have

    \[ \webleft (S_{1}\mathbin {\diamond }R_{1}\webright ) \cup \webleft (S_{2}\mathbin {\diamond }R_{2}\webright ) \mathrel {\smash {\overset {\scriptscriptstyle \mathrm{poss.}}\neq }}\webleft (S_{1}\cup S_{2}\webright ) \mathbin {\diamond }\webleft (R_{1}\cup R_{2}\webright ). \]

Proof of Proposition 9.3.2.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 )\cup \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}}$;

      or

      • •

        $\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}\cup S_{2}\webright )\mathbin {\diamond }\webleft (R_{1}\cup 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}}$ or $\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}}$ or $\require{color}{\color[rgb]{0.000000000000000,0.447058823529412,0.698039215686274}{b\sim _{S_{2}}c}}$.

These two conditions may fail to agree (counterexample omitted), and thus the two resulting relations on $A\times C$ may differ.

Up
Next

View Definition 9.3.2.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: