0
$\begingroup$

If $A_1$ and $A_2$ are countably infinite, and that $A_1\cap A_2=\phi$. Then prove that $A_1 \cup A_2$ is countably infinite.

My work:
As $A_1$ and $A_2$ are countably infinite, there exists a bijection $\theta_1: \mathbb{N}\to A_1$ and $\theta_2: \mathbb{N}\to A_2$. I need to prove now, that there exists a bijection $\theta : \mathbb{N}\to A_1\cup A_2$ which I am not able to find. Please help.

My knowledge about this topic is very limited and I have just started studying about all this.

$\endgroup$
1
  • 1
    $\begingroup$ Start by defining a bijection $\mathbb{N}\rightarrow\mathbb{N}\cup\mathbb{N}$, e.g. by mapping even numbers into the first and odd numbers into the second bucket. Then compose with your maps. $\endgroup$
    – Thomas
    Commented Mar 9, 2014 at 8:10

2 Answers 2

Reset to default
2
$\begingroup$

Define $\phi(2n) = \phi_1(n)$, $\phi(2n-1) = \phi_2(n)$.

$\endgroup$
1
$\begingroup$

Let's look at a trivial example for a moment. Suppose $A = \{a,b,c\}$ and $B = \{d,e\}$. One way of seeing that $A\cup B$ is countable is to right a list containing all the elements. One such list is $a,b,c,d,e$. But this doesn't generalize nicely to countably infinite lists, since we'd never finish $A$.

On the other hand, the list $a,d,b,e,c$, choosing an element from $A$, then an element from $B$, and vice versa, works very well.

In other words, you can explicitly create a list from the two lists you already have.

$\endgroup$
6
  • $\begingroup$ Yes, this is actually what I was thinking of, but is this a proper approach? $\endgroup$
    – Hawk
    Commented Mar 9, 2014 at 8:12
  • $\begingroup$ @Hawk: It's certainly valid, especially if you explicitly provide the map! Notice that's all that copper.hat has done. $\endgroup$
    – davidlowryduda ♦
    Commented Mar 9, 2014 at 8:14
  • $\begingroup$ You mean, I need to show the map, else it doesn't work right? $\endgroup$
    – Hawk
    Commented Mar 9, 2014 at 8:15
  • $\begingroup$ @Hawk: That depends on what you or your professor considers a complete proof, and the context. $\endgroup$
    – davidlowryduda ♦
    Commented Mar 9, 2014 at 8:17
  • $\begingroup$ Okay, I got it, thanks. $\endgroup$
    – Hawk
    Commented Mar 9, 2014 at 8:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .