Showing $A \cup B \cup C$ is countable if $A, B$ are countable and $C$ is finite.

How does one go about showing $A \cup B \cup C$ is countable if $A, B$ are countable and $C$ is finite?

I understand most of the confusion for resolving set theory questions online seem to be the definition. For my course we consider the following definitions:

countable: Finite or $A \sim\mathbb{N}$

uncountable: not countable

finite: The empty set or $A \sim J_n$ where $n \in \mathbb{N}$

infinite: not finite

So I'm not sure if I have this right but looking at the above definitions the way I'm looking to approach this is to consider 6 different cases.

1. Where C is the empty set and A, B are both finite sets
2. Where C is the empty set and A is finite and B is countably infinite
3. Where C is the empty set and both A, B are countably infinite

4 - 6. Repeated above but with C being a non-empty finite set

This seems like quite a round about way but intuitively it seems to me like the only way to cover all bases according to the definitions. I'm hoping I might be absolutely wrong on this. Is there a simpler way to prove this?

• You can reduce the time taken by first proving the lemma $A$ and $B$ both countable implies $A\cup B$ countable. By using the lemma twice you show $A\cup B\cup C = (A\cup B)\cup C$ is countable by noting that it is the union of two countable sets since what is in the parenthesis is also a countable set. Further cut down on the number of cases by saying "Without loss of generality suppose $|A|\leq |B|$" before working too hard since any situation where $|B|<|A|$ is proven the same way by a relabeling of the sets. Also, treat empty sets during the same case as finite sets. – JMoravitz Mar 21 '17 at 23:50
• You now need only prove the following three cases: $A$ finite and $B$ finite, $A$ finite and $B$ countably infinite, and $A$ countably infinite and $B$ countably infinite. In any of those cases, try to find a bijection between $A\cup B$ and a subset of $\Bbb N$. – JMoravitz Mar 21 '17 at 23:52
• @JMoravitz Thank you for the detail. This is very helpful – Sithe Mar 22 '17 at 0:05

If $A$ and $B$ are countable, then they can be enumerated, respectively, as:

$a_1, a_2, a_3, \ldots$ and $b_1, b_2, b_3, \ldots$

Since $C$ is finite, its elements can be listed as: $c_1, c_2, \ldots, c_n$.

To prove the union of all three is countable, it will suffice to list them in some order $d_1, d_2, d_3, \ldots$, since there is then a natural bijection with $\mathbb{N}$ in which we match $d_k$ with $k \in \mathbb{N}$.

As to the listing for this union, you could list all of $C$, then interweave enumerations of $A$ and $B$:

$c_1, c_2, \ldots, c_n, a_1, b_1, a_2, b_2, a_3, b_3, \ldots$

(You may also specify that no element is listed more than once.)

If either of $A$ or $B$ is finite (since your definition of countable allows for this) then the listing can be tweaked appropriately, e.g., if just $A$ is finite, then list all elements of $C$, then of $A$, and then enumerate $B$.

• We must have been typing in synchrony ... Great answer by the way!! – Bram28 Mar 21 '17 at 23:56
• Thank you. I've never seen countability being proven that way. It's very straight forward and I like it – Sithe Mar 22 '17 at 0:00
• Slight thing to watch out for if the sets aren't disjoint. But just skip them if they do. That's acceptable "tweaking". – fleablood Mar 22 '17 at 0:04
• This is an injection, not necessarily a bijection, because $A\cap B$ might not be empty. – vadim123 Mar 22 '17 at 0:04
• Okay, I missed that. – fleablood Mar 22 '17 at 0:09

Sets are countable if and only if their elements are 'listable'.

Now, $C$ is finite, so say it contains elements $c_1, c_2, ..., c_n$ for some $n$

$A$ is countable, so we can create a list:

$a_1, a_2, ...$

Same for $B$:

$b_1, b_2, ...$

So, I would create the following list:

$c_1, c_2, ..., c_n, a_1, b_1, a_2, b_2, ...$

• This list may have repeated elements. – vadim123 Mar 22 '17 at 0:04
• @vadim123 sure, but they can be removed if we really wanted to define an injection. So as long as every element appears somewhere on the list, we're fine. – Bram28 Mar 22 '17 at 1:06

Let $j_a: A \rightarrow \mathbb N$ be an injection. We know that is possible because $A$ is countable.

Let $j_b: B \rightarrow \mathbb N$ be an injection. We know that is possible because $B$ is countable.

Let $j_c: B \rightarrow \mathbb N_j$ be an bijection. We know that is possible because $C$ is finite.

Let $k:A\cup B\cup C \rightarrow \mathbb N$ via $k(x) = 3*j_a(x)$ if $x \in A$. If $x \in B$ but $x \not \in A$ let $k(x) = 3*j_b(x) + 1$. And if $x \in C$ but $x \not \in A$ and $x \not \in B$ let $k(x) = 3*j_c(x) + 2$.

Show that $k$ is an injection and that shows $A\cup B \cup C$ is countable.

Another way to think of it is to start by picking out the first element of $A$ then pick the first element of $B$, then of $C$, then pick the second element, then the third elements and so on. That's a list of all the elements. Since they can be listed one after another they are countable.

• And before vadim points out there'll be many elements of N not mapped into, I'll point out as long as there is an injection into N that is sufficient to prove countabity. It need not be onto. But it can be made onto if it is infinite. But it is not nescessary. – fleablood Mar 22 '17 at 0:07