finite and infinite sets...denumerable

**hebby** · November 19th 2009, 03:22 PM

Given Q is denumerable, such that R is not denumerable. Show now that R\Q is not denumerable.

**Focus** · November 19th 2009, 04:44 PM

Find injective map from the union of two countable sets to the naturals.

**Drexel28** · November 19th 2009, 05:14 PM

Problem: Given that $\mathbb{Q}\cong\mathbb{N}$ and $\mathbb{R}$ is not, prove that $\mathbb{R}-\mathbb{Q}$ is not as well.

Proof:

Lemma: If $n\ge2\wedge n\in\mathbb{N}$ and $E_i\cong\mathbb{N}\quad 1\le i\le n$ then $\bigcup_{i=1}^{n}E_i\cong\mathbb{N}$ .

Proof: It suffices to prove this for the case when $A\cap B=\varnothing$ (why?). Since $A,B\cong\mathbb{N}$ there exists $f,f'$ such that $f:A\mapsto\mathbb{N}$ and $f':B\mapsto\mathbb{N}$ bijectively. Define a new mapping $\tilde{f}:A\cup B\mapsto\mathbb{Z}-{0}$ by $\tilde{f}(x)=\begin{cases} f(x) & \mbox{if} \quad x\in A \\ -f'(x) & \mbox{if} \quad x\in B \end{cases}$ . Clearly this mapping is bijective, therefore $A\cup B\cong\mathbb{Z}-{0}$ . But it can easily be shown that $\mathbb{N}\cong\mathbb{Z}\cong\mathbb{Z}-{0}$ . And since $\cong$ is an equivalence relation it follows that $A\cup B\cong\mathbb{N}$ . If $A\cap B\ne\varnothing$ . The lemma follows by induction. $\blacksquare$

So assume that $\mathbb{R}-\mathbb{Q}$ was countable, then by the above lemma $\mathbb{Q}\cup\left(\mathbb{R}-\mathbb{Q}\right)=\mathbb{R}$ is countable. Contradiction.

**hebby** · November 19th 2009, 09:08 PM

Hi, What I wrote before that that a union of countable sets is countable , but in this case we have Q u (R\Q)= R were its is countable U non countable = Non Countable, how do I show this law to be be correct given we know Q is countable and R is not countable?

**Drexel28** · November 19th 2009, 09:12 PM

Originally Posted by hebby

Hi, What I wrote before that that a union of countable sets is countable , but in this case we have Q u (R\Q)= R were its is countable U non countable = Non Countable, how do I show this law to be be correct given we know Q is countable and R is not countable?

What?? I don't even understand what you mean. It sounds like you are restating the question. Was there something unsatisfactory with my proof?

**redsoxfan325** · November 19th 2009, 09:49 PM

Originally Posted by hebby

Hi, What I wrote before that that a union of countable sets is countable , but in this case we have Q u (R\Q)= R were its is countable U non countable = Non Countable, how do I show this law to be be correct given we know Q is countable and R is not countable?

He was using proof by contradiction, and showing that if we assumed $\mathbb{R}\backslash\mathbb{Q}$ was countable, we could reach a false conclusion. So therefore $\mathbb{R}\backslash\mathbb{Q}$ must be uncountable.

**hebby** · November 21st 2009, 02:40 PM

Hi

Thanks for the help, but your proof is rather complicated for me, maybe could you write a more simple proof so I can understand it?

**Plato** · November 21st 2009, 02:55 PM

Originally Posted by hebby

Thanks for the help, but your proof is rather complicated for me, maybe could you write a more simple proof so I can understand it?

Has your background prepared you for this question?
Do you understand that the union of two countable set is countable?
Do you understand that $\mathbb{Q}\cup(\mathbb{R}\setminus\mathbb{Q})=\mat hbb{R}?$

So what if $\mathbb{R}\setminus\mathbb{Q}$ is countable?

**hebby** · November 21st 2009, 03:01 PM

