Union of Bijections with Disjoint Domains and Codomains is Bijection
Theorem
Let $A$, $B$, $C$, and $D$ be sets or classes.
Let $A \cap B = C \cap D = \O$.
Let $f: A \to C$ and $g: B \to D$ be bijections.
Then $f \cup g: A \cup B \to C \cup D$ is also a bijection.
Corollary
Let $A$, $B$, $C$, and $D$ be sets or classes.
Let $A \cap B = C \cap D = \O$.
Let $f: A \to C$ and $g: D \to B$ be bijections.
Then $f \cup g^{-1}: A \cup B \to C \cup D$ is also a bijection.
Proof
By the definition of bijection, $f$ and $g$ are many-to-one and one-to-many relations.
By Union of Many-to-One Relations with Disjoint Domains is Many-to-One and Union of One-to-Many Relations with Disjoint Images is One-to-Many:
- $f \cup g$ is many-to-one and one-to-many.
Thus to show $f \cup g$ is a bijection requires us only to demonstrate that it is both left-total and right-total.
We will show that $f \cup g$ is left-total.
Let $x \in A \cup B$.
Then $x \in A$ or $x \in B$.
If $x \in A$ then since $f$ is left-total there is a $y \in C$ such that $\tuple {x, y} \in f$.
By the definition of union, $\tuple {x, y} \in f \cup g$.
If $x \in B$ then since $g$ is left-total there is a $y \in D$ such that $\tuple {x, y} \in g$.
Then by the definition of union, $\tuple {x, y} \in f \cup g$.
As this holds for all $x$, $f \cup g$ is left-total.
The proof that $f \cup g$ is right-total is similar.
Thus it has been demonstrated that:
- $f \cup g$ is many-to-one
- $f \cup g$ is one-to-many
- $f \cup g$ is left-total
- $f \cup g$ is right-total
and therefore, by definition, a bijection.
$\blacksquare$