Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$$\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

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
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$".

share|cite|improve this answer
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))$$


$$\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 ;-)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.