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

Cardinality: |R\N| = |R\C| where C is countable

  1. Mar 15, 2010 #1
    If C is countable, then |N|=|C|, so there exists a bijection bewteen N and C, but does this imply that |R\N| = |R\C|? It is intutively believable, but I don't see how it rigorously follows. What is the bijection between R\N and R\C?

    Is it provable in general that
    If |A|=|C| and |B|=|D|,
    then |A\B| = |C\D| ?

    If so, how can we formally prove this? i.e. how to define the bijection?

    Thanks!
     
  2. jcsd
  3. Mar 15, 2010 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    How do they compare to |R|?
     
  4. Mar 15, 2010 #3

    Landau

    User Avatar
    Science Advisor

    Yes. I believe Hurkyl is trying to get you to a proof, so I won't go into this. But:
    No.
    Take A=B=C={1,2} and D={3,4}. Then |A|=|C| and |B|=|D|, but |A\B|=0 and |C\D|=|C|=2.
     
  5. Mar 15, 2010 #4
    OK!

    Then how do we prove taht |R\N| = |R\C|?

    Maybe we can say that both are equal to |R|, so |R\N| = |R\C|. But how can we rigorously prove this?

    Thanks!
     
  6. Mar 15, 2010 #5

    Landau

    User Avatar
    Science Advisor

    Let C be a countable subset of [tex]\mathbb{R}[/tex]. We show that [tex]|\mathbb{R}\backslash C|=|\mathbb{R}|[/tex]. This is very easy assuming the continuum hypothesis:

    Of course, [tex]\mathbb{R}\backslash C[/tex] is either countable or uncountable. If it were countable, then [tex](\mathbb{R}\backslash C)\cup C=\mathbb{R}[/tex] would be countable, being the union of countable sets, which we know is impossible. Hence [tex]\mathbb{R}\backslash C[/tex] is uncountable. But, by the continuum hypothesis, an uncountable subset of [tex]\mathbb{R}[/tex] necessarily has the same cardinality of [tex]\mathbb{R}[/tex].

    A proof without using CH is also possible, but is a bit longer. If you're interested I can sketch such a proof.
     
  7. Mar 15, 2010 #6
    Since the continuum hypothesis is not necessarily true, I perfer not to use it in any formal proof. Can you explain the proof without the continuum hypothesis?

    Thanks!
     
    Last edited: Mar 16, 2010
  8. Mar 16, 2010 #7
    This is the original context of the problem:

    Assuming the fact that the set of algebraic numbers is countable, prove that the set of transcendental numbers has the exact same cardinality R, the set of real numbers.

    First Attempt:
    Let A be the set of algebraic numbers and T the set of transcendentals. Then R= A U T, so if T was countable then so would R be (because a countable union of countable sets is countable). Contradiction. Thus T is uncountable.

    But this only proves that T is uncountable, and we need to prove MORE than that, namely, |T|=|R|, i.e. the cardinality of the set of transcendental numbers is EXACTLY equal to the cardinality of the real numbers. How to prove this without using the continuum hypothesis??


    So my need to prove |R\N| = |R\C| arises exactly because I don't want to assume the continuum hypothesis.
    I was trying to use the Schroeder-Bernstein Theorem to show that
    |R| ≥ |R\C| where C is countable
    and |R\C| ≥ |(0,1)| = |R|


    But then I am not sure how to rigorously prove that |R\C| ≥ |(0,1)|

    But I can define an injection from (0,1) into R\N, so I can show that |R\N| ≥ |(0,1)|.

    So if I can show that |R\N|=|R\C|, then I'm done. But how can we rigorously prove this??

    Thanks for helping!
     
  9. Mar 16, 2010 #8

    Landau

    User Avatar
    Science Advisor

    If you can find an injection from [0,1] to R\C, you are done, right? Because then you have shown it for arbitrary countable subsets C of R, so in particular for N.
    But:
    you have already done it for C=N, so I'm guessing that your injection can be slightly modified to work for arbitrary C. What is your injection?
     
  10. Mar 16, 2010 #9
    The injection is f(x)=x.
    It works for R\N, but it doesn't work for R\C...
     
  11. Mar 16, 2010 #10

    Landau

    User Avatar
    Science Advisor

    Haha, I hadn't thought of that (I was thinking about [0,1] instead of (0,1)) :) No, obviously that doesn't work for arbitrary C.

    To be precise, we are going to show that if C is a countable subset of [0,1], then we have |[0,1]|=|[0,1]\C|. The result then follows since |[0,1]|=|R|.

    Bu Schroeder-Bernstein it is enough to find injections g:[0,1]\C -> [0,1] and f:[0,1] -> [0,1]\C. Of course, g(x)=x works. Now we define f.

    C is countable, so we can write [itex]C=\{c_1,c_2,c_3,...\}[/itex], where c_i and c_j are distinct if i and j are. For every [itex]i\in \mathbb{N}[/itex], let [itex]0.c_{i1}c_{i2}c_{i3}... [/itex] be the decimal expansion of [itex]c_i[/itex]. As always, avoid infinite strings of 9's to obtain uniqueness. Now define [itex]d_i:=2[/itex] if [itex]c_{ii}=1[/itex], and [itex]d_i:=1[/itex] otherwise. Let [itex]x\in [0,1][/itex], and [itex]x=0.x_1x_2x_3...[/itex] its decimal expansion. Define [itex]f(x)=0.d_1x_1d_3x_2d_5x_4...[/itex], i.e. the decimal expansion of f(x) has as its odd entries d_1,d_3,d_5,... and as its even entries x_1,x_2,x_3,...

    Check that f is a function [0,1] -> [0,1]\C (f(x) never equals c_i.), and is injective.

    PS. why has this thread been moved to Calculus & Analysis?
    PPS: I can't remember myself why f(x) cannot equal c_i for every i. It's true for odd i, but not necessarily for even i (?). But this can easily be bypassed by just replacing C with C={c_1,c_3,c_5,...}, and keep the rest. This is harmless since [itex]\mathbb{N}[/itex] and the set of odd natural numbers have the same cardinality. I'm sure there is a cleaner solution, but this works.
     
    Last edited: Mar 16, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook