Union of Indexed Family of Sets Equal to Union of Disjoint Sets

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\family {E_n}_{n \mathop \in \N}$ be a countable indexed family of sets where at least two $E_n$ are distinct.


Then there exists a countable indexed family of disjoint sets $\family {F_n}_{n \mathop \in \N}$ defined by:

$\ds F_k = E_k \setminus \paren {\bigcup_{j \mathop = 0}^{k \mathop - 1} E_j}$

satisfying:

$\ds \bigsqcup_{n \mathop \in \N} F_n = \bigcup_{n \mathop \in \N} E_n$

where $\bigsqcup$ denotes disjoint union.


Corollary

The countable family $\family {F_k}_{k \mathop \in \N}$ can be constructed by:

$\ds F_k = \bigcap_{j \mathop = 0}^{k \mathop - 1} \paren {E_k \setminus E_j}$


General Result

Let $I$ be a set which can be well-ordered by a well-ordering $\preccurlyeq$.

Let $\family {E_\alpha}_{\alpha \mathop \in I}$ be a countable indexed family of sets indexed by $I$ where at least two $E_\alpha$ are distinct.


Then there exists a countable indexed family of disjoint sets $\family {F_\alpha}_{\alpha \mathop \in I}$ defined by:

$\ds F_\beta = E_\beta \setminus \paren {\bigcup_{\alpha \mathop \prec \beta} E_\alpha}$

satisfying:

$\ds \bigsqcup_{\alpha \mathop \in I} F_n = \bigcup_{\alpha \mathop \in I} E_n$

where:

$\bigsqcup$ denotes disjoint union.
$\alpha \prec \beta$ denotes that $\alpha \preccurlyeq \beta$ and $\alpha \ne \beta$.


Proof

Denote:

\(\ds E\) \(=\) \(\ds \bigcup_{k \mathop \in \N} E_k\)
\(\ds F\) \(=\) \(\ds \bigcup_{k \mathop \in \N} F_k\)

where:

$\ds F_k = E_k \setminus \paren {\bigcup_{j \mathop = 0}^{k \mathop - 1} E_j}$


We first show that $E = F$.


That $x \in E \implies x \in F$ follows from the construction of $F$ from subsets of $E$.

Thus $E \subseteq F$.


Then:

\(\ds x\) \(\in\) \(\ds \bigcup_{k \mathop \in \N} F_k\)
\(\ds \leadsto \ \ \) \(\ds \exists k \in \N: \, \) \(\ds x\) \(\in\) \(\ds F_k\)
\(\ds \leadsto \ \ \) \(\ds \exists k \in \N: \, \) \(\ds x\) \(\in\) \(\ds E_k\)
\(\, \ds \land \, \) \(\ds x\) \(\notin\) \(\ds \paren {E_0 \cup E_1 \cup E_2 \cup \cdots \cup E_{k - 1} }\)
\(\ds \leadsto \ \ \) \(\ds \exists k \in \N: \, \) \(\ds x\) \(\in\) \(\ds E_k\) Rule of Simplification

so $F \subseteq E$.


Thus $E = F$ by definition of set equality.


To show that the sets in $F$ are (pairwise) disjoint, consider an arbitrary $x \in F$.

Then $x \in F_k$ for some $F_k$.

By the Well-Ordering Principle, there exists a smallest such $k$.

Then:

$\forall j < k: x \notin F_j$

Choose any distinct $\ell, m \in \N$.

We have:


If $m > \ell$, then:

\(\ds x \in F_\ell\) \(\implies\) \(\ds x \in E_\ell\)
\(\ds x \in F_m\) \(\implies\) \(\ds x \notin E_m\)

If $m < \ell$, then:

\(\ds x \in F_m\) \(\implies\) \(\ds x \in E_m\)
\(\ds x \in F_\ell\) \(\implies\) \(\ds x \notin E_\ell\)


So the sets $F_\ell, F_m$ are disjoint.

Thus $F$ is the disjoint union of sets equal to $E$:

$\ds \bigcup_{k \mathop \in \N} E_k = \bigsqcup_{k \mathop \in \N} F_k$

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Union_of_Indexed_Family_of_Sets_Equal_to_Union_of_Disjoint_Sets&oldid=518552"