Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Disjoint Union Proof

  1. Jan 13, 2012 #1
    1. The problem statement, all variables and given/known data
    A[itex]_{1}[/itex], A[itex]_{2}[/itex], A[itex]_{3}[/itex],... 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. jcsd
  3. Jan 13, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper

    Did you prove that the rational numbers are countable? It's essentially the same proof with some changes of notation.
  4. Jan 13, 2012 #3


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I would try thinking about listing the elements of the sets in an infinite square array and moving along diagonals.
  5. Jan 13, 2012 #4
    Thanks for the replies! So, from the definition, the disjoint union gives pairs (x, i) : x[itex]\in[/itex]S[itex]_{i}[/itex]. 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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook