2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – JMoravitz Mar 21 '17 at 23:50
  • $\begingroup$ 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$. $\endgroup$ – JMoravitz Mar 21 '17 at 23:52
  • $\begingroup$ @JMoravitz Thank you for the detail. This is very helpful $\endgroup$ – Sithe Mar 22 '17 at 0:05
3
$\begingroup$

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

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

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

$\endgroup$
  • 2
    $\begingroup$ This list may have repeated elements. $\endgroup$ – vadim123 Mar 22 '17 at 0:04
  • $\begingroup$ @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. $\endgroup$ – Bram28 Mar 22 '17 at 1:06
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – fleablood Mar 22 '17 at 0:07

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.