0
$\begingroup$

Say you have a set $A_i$ for $i$ in the natural numbers $\mathbb{N}$, and that is a countable set. Then for all natural numbers $n$, the union of those sets is countable.

I must prove this by induction, and I do realize that to do that, I must show that there is an injection( or surjection ) between the first two sets. Everything should follow accordingly afterwards, but I had the idea to utilize Cantor's Diagonal Argument in the inductive proof, but I am not sure how to go about defining injections for the argument in a way that shows that the sets are countable.

$\endgroup$
4
  • 1
    $\begingroup$ So, you're trying to prove that a countable union of countable sets is countable? While that's true, I don't think proving it by induction is appropriate, as (unless I'm missing some really creative idea) induction will only ever show that finite unions of countable sets are countable. $\endgroup$ – Theo Bendit Oct 25 '18 at 2:25
  • $\begingroup$ Why would you use the diagonal argument? That's a way to prove something is not countable. $\endgroup$ – Matt Samuel Oct 25 '18 at 2:27
  • $\begingroup$ Also (again, unless I'm missing something really creative), Cantor's diagonal argument will only ever show a set is strictly larger than a given cardinality, not equal to a given cardinality. You'll need to construct the maps explicitly. $\endgroup$ – Theo Bendit Oct 25 '18 at 2:28
  • $\begingroup$ For aall natural numbers $n$ the union of WHAT sets is countable? All of the sets $A_i$? No, must be something to do with $n$, I guess. The union of all the sets $A_i$ for $i\gt n$ is countable? It would help a lot if we know what sets you were trying to prove countable. $\endgroup$ – bof Oct 25 '18 at 9:25
0
$\begingroup$

Are you talking about a finite union of countable sets? If so, for the induction hypothesis write $$ \cup_{i=1}^n A_i=(\cup_{i=1}^{n-1}A_i)\cup A_n. $$ Now both sets on the right hand side are countable, so there is a surjection from $\mathbb{N}$ to each of them. Can you turn this into a surjection from $\mathbb{N}$ to their union, possibly by splitting $\mathbb{N}$ into $\mathbb{N}=\{2k:k\in \mathbb{N}\}\cup \{2k+1:k\in \mathbb{N}\}$?

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