Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Math Help - finite and infinite sets...denumerable

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    81

    Question finite and infinite sets...denumerable

    Given Q is denumerable, such that R is not denumerable. Show now that R\Q is not denumerable.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Focus's Avatar
    Joined
    Aug 2009
    Posts
    228
    Find injective map from the union of two countable sets to the naturals.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Nov 2009
    Posts
    81
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by hebby View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member redsoxfan325's Avatar
    Joined
    Feb 2009
    From
    Swampscott, MA
    Posts
    943
    Quote Originally Posted by hebby View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Nov 2009
    Posts
    81
    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?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by hebby View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Nov 2009
    Posts
    81
    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
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member Focus's Avatar
    Joined
    Aug 2009
    Posts
    228
    Quote Originally Posted by hebby View Post
    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).
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by Drexel28 View Post

    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.
    Attached Thumbnails Attached Thumbnails finite and infinite sets...denumerable-bijection.jpg  
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Moo View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member redsoxfan325's Avatar
    Joined
    Feb 2009
    From
    Swampscott, MA
    Posts
    943
    Quote Originally Posted by Drexel28 View Post
    A) I don't like pictures
    Amen to that.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by Drexel28 View Post
    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 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    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.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Finite and infinite sets
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: August 6th 2011, 03:53 PM
  2. Proof: Section- Finite and Infinite Sets
    Posted in the Differential Geometry Forum
    Replies: 15
    Last Post: March 9th 2011, 09:44 AM
  3. Replies: 1
    Last Post: October 2nd 2010, 11:21 AM
  4. Denumerable sets...
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 5th 2009, 10:26 PM
  5. denumerable sets
    Posted in the Advanced Math Topics Forum
    Replies: 15
    Last Post: December 14th 2008, 10:39 PM

Search Tags


/mathhelpforum @mathhelpforum