Subsection 6.3.5 (00PP): Binary Unions of Relations

Style	Class	Font	Theorem Environments
Style 1	`book`	Alegreya Sans	`tcbthm`
Style 2	`book`	Alegreya Sans	`amsthm`
Style 3	`book`	Arno*	`amsthm`
Style 4	`book`	Computer Modern	`amsthm`

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 define ^[2]

\[ R\cup S\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\webleft\{ \webleft (a,b\webright )\in B\times A\ \middle |\ \text{we have $a\sim _{R}b$ or $a\sim _{S}b$}\webright\} . \]
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$.

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$.

Interaction With Inverses. We have
\[ \webleft (R\cup S\webright )^{\dagger } = R^{\dagger }\cup S^{\dagger }. \]
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 ). \]

Item 1: Interaction With Inverses

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:
1. There exists some $b\in B$ such that:
  1. $\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
  1. $\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:
1. There exists some $b\in B$ such that:
  1. $\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
  1. $\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.

Footnotes

[1] Further Terminology: Also called the binary union of $R$ and $S$, for emphasis.

[2] This is the same as the union of $R$ and $S$ as subsets of $A\times B$.