well i have been out of school for some time...well

So what if

is countable then that means there is contradiction because R is not denumerable...thanks for the breakdown

**Focus** · November 21st 2009, 03:03 PM

Originally Posted by hebby

Hi

Thanks for the help, but your proof is rather complicated for me, maybe could you write a more simple proof so I can understand it?

Here is a list of things that you are assumed to know (if you doubt/don't know these then say so):
- $\mathbb{R}=\mathbb{R}\backslash\mathbb{Q} \cup \mathbb{Q}$
- A countable set can be mapped bijectively to the natural numbers {1,2,3...}
- $\mathbb{Z}$ is countable (take the mapping that sends negative integers to odd naturals and positive integers to even naturals)
- The composition of two bijections is a bijection (so a countable set is one who is bijective to an other countable set)

Suppose that R\Q is countable. Then as Q is countable we can bijectively map Q to N using a function (say f). Same is true for R\Q, say g maps R\Q to N bijectively. Notice that R and R\Q are disjoint, hence if we define $h:\mathbb{R}\rightarrow \mathbb{Z}$ by
$<br /> h(x)=\begin{cases} f(x) & \mbox{if} \quad x\in \mathbb{Q} \\ -g(x) & \mbox{if} \quad x\in \mathbb{R}\backslash\mathbb{Q} \end{cases}<br />$
then we see that that h is a bijection. Hence R is countable (by the fact that Z is countable).

**Moo** · November 22nd 2009, 06:56 AM

Originally Posted by Drexel28

Lemma: If $n\ge2\wedge n\in\mathbb{N}$ and $E_i\cong\mathbb{N}\quad 1\le i\le n$ then $\bigcup_{i=1}^{n}E_i\cong\mathbb{N}$ .

I don't like the way it's stated. Imho there are some wrong things.

It suffices for n to be $\geq 1$ . Then I don't understand why you put $1\le i \le n$ , since i is just an index in the union, and we don't need any condition over it (it's given in the notation of the union).

Then more generally, it is sufficient to put a countable union, not necessarily finite.

Note : E is countable means that there exists an injection from E to $\mathbb{N}$

Lemma 1 : $\mathbb{N}^2$ is countable.

Proof : The easiest way is to consider the attached picture.
Then you denote... :
point 1: (0,0)
point 2: (1,0)
point 3: (1,1)
point 4: (0,1)
point 5: (0,2)
point 6: (1,2)
...
This is a bijection from N² to N.

Lemma 2 : A countable union of countable sets is countable.

Proof : Suppose we have a sequence $(E_n)_{n\geq 0}$ of countable sets.
Then $\forall n \in\mathbb{N}, \exists \varphi_n ~:~ E_n \to \mathbb{N}$ , an injective mapping.

Let $E=\bigcup_{n\geq 0} E_n$
And for any $x\in E$ , there exists $n\in\mathbb{N},x\in E_n$ . So define $N(x)=\min \{n ~:~ x\in E_n\}$

Now consider $\phi ~:~ E \to \mathbb{N}^2$ , where $\phi(x)=(N(x),\varphi_{N(x)}(x))$ which is an injection (easy to prove)

And for finishing it, (injection o bijection) is an injection.

**Drexel28** · November 22nd 2009, 01:55 PM

Originally Posted by Moo

I don't like the way it's stated. Imho there are some wrong things.

It suffices for n to be $\geq 1$ . Then I don't understand why you put $1\le i \le n$ , since i is just an index in the union, and we don't need any condition over it (it's given in the notation of the union).

Then more generally, it is sufficient to put a countable union, not necessarily finite.

Note : E is countable means that there exists an injection from E to $\mathbb{N}$ $\color{red}\star$

Lemma 1 : $\mathbb{N}^2$ is countable.

Proof : The easiest way is to consider the attached picture.
Then you denote... :
point 1: (0,0)
point 2: (1,0)
point 3: (1,1)
point 4: (0,1)
point 5: (0,2)
point 6: (1,2)
...
This is a bijection from N² to N.

Lemma 2 : A countable union of countable sets is countable.

Proof : Suppose we have a sequence $(E_n)_{n\geq 0}$ of countable sets.
Then $\forall n \in\mathbb{N}, \exists \varphi_n ~:~ E_n \to \mathbb{N}$ , an injective mapping.

Let $E=\bigcup_{n\geq 0} E_n$
And for any $x\in E$ , there exists $n\in\mathbb{N},x\in E_n$ . So define $N(x)=\min \{n ~:~ x\in E_n\}$

Now consider $\phi ~:~ E \to \mathbb{N}^2$ , where $\phi(x)=(N(x),\varphi_{N(x)}(x))$ which is an injection (easy to prove)

And for finishing it, (injection o bijection) is an injection.

I forgot to change the index to $\scriptstyle k$ . The reason why it is $n\ge 2$ is because its obvious if $n=1$ and wasn't worth the weriting. Lastly, doing the countable case requires your nice little pictures which: A) I don't like pictures, B) I can't draw pictures, C) was uneccessary here. Also, the starred section above is a little misleading. Most books use countable as countably infinite and "at most countable" for what you said.

**redsoxfan325** · November 22nd 2009, 02:09 PM

Originally Posted by Drexel28

A) I don't like pictures

Amen to that.

**Plato** · November 22nd 2009, 02:48 PM

Originally Posted by Drexel28

Most books use countable as countably infinite and "at most countable" for what you said.

That is certainly not been my experience in years of reviewing textbooks.
It is true that many texts make that distinction between finite and denumerable sets.
Then say a countable set is either.

Originally Posted by redsoxfan325

I don't like pictures
Amen to that.

Amen again. I have never liked that zigzag proof.

Here is a way that really teaches students the structure of that problem.
Let $\mathbb{N}=\{0,1,2,\cdots\}$ then define $\Phi :\mathbb{N} \times \mathbb{N} \mapsto \mathbb{Z}^ +$ as $\Phi (m,n) = 2^m (2n + 1)$ .

In proving that $\Phi$ is a bijection a great many concepts are learned.

**Moo** · November 22nd 2009, 03:35 PM

Who cares if you don't like sketches ????
You think I do too ? To be honest, my friend did this sketch, and had to explain it 3 times before I understood.

You're just a bunch of selfish people, who don't think that sometimes people reply to those who ask questions, and that maybe the ones who ask questions may understand better this way !!!!!!!!!!

And that's precisely the problem with you, M. Drexel28, who dare say that he doesn't like sketches, and (presumably) suppose it shouldn't be used in order to prove or to explain something.
But what about your Greek letters, that everybody would be such in an ease to manipulate ? What about that isomorphic sign that, of course, everybody would recognize at first sight and understand ? What about your so-perfect proof that everybody would understand where A and B come from ? And what about that excellent example of you saying that in most books, countable means being in bijection with $\mathbb{N}$ , with your so-long experience of analysis books ? For your information, I precised at the beginning of my message what countable would stand for in the rest of the message.
And why the heck would you say that the sketch is unnecessary here ? Do you think you can just memorize the function Plato gave and present it one year after reading it ?
The aim of my message was to give a way to prove a general thing, that's what "more generally" means.

I forgot to change the index to $\scriptstyle k$

And so, where does k intervene ? I wonder !!

Just things among others.
And, in response to your PM, I won't change my way, if I see something I don't like, or where there are problems (and there were !), I will say it. I won't shut up in order to be pleasant to M. Drexel28.

Thread: finite and infinite sets...denumerable

LinkBack

Thread Tools

Display

finite and infinite sets...denumerable

Similar Math Help Forum Discussions

Finite and infinite sets

Proof: Section- Finite and Infinite Sets

Prove if two sets are denumerable then their union is denumerable

Denumerable sets...

denumerable sets

Search Tags