Bijection between Power Set of Disjoint Union and Cartesian Product of Power Sets

From ProofWiki
Jump to navigation Jump to search


Let $S$ and $T$ be disjoint sets.

Let $\powerset S$ denote the power set of $S$.

Then there exists a bijection between $\powerset {S \cup T}$ and $\paren {\powerset S} \times \paren {\powerset T}$.


$\powerset {S \cup T} \sim \paren {\powerset S} \times \paren {\powerset T}$

where $\sim$ denotes set equivalence.


Let $\phi: \paren {\powerset S} \times \paren {\powerset T} \to \powerset {S \cup T}$ be defined as:

$\forall \tuple {A, B} \in \paren {\powerset S} \times \paren {\powerset T}: \map \phi {A, B} = A \cup B$

In order to show that $\phi$ is a bijection, it needs to be shown that $\phi$ has the following properties:

$\phi$ is a mapping, that is:
$\phi$ is left-total
$\phi$ is many-to-one
$\phi$ is a surjection
$\phi$ is an injection.

Let $A \subseteq S$ and $B \subseteq T$.


\(\displaystyle A\) \(\in\) \(\displaystyle \powerset S\) Definition of Power Set
\(\, \displaystyle \land \, \) \(\displaystyle B\) \(\in\) \(\displaystyle \powerset T\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \tuple {A, B}\) \(\in\) \(\displaystyle \paren {\powerset S} \times \paren {\powerset T}\) Definition of Cartesian Product


$\forall A \subseteq S, B \subseteq T: \tuple {A, B} \in \Dom \phi$

and so $\phi$ is left-total.


Let $A_1, A_2 \subseteq S$ and $B_1, B_2 \subseteq T$.


\(\displaystyle \map \phi {A_1, B_1}\) \(\ne\) \(\displaystyle \map \phi {A_2, B_2}\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle A_1 \cup B_1\) \(\ne\) \(\displaystyle A_2 \cup B_2\) Definition of $\phi$
\(\displaystyle \leadsto \ \ \) \(\displaystyle A_1 \cup B_1\) \(\nsubseteq\) \(\displaystyle A_2 \cup B_2\) Definition of Set Equality
\(\, \displaystyle \lor \, \) \(\displaystyle A_2 \cup B_2\) \(\nsubseteq\) \(\displaystyle A_1 \cup B_1\)

Without loss of generality, suppose $A_1 \cup B_1 \nsubseteq A_2 \cup B_2$.


\(\displaystyle \exists x \in A_1 \cup B_1: \ \ \) \(\displaystyle x\) \(\notin\) \(\displaystyle A_2 \cup B_2\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle x \in A_1 \lor x \in B_1: \ \ \) \(\displaystyle x \notin A_2\) \(\land\) \(\displaystyle x \notin B_2\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle A_1 \ne A_2\) \(\lor\) \(\displaystyle A_1 \ne B_2\)
\(\, \displaystyle \land \, \) \(\displaystyle B_1 \ne A_2\) \(\lor\) \(\displaystyle B_1 \ne B_2\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \tuple {A_1, B_1}\) \(\ne\) \(\displaystyle \tuple {A_2, B_2}\)

That is:

$\map \phi {A_1, B_1} \ne \map \phi {A_2, B_2} \implies \tuple {A_1, B_1} \ne \tuple {A_2, B_2}$

demonstrating that $\phi$ is many-to-one.

Thus $\phi$ has been shown to be a mapping.


Let $A \cup B \in \powerset {S \cup T}$.


$\tuple {A, B} \in \paren {\powerset S} \times \paren {\powerset T}$

by definition of power set and Cartesian product.

That is, $\phi$ is a surjection by definition.


It remains to be shown that $\phi$ is an injection.

Let $\tuple {A_1, B_1} \ne \tuple {A_2, B_2}$.

Then either $A_1 \ne A_2$ or $B_1 \ne B_2$.

That is, at least one of the following holds:

\(\displaystyle A_1\) \(\nsubseteq\) \(\displaystyle A_2\)
\(\displaystyle A_2\) \(\nsubseteq\) \(\displaystyle A_1\)
\(\displaystyle B_1\) \(\nsubseteq\) \(\displaystyle B_2\)
\(\displaystyle B_2\) \(\nsubseteq\) \(\displaystyle B_1\)

Without loss of generality, suppose $A_1 \nsubseteq A_2$.


$\exists x \in A_1: x \notin A_2$

and so by Set is Subset of Union:

$x \in A_1 \cup B_1$

But we have that $S$ and $T$ are disjoint.

That is:

$x \in A_1 \implies x \notin B_2$


$\exists x \in A_1 \cup B_1: x \notin A_2 \cup B_2$

and so:

$A_1 \cup B_1 \ne A_2 \cup B_2$

That is:

$\map \phi {A_1, B_1} \ne \map \phi {A_2, B_2}$

demonstrating that $\phi$ is an injection.

Hence the result.