Exists Bijection to a Disjoint Set
Theorem
Let $S$ and $T$ be sets.
Then there exists a bijection from $T$ onto a set $T'$ disjoint from $S$.
Proof
Consider the set:
- $X = \text{Ran}(S) = \set {y: \paren {\exists x : \tuple {x, y} \in S} }$
From Relation is Set implies Domain and Image are Sets, this is indeed a set.
That is, $X$ consists of all the elements which are the second coordinate of some ordered pair which happens to be in $S$.
From Exists Element Not in Set, we have that $\exists z: z \notin X$.
Now consider the cartesian product $T' = T \times \set z$.
Suppose that $p \in T'$.
Then $p = \tuple {c, z}$ where $c \in T$.
Suppose $\tuple {c, z} \in S$.
Then that would mean that $z \in X$.
But we have specifically selected $z$ such that $z \notin X$.
So $p = \tuple {c, z} \notin S$.
Thus we have that $T' \cap S = \O$.
There is an obvious bijection $g: T \to T'$:
- $\forall t \in T: \map g t = \tuple {t, z}$
and hence the result.
$\blacksquare$
Sources
- 1965: Seth Warner: Modern Algebra ... (previous) ... (next): Chapter $\text {II}$: New Structures from Old: $\S 8$: Compositions Induced on Subsets
- 1965: Seth Warner: Modern Algebra ... (previous) ... (next): Chapter $\text {II}$: New Structures from Old: $\S 8$: Compositions Induced on Subsets: Exercise $8.12$