# How to derive a union of sets as a disjoint union?

$$\bigcup_{n=1}^\infty A_n = \bigcup_{n=1}^\infty (A_{1}^c \cap\cdots\cap A_{n-1}^c \cap A_n)$$

The results is obvious enough, but how to prove this

-

For $n\in\Bbb Z^+$ let $B_n=A_n\setminus\bigcup_{k=1}^{n-1}A_k=A_n\cap\bigcap_{k=1}^{n-1}A_k^c$; you want to show that $$\bigcup_{n\ge 1}A_n=\bigcup_{n\ge 1}B_n\;.$$

Clearly it suffices to show that

$$\bigcup_{k\ge 1}A_k\subseteq\bigcup_{k\ge 1}B_k\;.$$

For $x\in\bigcup_{k\ge 1}A_k$ let $n(x)=\min\{k\in\Bbb Z^+:x\in A_k\}$; then $x\in B_{n(x)}\subseteq\bigcup_{k\ge 1}B_k$, and you’re done.

-
thanks for your effort, and id appreciate it if you could take a look at my another question which is ' how to prove the limsup equals liminf for a monotone class ', it seems no one interest in that question so far... –  Dylan Zhu Mar 11 '13 at 21:00

The $n$'s on the right side should be $i$'s (or the $i$ should be $n$).

For any $x$, the statement "there is an $i\in\mathbb N$ such that $x\in A_i$" is equivalent to "there is a smallest $i\in\mathbb N$ such that $x\in A_i$".

-
Essentially, this is a consequence of the well-ordering principle of $\mathbb N$. –  Thomas Andrews Mar 11 '13 at 20:05
@AndreasBlass sorry, ive changed it to n. thanks –  Dylan Zhu Mar 11 '13 at 20:12

This is a similar approach, but using different tools. It came out a bit over-formalized, but perhaps it still might be helpful to you.

You want to prove

$$\bigcup_{n=1}^\infty A_n = \bigcup_{n=1}^\infty (A_{1}^c \cap \ldots\cap A_{n-1}^c \cap A_{n})$$ or more concisely

$$\bigcup_{n=1}^\infty A_n = \bigcup_{n=1}^\infty\left(\bigcap_{k=1}^{n-1} A_k^c\right) \cap A_n.$$

This is equivalent to

$$\exists n.\ P(n) \iff \exists n.\ (\neg P(1) \land \ldots \land \neg P(n-1) \land P(n))$$

or

$$\exists n.\ P(n) \iff \exists n.\ \Big(\forall k < n. \neg P(k)\Big) \land P(n).$$

Of course $A \land B$ implies $B$ so the $\Leftarrow$ part is trivial. To prove $\Rightarrow$, set $$\mathcal{I} = \big\{n\ \big|\ P(n)\big\}.$$ By $\exists n. P(n)$ we know that $\mathcal{I}$ is non-empty. Now, observe that $\langle \{1,2,3,\ldots\},\leq\rangle$ is a well order (that is a well-founded total order), and as such $\mathcal{I}$ has the smallest element; name it $m$. By the definition of $\mathcal{I}$ we know that $\forall k < m.\ \neg P(k)$, and also $P(m)$, so we have constructed the desired $n$ from the right-hand side.

I hope that helps ;-)

-