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

  • Thread starter kingwinner
  • Start date
  • Tags
    Cardinality
In summary, if C is countable, then |N|=|C|, so there exists a bijection bewteen N and C. However, this does not imply that |R\N| = |R\C|, because there may exist a bijection between R\N and R\C, but it is not unique. The bijection between R\N and R\C can be proved by finding an injection from [0,1] to R\C.
  • #1
kingwinner
1,270
0
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!
 
Physics news on Phys.org
  • #2
kingwinner said:
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|?
 
  • #3
kingwinner said:
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.
 
  • #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!
 
  • #5
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.
 
  • #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:
  • #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!
 
  • #8
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:
kingwinner said:
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?
 
  • #9
Landau said:
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
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:

What is the meaning of "cardinality" in mathematics?

In mathematics, cardinality refers to the size or number of elements in a set. It is a concept used to compare the sizes of different sets and determine whether they have the same number of elements.

What is the "R" and "N" in the statement "Cardinality: |R\N| = |R\C| where C is countable"?

In set theory, "R" refers to the set of all real numbers and "N" refers to the set of all natural numbers. In this statement, |R\N| refers to the cardinality of the set of real numbers without the set of natural numbers, and |R\C| refers to the cardinality of the set of real numbers without the set C.

What does it mean for two sets to have the same cardinality?

Two sets have the same cardinality if there exists a one-to-one and onto (bijective) function between them. This means that every element in one set is paired with a unique element in the other set, and vice versa.

What is the significance of the statement "Cardinality: |R\N| = |R\C| where C is countable"?

This statement means that the set of real numbers without the set of natural numbers has the same cardinality as the set of real numbers without any countable set. This concept is important in understanding the infinite nature of real numbers and the concept of uncountability.

Can you give an example to demonstrate the statement "Cardinality: |R\N| = |R\C| where C is countable"?

One example is the set of all real numbers without the set of all even integers. This set has the same cardinality as the set of all real numbers without the set of all integers, which is uncountable. This demonstrates the statement since both sets have the same cardinality despite one being a subset of the other.

Similar threads

Replies
16
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
494
Replies
1
Views
904
Replies
22
Views
1K
  • Precalculus Mathematics Homework Help
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
506
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus
Replies
9
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
700
  • Topology and Analysis
Replies
12
Views
364
Back
Top