2
$\begingroup$

Let $A_1,A_2,\ldots$ be a sequence of subsets of $\mathcal{X}$. Let $B_1=A_1$ and define $$ B_n=A_n\setminus \bigcup_{i=1}^{n-1}A_i \text{ for } n=2,3,\ldots $$

Show that $$ \bigcup_{i=1}^n B_i = \bigcup_{i=1}^n A_i \text{ for all } n\in\mathbb{N} $$

I can see why this is, intuitively, but I can't figure out how to construct a formal proof.

I can see that $\bigcup_{i=1}^n B_i\subset \bigcup_{i=1}^n A_i$, but how do I show the opposite?

$\endgroup$
0
$\begingroup$

HINT: If $x\in\bigcup A_i$, let $k$ be the least such that $x\in A_k$, show that $x\in B_k$. Finish the proof.

$\endgroup$
  • $\begingroup$ $x\in \bigcup_{i=1}^n A_i$. Let $k$ be the least index for which $x\in A_k$. Then $x\in A_k\setminus\bigcup_{i=1}^{k-1}A_i\Rightarrow x\in\bigcup_{i=1}^k B_k $. But does this imply that $\bigcup_{i=1}^n A_n \subset \bigcup_{i=1}^n B_n$? $\endgroup$ – Rud Faden Nov 16 '14 at 20:06
  • $\begingroup$ It means that $x\in B_k$ and therefore $x\in\bigcup B_i$. Therefore $\bigcup A_i\subseteq\bigcup B_i$, which is what you are asked for, no? $\endgroup$ – Asaf Karagila Nov 16 '14 at 20:08
  • $\begingroup$ Yes. I just wanted to be sure. Thanks $\endgroup$ – Rud Faden Nov 16 '14 at 20:10
  • $\begingroup$ Would this also work for infinite unions? E.i. $\bigcup_{i=1}^\infty B_n = \bigcup_{i=1}^\infty A_n$ $\endgroup$ – Rud Faden Nov 16 '14 at 20:15
  • $\begingroup$ Sure, if the index set is well-ordered (and in this case, the index set is $\Bbb N$) then we can make this argument. Note that from the axiom of choice we can always well-order the index set (although we might lose some of the natural properties of the index set, if we care for them). $\endgroup$ – Asaf Karagila Nov 16 '14 at 20:20
1
$\begingroup$

Suppose $x \in \bigcup_{i=1}^n A_i$. Then there is at least one $n\in\{1,2,3,\ldots\}$ for which $x\in A_n$. Let $n\in\{1,2,3,\ldots\}$ be the smallest index for which $x\in A_n$. Then $x\in A_n\smallsetminus\bigcup_{i=1}^{n-1} A_i=B_n$. Hence $x\in\bigcup_{n=1}^\infty B_n$.

Conversely, suppose $x\in\bigcup_{n=1}^\infty B_n$. Then $\exists n\ x\in (A_n\smallsetminus\text{something})$, so $x\in A_n$; hence $x\in\text{their union}$.

$\endgroup$
0
$\begingroup$

Hint: Suppose $x \in \cup_{i=1}^n A_i$. Consider the first index $j$ such that $x \in A_j$ (there is at least one, so there is a minimal one...).

$\endgroup$
0
$\begingroup$

Let $x\in\bigcup_{i=1}^nA_i$.

Find the smallest index $k\in\{1,\dots,n\}$ with $x\in A_k$.

Then $x\in B_k\subseteq\bigcup_{i=1}^nB_i$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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