# Prove that if sets $A$ and $B$ are countable, then their union $A\cup B$ is countable

Prove that if sets $A$ and $B$ are countable, then their union $A\cup B$ is countable.

I'm really confused because I'm not sure if $A$ and $B$ are finite or infinite. If I have to consider every case, then there will be $4$ cases. Also I'm not sure if $A$ and $B$ are disjoint. If they are not, then their common element would show up only once in $A\cup B$. Is there a way to avoid dealing with all these as separate cases?

• en.wikipedia.org/wiki/Countable_set – Surb Dec 20 '14 at 23:20
• So, you have a few cases. Why would that be cause for confusion? – Andrés E. Caicedo Dec 20 '14 at 23:20
• and by symmetry you have only three cases ($A\cup B = B \cup A$) – Surb Dec 20 '14 at 23:20

To remedy confusions like yours and to avoid the needless case analyses, I prefer to define $X$ to be countable if there is a surjection from $\mathbb{N}$ to $X$. This definition is equivalent to a few of the many definitions of countability, so we are not losing any generality. It is a matter of convention whether we allow finite sets to be countable or not (though, amusingly, finite sets are the only ones whose elements you could ever finish counting).

So, if $A$ and $B$ be countable, let $f:\mathbb{N}\to A$ and $g:\mathbb{N}\to B$ be surjections. Then the two sequences $(f(n):n\geqslant 1) = (f(1), f(2), f(3), \dotsc)$ and $(g(n):n\geqslant 1) = (g(1), g(2), g(3), \dotsc)$ eventually cover all of $A$ and $B$, respectively; we can interleave them to create a sequence that will surely cover $A\cup B$: $$(h(n):n\geqslant 1) := (f(1), g(1), f(2), g(2), f(3), g(3), \dotsc).$$ An explicit formula for $h$ is $h(n) = f((n+1)/2)$ if $n$ is odd, and $h(n) = g(n/2)$ if $n$ is even.

• how to deal with the case where a element is both in A and B? – XPN1122 Dec 21 '14 at 2:01
• It doesn't matter. With this definition, repeated mentions are allowed. Indeed, any surjection from $\mathbb{N}$ to a finite set must cover an element infinitely often. For countability, it does not matter if we count an element twice, thrice, or infinitely often. So if $x$ is in $A$ and in $B$, then $f$ will cover it at least once, $g$ will cover it at least once, and $h$ will cover it at least twice, which is fine, because all we want is simply that $x$ be covered. – Unit Dec 21 '14 at 2:07

Hint:

Case 1: Without loss of generality, suppose $A$ is finite with cardinality $n$ and $B$ is countably infinite. Then there exist bijections $f_{A}: A \to \mathbb{N}_{n} = \{1, 2, \dots, n\}$ and $f_{B}: B \to \mathbb{N}$. Is $A \cup B$ finite or countably infinite? How would you define such a bijection?

Case 2: Suppose $A$ and $B$ are both finite. Same thought process as case 1.

Case 3: Suppose $A$ and $B$ are both infinite. Same thought process as case 1.

First way:

If A and B are countable that you can numerate them. $A=\{a_1,a_2,...\}$ and $B=\{b_1,b_2,...\}$. So this means that you can numerate $A\cup B =\{a_1,b_1,a_2,b_2,...\}$.

Second way:

If A or B are finite then it is trivial. If they both are infinite, then there is a bijection between A and odd natural numbers, because they are both countable infinite. The same with B and even natural numbers. So it is not hard to define a bijection from $A\cup B$ to $\mathbb{N}$.

Hint: Suppose first that $A$ and $B$ are disjoint. Solve the problem.$^*$ If $A$ and $B$ are not disjoint, apply the result for disjoint sets to $(A\setminus B) \cup B$, using that $A \setminus B$ and $B$ are disjoint and $(A\setminus B) \cup B = A \cup B$.

$^*$: the finite cases are easy, you do them. Suppose $A$ and $B$ countably infinite. We have bijections $f_A: \Bbb N \to : A$, $f_B: \Bbb N \to B$. Define $f$ using $f_A$ and $f_B$ (hint inside a hint: odds and evens).

No need to separate it in different cases. You can use the fact that a set $A$ is countable if there is an injective function $f : A \rightarrow \mathbb{N}$. Let $g$ and $h$ are these injective functions for $A$ and $B$ respectively. Then you can build an injective function $f$ from $A \cup B$ to $\mathbb{N}$ this way : $f(x) = 2g(x)$ if $x \in A$ and $f(x) = 2h(x)+1$ if $x \in A \backslash B$.