Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A union of finite sets can always be converted to a union of finite disjoint sets.

I was wondering if a union of countable sets can always be converted to a union of countable disjoint sets? If yes how to do that?

Thanks!


Update with Paul's question:

"I wonder about the natural extension of this question to uncountable unions. Can we always refine an arbitrary set {Aα} to {Bα} (i.e. with Bα⊂Aα for each α) such that ⋃αBα=⋃αAα? The answer below uses countability pretty blatantly and I can't think of a way to do it without. "

Thanks!

share|improve this question
    
I wonder about the natural extension of this question to uncountable unions. Can we always refine an arbitrary set $\{A_\alpha\}$ to $\{B_\alpha\}$ (i.e. with $B_\alpha\subset A_\alpha$ for each $\alpha$) such that $\bigcup_\alpha B_\alpha=\bigcup_\alpha A_\alpha$? The answer below uses countability pretty blatantly and I can't think of a way to do it without. –  Paul VanKoughnett Oct 28 '10 at 1:55
    
I also would like to know about that! I will add it to my post. –  Tim Oct 28 '10 at 2:03
1  
@Paul: You could use a well-ordering of the index set to do the same thing in the uncountable case. But I don't know what can be said without the axiom of choice. –  Jonas Meyer Oct 28 '10 at 2:05

1 Answer 1

up vote 12 down vote accepted

Given $A_1,A_2,\ldots$, let $B_1=A_1$, and for $n\gt1$, $B_n=A_n\setminus\cup_{k=1}^{n-1}A_k$. Then for $m\lt n$, $B_m$ is contained in $A_m$ while $B_n$ is contained in $A_n\setminus A_m$, so $B_m$ and $B_n$ are disjoint. You can check that $\cup_{k=1}^n B_k=\cup_{k=1}^n A_k$ for all $n$, and $\cup_{k=1}^\infty B_k=\cup_{k=1}^\infty A_k$.

If you have a collection of sets indexed by an arbitrary set, then assuming the axiom of choice you can put a well-order on the index set. Given $\{A_i\}_{i\in I}$, where $(I,\lt)$ is a well-ordered set, we can define $\{B_i\}_{i\in I}$ as follows. Let $B_{i_0}=A_{i_0}$, where $i_0$ is the least element of $I$, and for $i\gt i_0$, $B_i=A_i\setminus\cup_{j\lt i}A_j$.

share|improve this answer
    
Thank you, Jonas! Do you know about the way for the uncountable case as asked by Paul? –  Tim Oct 28 '10 at 2:05
    
The difference is that to show that the unions are equal you can use transfinite induction, instead of ordinary induction. Hopefully someone more knowledgeable in set theory will correct me if I've made a mistake. –  Jonas Meyer Oct 28 '10 at 2:39
    
+1 for answering the general case. Well-ordering rules! –  Paul VanKoughnett Oct 28 '10 at 5:37

Your Answer

 
discard

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.