1. Limited time only! Sign up for a free 30min personal 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!

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