2
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ how to deal with the case where a element is both in A and B? $\endgroup$ – XPN1122 Dec 21 '14 at 2:01
  • $\begingroup$ 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. $\endgroup$ – Unit Dec 21 '14 at 2:07
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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