1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Countable infinite sets

  1. Sep 12, 2007 #1
    1. The problem statement, all variables and given/known data
    Why is the union of two countably infinite sets countably infinite?


    2. Relevant equations



    3. The attempt at a solution

    So, you have bijections with the naturals for each of the two sets and you need to find a new bijection from the naturals to their union. It seems impossible to me.
     
  2. jcsd
  3. Sep 12, 2007 #2
    Hint: Consider all possible intersections
     
    Last edited: Sep 12, 2007
  4. Sep 12, 2007 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Uh, why? You're supposed to assume that the two sets are disjoint.

    It might help to think the other way round: there are bijections from X to N and Y to N. Now, if only there were two proper subsets of N that were disjoint and each in bijection with N (this is clearly an equivalent problem - whenever you have a question about countable sets, you can replace all of them with a (different) copy of N by definition)....
     
  5. Sep 12, 2007 #4
    That was not stated in the original post, but it does make the proof shorter and simpler.
     
  6. Sep 12, 2007 #5
    But there aren't!! That sentence just seems manifestly contradictory to me.
     
  7. Sep 12, 2007 #6

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    Hint (I hope): [tex]\{ 0, 2, 4, 6, 8, \cdots \} \cup \{ 1, 3, 5, 7, 9, \cdots \} = \mathbb{N}[/tex].
     
  8. Sep 12, 2007 #7
    I am still not convinced. If you have two sets with the same number of elements as each other and as the set of natural numbers (they are countably infinite). How can you add those elements together without the cardinality of the set increasing?
     
  9. Sep 12, 2007 #8
    you can easily construct disjoint sets if you can't assume they are:

    A u B = A u (B - A intersection B)
     
  10. Sep 12, 2007 #9
    If you think that, your idea of cardinality is wrong. Two sets have the same cardinality iff there exists a bijection between them. No other definition is acceptable. Thus, the even and odd numbers have the same cardinality, because you can use (+1) as a bijective mapping to go from the evens to the odds. At the same time, they are both bijective to the natural numbers, in a fairly obvious manner. Thus, the three sets have the same cardinality.
     
  11. Sep 12, 2007 #10
    Interesting.
     
  12. Sep 12, 2007 #11

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    A set having a proper subset of the same cardinality as itself is the basic definition of 'infinite'.
     
  13. Sep 12, 2007 #12

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    It doesn't bloody well need to be (it is the 'worst case scenario'), and doesn't alter the fact that your suggestion wasn't at all helpful.
     
  14. Sep 13, 2007 #13
    Not for us, but for one (the OP) who is just learning (for what may be the first time, presumably from the posts) about sets and cardinality, such a statement may warrant a proof \
     
    Last edited: Sep 13, 2007
  15. Sep 13, 2007 #14
    What does OP stand for?
     
  16. Sep 13, 2007 #15
    Original poster or original post. It's usually good for focusing the discussion on the actual topic of the thread. Which ironically, we've now failed to do. :blushing:
     
  17. Sep 13, 2007 #16

    learningphysics

    User Avatar
    Homework Helper

    The case where the two sets are disjoint seems like the most straightforward one to me... construct a bijection from the first set to the odds... second to the evens... thereby constructing a bijection of the union to the naturals...

    But in the case of the two sets intersecting constructing such a bijection seems less straightforward to me. particulary the case of an infinite intersection.
     
  18. Sep 13, 2007 #17

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Sigh. If you read the other posts here someone pointed out what to do if you really want to consider the idea of intersecting sets: replace XuY with Xu(Ynx^c).
     
  19. Sep 13, 2007 #18
    Post #2

    Clearly the intersection of countable sets A,B is itself countable, since [tex]\left| {A \cap B} \right| \leqslant \left| A \right|[/tex].
    Hence the intersection is either finite or countably infinite.

    Finite case: Let
    [tex]\begin{gathered}
    C = A \cap B,\;\left| {A \cap B} \right| = N \in \mathbb{N} \hfill \\
    D = A - C \hfill \\
    E = B - C \hfill \\
    \end{gathered} [/tex]
    Your bijection could be
    [tex]b\left( n \right) = \left\{ \begin{gathered}
    c_n ,\;n \leqslant N \hfill \\
    d_n ,\;n > N \wedge n\;{\text{is odd}} \hfill \\
    e_n ,\;n > N \wedge n\;{\text{is even}} \hfill \\
    \end{gathered} \right.[/tex]

    Countably infinite case: Let
    [tex]
    \begin{gathered}
    C = A \cap B,\;\left| {A \cap B} \right| = \left| \mathbb{N} \right| \hfill \\
    D = A - C \hfill \\
    E = B - C \hfill \\
    \end{gathered} [/tex]
    Your bijection could be
    [tex]b\left( n \right) = \left\{ \begin{gathered}
    c_n ,\;n\bmod 3 = 0 \hfill \\
    d_n ,\;n\bmod 3 = 1 \hfill \\
    e_n ,\;n\bmod 3 = 2 \hfill \\
    \end{gathered} \right.[/tex]

    **Edit:
    That essentially is the idea, hinted in previous posts but not quite so quickly received
     
    Last edited: Sep 13, 2007
  20. Sep 13, 2007 #19
    Guys... we're drifting a bit from the original problem.
     
  21. Sep 13, 2007 #20
    The question was pretty much answered a few posts ago. Consider two disjoint sets (this can be done by making the replacements either me or Matt stated). Then use the fact that N is bijective with Z and it follows pretty immediately (map one set to positives and the other to negatives and chuck out 0).

    It might be a good exercise for the OP to see if as a corollary he can prove that a countable union of countable sets is countable.
     
    Last edited: Sep 13, 2007
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?