# finite and infinite sets...denumerable

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Nov 19th 2009, 04:22 PM
hebby
finite and infinite sets...denumerable
Given Q is denumerable, such that R is not denumerable. Show now that R\Q is not denumerable.
• Nov 19th 2009, 05:44 PM
Focus
Find injective map from the union of two countable sets to the naturals.
• Nov 19th 2009, 06:14 PM
Drexel28
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.
• Nov 19th 2009, 10:08 PM
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?
• Nov 19th 2009, 10:12 PM
Drexel28
Quote:

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?
• Nov 19th 2009, 10:49 PM
redsoxfan325
Quote:

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.
• Nov 21st 2009, 03:40 PM
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?
• Nov 21st 2009, 03:55 PM
Plato
Quote:

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?
• Nov 21st 2009, 04:01 PM
hebby
well i have been out of school for some time...well

http://www.mathhelpforum.com/math-he...2a3ca67e-1.gif

So what if http://www.mathhelpforum.com/math-he...98f7829d-1.gif is countable then that means there is contradiction because R is not denumerable...thanks for the breakdown :)
• Nov 21st 2009, 04:03 PM
Focus
Quote:

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
$
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}
$

then we see that that h is a bijection. Hence R is countable (by the fact that Z is countable).
• Nov 22nd 2009, 07:56 AM
Moo
Quote:

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.
• Nov 22nd 2009, 02:55 PM
Drexel28
Quote:

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.
• Nov 22nd 2009, 03:09 PM
redsoxfan325
Quote:

Originally Posted by Drexel28
A) I don't like pictures

Amen to that.
• Nov 22nd 2009, 03:48 PM
Plato
Quote:

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.

Quote:

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.
• Nov 22nd 2009, 04:35 PM
Moo
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.

Quote:

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.
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last