# Let $X$ and $Y$ be countable sets. Then $X\cup Y$ is countable

Since $X$ and $Y$ are countable, we have two bijections:

(1) $f: \mathbb{N} \rightarrow X$ ;

(2) $g: \mathbb{N} \rightarrow Y$.

So to prove that $X\cup Y$ is countable, I figure I need to define some function,

h: $\mathbb{N} \rightarrow X\cup Y$

Thus, I was wondering if I could claim something similar to the following:

since we have (1) & (2) it follows that we also have the bijections

$\alpha : \{n\in \mathbb{N} : n = 2k + 1, k\in \mathbb{N}\} \rightarrow X$;

$\beta : \{n\in \mathbb{N} : n = 2k, k\in \mathbb{N}\} \rightarrow Y$;

because we have bijections from $\mathbb{N}$ to the evens and odds respectively.

Then define $h := \alpha$ for odd $n$, $h := \beta$ for even $n$.

Thus, since $\forall n\in \mathbb{N}$(either $n$ is even or $n$ is odd but not both) $h$ is a bijection from $\mathbb{N}$ to $X\cup Y$.

Thanks for reading, and for answering if you answer. I'm just really unsure if my logic holds here, or if I'm even approaching this right because I've been stuck on this problem for a little while today.

p.s sorry for asking so many questions recently, I'm trying to study on my own and apparently I get confused and stuck more easily than I thought I would without a teacher.

EDIT: (1) fixed the even and odd. (2) I do mean countably infinite. My bad, going through some notes I found online they were using the notation of "countable" for what you call "countably infinite", and "at most countable" for what you called "countable" (3) Thanks for the good answers, I do see now that this makes breaks down when they are not disjoint, but at least I'm not too far off.

-
@Theo you're definitely right. I'll fix it – Deven Ware Aug 15 '11 at 0:04
@Deven: While it is always best to be clear as possible and use "countably infinite" (or at least note that you require the sets to be infinite somewhere), it is a matter of convention whether or not countable means infinite or not. – Asaf Karagila Aug 15 '11 at 0:27
I'm starting to get dizzy by the recent flood of [cardinals] related questions. Am I being too quick on the retags or am I just being more vigilant? – Asaf Karagila Aug 15 '11 at 0:47

By countable you seem to mean countably infinite. That may not be the formal definition in your book. The formal definition of countable that I am more accustomed to is that a set $S$ is countable if there is a bijection between $S$ and a subset of $\mathbb{N}$.

If the more general definition is the formal definition of countable used in your book, you will need to either break up the proof into a number of cases, or write an argument that simultaneously covers all cases. That can be done, but there will be greater clarity if you take the number of cases approach.

For countably infinite sets $X$ and $Y$, the proof technique that you used is very good if $X$ and $Y$ are disjoint. The notation that you used is not familiar to me. It is clear what you intend the functions $\alpha$ and $\beta$ to do. It would have been relatively easy to be totally explicit, as follows.

If $n$ is odd, then $h(n)=f((n+1)/2)$; if $n$ is even then $h(n)=g(n/2)$.

You will need to modify your method to take care of the cases where $X$ and $Y$ are not disjoint. The intuition is clear, and even, informally, a procedure for finding a bijection. But it is a very good idea to write out all of the details.

I hope this gives a good way to begin. I can append more details if you like.

-
Andre: In many places countable is used solely for countably infinite. – Asaf Karagila Aug 14 '11 at 23:53
@Asaf Karagila: Out of curiosity I just checked Wikipedia, the source of all knowledge. It uses the classical (one-to-one correspondence with a subset of the natural numbers) definition. Certainly in informal speech, we do often say countable to mean countably infinite. – André Nicolas Aug 15 '11 at 0:01
Quoting from Jech, Set Theory, 3rd Millennium ed. (p. 30): "Sets whose cardinality is $\aleph_0$ are called countable; a set is at most countable if it is either finite or countable.", it is really a matter of convention. – Asaf Karagila Aug 15 '11 at 0:23
The definition given by Asaf is essentially the definition I have worked with. Also thanks, can you try to push me in the direction of fixing the problem with them needing to be disjoint without giving me the answer. Thank you if you can, if not I will work on it myself soon and append the original post if I get anything. – Deven Ware Aug 15 '11 at 0:33
@Deven: There is a hint in a comment to the answer by mixedmath. Consider separately the situation in which $X\setminus Y$ is finite and when it is infinite, if you want. – Arturo Magidin Aug 15 '11 at 0:51

Your intuition is correct. The mechanics of your proof lack just a bit. For example, what if an element is in both $X$ and $Y$? Then your proposed function is not a bijection.

But that is not so hard to fix.

-
Hint: $X \cup Y = (X \setminus Y) \cup Y$ – Austin Mohr Aug 15 '11 at 0:05
@Austin Mohr thanks for the hint :) – Deven Ware Aug 15 '11 at 0:52