0
$\begingroup$

I am trying to prove the following claim:

The union of a finite or countable number of sets each of power $c$ is itself of power $c$.

My idea is to use induction, but I cannot finish the proof when there are two sets. Here is what I thought: if $I_1$ and $I_2$ both have continuum cardinality and $I_1\cap I_2=\emptyset$ then it is straightforward to prove. I cannot figure out how to prove if their intersection is non-empty. Any help would be great!

$\endgroup$
  • 1
    $\begingroup$ Have you learned the Cantor-Schröder-Bernstein Theorem? That would be one way to finish it off. $\endgroup$ – dfeuer Oct 18 '13 at 19:42
  • 1
    $\begingroup$ Have you considered that $\max(|I_1|,|I_2|)\le |I_1\cup I_2|\le |I_1|+|I_2|$? $\endgroup$ – abiessu Oct 18 '13 at 19:42
  • $\begingroup$ @dfeuer: Could you please give a hint how to use CBT? So their union has subset equinumerous with one of the sets, but again I can't find the other way around $\endgroup$ – user64066 Oct 18 '13 at 19:52
  • $\begingroup$ Study abiessu's comment and make the appropriate substitutions. $\endgroup$ – dfeuer Oct 18 '13 at 19:54
2
$\begingroup$

Here's a hint:

  1. Show that $\Bbb{R\times R}$ has size $\frak c$.
  2. Let $A_n$ be your sets which are disjoint (without loss of generality), choose for each $n$ an injection $f_n\colon A_n\to\Bbb R$.
  3. Consider now $A=\bigcup A_n$ and $f(a)=\langle n,r\rangle$ if and only if $a\in A_n$ and $f_n(a)=r$. Show that $f$ is an injection.

Note the use of the axiom of choice in the second part. It is essential and we can prove that the following situation is consistent with the failure of the axiom of choice: the union of countably many sets of size continuum does not have size continuum anymore.

$\endgroup$
  • 1
    $\begingroup$ Instead of your step 1, one can easily show that $(n,n+1)$ has cardinality $c$; next, step 2 consists in choosing an injection $f_n\colon A_n\to(n,n+1)$. Your argument, OTOH, can be used for showing that the union of a family of $c$ sets having size at most $c$ has size at most $c$. $\endgroup$ – egreg Oct 18 '13 at 20:18
  • $\begingroup$ I agree with your suggestion. One can even take $f_n$ to be into $(0,1)$ and then have $f(a)=n+f_n(a)$ for $a\in A_n$ instead. However I find the first step to be even more important than the subsequent ones in the general scheme of elementary set theory. So from a pedagogical point of view, I think it's better to leave it there. $\endgroup$ – Asaf Karagila Oct 18 '13 at 20:23
  • $\begingroup$ Of course a bijection $X\times X\to X$ (for infinite $X$) can be used for proving deeper results. But it requires stronger arguments to be proved in general. It all depends on the progression one chooses for presenting the theory. $\endgroup$ – egreg Oct 18 '13 at 20:29
  • $\begingroup$ @egreg: Yes, but unlike the general case, the case for $\Bbb R$ can be achieved with very basic cardinal arithmetics and the Cantor-Bernstein theorem (neither of which would require the axiom of choice, actually). And it is after all one of the most important results of elementary set theory. As Cantor wrote "I see it, but I don't believe it!" $\endgroup$ – Asaf Karagila Oct 18 '13 at 20:40
0
$\begingroup$

I don't know, but I suspect this may get at your problem:

Lemma: Let $\mathcal T$ be a set of sets. Then $$\left|\bigcup\mathcal T\right|\le\left|\bigsqcup\mathcal T\right|\le\left|\mathcal T\times\max\bigl\{|T|: T\in\mathcal T\bigr\}\right|,$$ where $\bigsqcup$ represents disjoint union.

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