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

[kingwinner]

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!

 

[Hurkyl]

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|?

How do they compare to |R|?

 

[Landau]

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|?

Yes. I believe Hurkyl is trying to get you to a proof, so I won't go into this. But:

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

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.

 

[kingwinner]

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!

 

[Landau]

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

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

A proof without using CH is also possible, but is a bit longer. If you're interested I can sketch such a proof.

 

[kingwinner]

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!

 

[kingwinner]

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!

 

[Landau]

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

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:

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

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?

 

[kingwinner]

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?

The injection is f(x)=x.
It works for R\N, but it doesn't work for R\C...

 

[Landau]

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 C=\{c_1,c_2,c_3,...\}, where c_i and c_j are distinct if i and j are. For every i\in \mathbb{N}, let 0.c_{i1}c_{i2}c_{i3}... be the decimal expansion of c_i. As always, avoid infinite strings of 9's to obtain uniqueness. Now define d_i:=2 if c_{ii}=1, and d_i:=1 otherwise. Let x\in [0,1], and x=0.x_1x_2x_3... its decimal expansion. Define f(x)=0.d_1x_1d_3x_2d_5x_4..., 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 \mathbb{N} and the set of odd natural numbers have the same cardinality. I'm sure there is a cleaner solution, but this works.