I need to prove that the union of two countable sets is countable. I have seen some solutions on this website and others, but they are all too complicated for my background. Could someone suggest a basic proof for this and explain the intuition?

  • $\begingroup$ Which is your definition of countable? $\endgroup$ – Brandon Jan 22 '14 at 2:08
  • $\begingroup$ A countable set has the cardinality of natural numbers. $\endgroup$ – user120494 Jan 22 '14 at 2:09

Example of two countable sets:

$$\{2, 4, 6, 8, \dots\}$$ $$\{1, 3, 5, 7, \dots\}$$

What is their union? It's all of the natural numbers. However, think about it this way. "Zip" the two sets together to get

$$\{1, 2, 3, 4, 5, 6, 7, 8, \dots\}.$$

Will anything change in general?

  • $\begingroup$ This seems very intuitive to me, but the proofs I see online have complicated bijections, inductions etc so I wonder if I am missing something by adopting such reasoning. $\endgroup$ – user120494 Jan 22 '14 at 2:13
  • 1
    $\begingroup$ The thing about countable sets is that if you're concerned about cardinality only, then the natural numbers are just as good an example as any (as they are all, by definition, bijectively equivalent). So technically this is actually just a proof (this argument is made clear in a little more detail in my post above). $\endgroup$ – Sempliner Jan 22 '14 at 2:16
  • 1
    $\begingroup$ The question is how do you make it precise? A set is countable if you have a bijection $f:A\to N$, the natural numbers. Let $E$ be the even numbers and $O$ the odd numbers. Show there are bijections $f:N \to O$ and $g:N \to E$, and finally a bijection $h:E \cup O \to N$. Then given two countable sets $A$ and $B$, construct a bijection using the above functions $A\cup B$ to $N$. (You'll have to use a case structure.) $\endgroup$ – abnry Jan 22 '14 at 2:17
  • $\begingroup$ And what would be the different cases here in the case structure proof? $\endgroup$ – user120494 Jan 22 '14 at 2:45
  • $\begingroup$ The bijection $f:A\cup B \to O \cup E$. Hopefully you can write down bijections $F:A\to O$ and $G:B \to E$. Then define the bijection $f(x)$ when $f(x)=F(x)$ if $x\in A$ and $f(x)=G(x)$ if $x\in B$. $\endgroup$ – abnry Jan 22 '14 at 2:48

I think a basic proof would show that the odd and even numbers are countable, and then map the odd numbers onto one set in the union, and the even numbers onto the other set (you get a map from the odds/evens to the naturals, then you compose with the map sending the naturals to one of the sets in the union). This is sort of just saying that if you have an infinite thing you can divide it into subsets that are the same size as it (the definition of being infinite). You would have to handle the special case where the two sets share all but finitely many points with this proof, but that should be easy.

  • $\begingroup$ So you are saying that I can divide the infinite union into odd and even components, the sets of which should be countable? + the special case when the two sets have infinite overlap? $\endgroup$ – user120494 Jan 22 '14 at 2:15
  • $\begingroup$ Well sort of. What we're trying to find is a bijection between $\mathbb N$ and our set. Now since we know both sets have their own bijections between themselves and $\mathbb N$. In other words there exists $\sigma, \pi$ bijections such that $\sigma(A) = \mathbb N$ and $\pi(B) = \mathbb N$, where $A \cup B$ is the union in question. One way to do this is to map half of $\mathbb N$ to one and the other half to the other, making use of these bijections. The easiest way to describe cutting $\mathbb N$ in half doing the above. The special case is just when you only add finitely many things. $\endgroup$ – Sempliner Jan 22 '14 at 2:21

Your Answer

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