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: Subsets of Uncountable Infinite Sets

  1. Feb 1, 2009 #1
    1. The problem statement, all variables and given/known data

    Let [tex]A[/tex] be an infinite set which is not countable and let [tex]B \subset A[/tex] be a countably infinite set.

    (1) Show that [tex]A - B[/tex] is also infinite and not countable

    (2) Show that [tex]A[/tex] and [tex]A - B[/tex] have the same cardinality

    2. Relevant equations

    Hints written directly:

    "Show that there is a countable subset [tex]C \subset (A - B)[/tex] and that there is a bijection [tex]g : C \cup B \rightarrow B[/tex], and try to make it into a bijection of [tex]A[/tex] with [tex]A - B[/tex]."

    3. The attempt at a solution

    Here is what I have so far:

    Given the hint, I am thinking that I want to use the fact that a set is infinite if there is a bijection between it and a strict subset of it. However, there's a possibility that the set [tex]C[/tex] is a finite subset, which is why I believe the professor gave us that hint about constructing a map from [tex]C \cup B[/tex] to make sure it is infinite.

    Here, then is where I show that [tex]C \cup B[/tex] is infinitely countable.

    Define [tex]C \subset (A - B)[/tex] as a countable subset of [tex]A - B[/tex]
    Construct [tex]f : C \cup B \rightarrow B[/tex]
    Since [tex]C[/tex] and [tex]B[/tex] are disjoint countable sets, their union is also countable.

    [tex]B[/tex] is a countably infinite set
    [tex]\Rightarrow C \cup B[/tex] is countably infinite
    [tex]\Rightarrow #B = #(C \cup B) = \aleph_{0}[/tex]
    [tex]\exists bijection f : C \cup B \rightarrow B[/tex]

    However, this is where I get stuck. I can easily conclude that since [tex]A[/tex] is not countable, there is no bijection between and [tex]C \cup B[/tex], but that seems quite trivial at the moment, especially if I'm going to be using the theorem from above.

    The part that gets me the most is how [tex]C \cup B[/tex] could possibly be a strict subset of [tex]A - B[/tex], since [tex] B \notin (A - B)[/tex]. I will probably need to use this fact that [tex]A - B[/tex] is infinite, but I am completely lost as to how to go about this.

    To prove that [tex]A - B[/tex] is also uncountable: will I need to show that there cannot exist a bijection between it and [tex]C \cup B[/tex] ? The funny thing about this is that if [tex]A - B[/tex] is infinite, it must have a bijection between it and [tex]C[/tex], which is where the whole issue with [tex]C \cup B[/tex] turns almost circular.

    Can someone please help me clear things up and perhaps find a better strategy for a proof?

    As per part (2), I would assume that the easiest way to do this is to show that there exists a bijection between [tex]A - B[/tex] and [tex]A[/tex]. Would the results of the previous part be required to solve this?

    Thank you for your time--any help would be greatly appreciated!
  2. jcsd
  3. Feb 1, 2009 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    For part (1), just notice [tex] (A-B) \cup B[/tex] = A, and the union of two countable sets is countable.

    For part (2), you (should) know there is a countable subset C of A-B. This is useful to know. When making your bijection from A to A-B, try separating it into the case of whether an element of A is in (A-B)-C or not.
  4. Feb 1, 2009 #3
    Ah, but we're trying to prove that [tex](A - B)[/tex] is uncountable.
  5. Feb 1, 2009 #4


    User Avatar
    Science Advisor
    Homework Helper

    Office_Shredder is gently suggesting a proof by contradiction. If (A-B) were countable then so would (A-B) union B. But that's A. And it's not countable. Hence A-B is uncountable.
  6. Feb 2, 2009 #5
    Ah, I see. The contradiction comes from the fact that the given A is uncountable.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook