# Disjoint Union Proof

1. Jan 13, 2012

### the_kid

1. The problem statement, all variables and given/known data
A$_{1}$, A$_{2}$, A$_{3}$,... are countable sets indexed by positive integers. I'm looking to prove that the disjoint union of these sets is countable.

2. Relevant equations

3. The attempt at a solution
I can't figure out how to enter the form of the disjoint union in this interface, but I'm using the one listed on Wikipedia (http://en.wikipedia.org/wiki/Disjoint_union). So, I understand that when looking to prove that a single set, S, is countable, one must show that there exists a bijection from the N-->S. However, I'm confused about how I'd show this for the disjoint union. It seems to me that this bijection is almost implicit in the definition of the disjoint union. I.e. the disjoint union indexes each element according to which set it came from. I'm looking for some help getting started with this.

2. Jan 13, 2012

### Dick

Did you prove that the rational numbers are countable? It's essentially the same proof with some changes of notation.

3. Jan 13, 2012

### LCKurtz

I would try thinking about listing the elements of the sets in an infinite square array and moving along diagonals.

4. Jan 13, 2012

### the_kid

Thanks for the replies! So, from the definition, the disjoint union gives pairs (x, i) : x$\in$S$_{i}$. I'm looking at my proof of why Q is countable: It begins with showing that if S and T are countable sets, then so is S X T. What would be the analogous argument for the disjoint union?

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook