6
$\begingroup$

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.

  • 0
    @Theo you're definitely right. I'll fix it2011-08-15
  • 0
    @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.2011-08-15
  • 0
    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?2011-08-15

2 Answers 2

3

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.

  • 0
    Andre: In many places *countable* is used solely for *countably infinite*.2011-08-14
  • 0
    @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.2011-08-15
  • 1
    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.2011-08-15
  • 0
    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.2011-08-15
  • 1
    @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.2011-08-15
2

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.

  • 5
    Hint: $X \cup Y = (X \setminus Y) \cup Y$2011-08-15
  • 0
    @Austin Mohr thanks for the hint :)2011-08-15