Exists Bijection to a Disjoint Set

From ProofWiki

Jump to: navigation, search

Theorem

Let $S$ and $T$ be sets.

Then there exists a bijection from $T$ onto a set $T\,'$ disjoint from $S$.

Consider the set:

$X = \left\{{y \in S: \left({\exists x \in T: \left({x, y}\right) \in S}\right)}\right\}$

That is, $X$ consists of all the elements of $S$ which are the second coordinate of some ordered pair which also happens to be in $S$ and whose first coordinate is in $T$.

From Exists Element Not in Set, we have that $\exists z: z \notin X$.

Now consider the cartesian product $T\,' = T \times \left\{{z}\right\}$.

Suppose that $p \in T\,'$.

Then $p = \left({c, z}\right)$ where $c \in T$.

Suppose $\left({c, z}\right) \in S$.

Then that would mean that $z \in X$.

But we have specifically selected $z$ such that $z \notin X$.

So $p = \left({c, z}\right) \notin S$.

Thus we have that $T\,' \cap S = \varnothing$.

There is an obvious bijection $g: T \to T\,'$:

$\forall t \in T: g \left({t}\right) = \left({t, z}\right)$

and hence the result.

$\blacksquare$