- #1

- 1,270

- 0

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!

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter kingwinner
- Start date

- #1

- 1,270

- 0

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

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

How do they compare to |R|?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|?

- #3

Landau

Science Advisor

- 905

- 0

Yes. I believe Hurkyl is trying to get you to a proof, so I won't go into this. But: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|?

No.Is it provable in general that

If |A|=|C| and |B|=|D|,

then |A\B| = |C\D| ?

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.

- #4

- 1,270

- 0

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!

- #5

Landau

Science Advisor

- 905

- 0

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.

- #6

- 1,270

- 0

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!

Thanks!

Last edited:

- #7

- 1,270

- 0

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

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!

- #8

Landau

Science Advisor

- 905

- 0

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.So if I can show that |R\N|=|R\C|, then I'm done. But how can we rigorously prove this?

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?But I can define an injection from (0,1) into R\N, so I can show that |R\N| ≥ |(0,1)|.

- #9

- 1,270

- 0

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

- #10

Landau

Science Advisor

- 905

- 0

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.

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:

Share: