Results 1 to 6 of 6

Math Help - Denumerable sets...

  1. #1
    Senior Member Danneedshelp's Avatar
    Joined
    Apr 2009
    Posts
    303

    Denumerable sets...

    Let A, B, and C be disjoint denumerable sets. Show that A∪B∪C is also denumerable.

    Given: A≈N, B≈N, and C≈N. Goal:A∪B∪C≈N

    Suppose A,B, and C are non-empty disjoints sets such that A≈N, B≈N, and C≈N. Then, there exists functions f:A→N, g:B→N, and h:C→N that are one-to-one and onto N.

    This is where my understanding kinda falls apart...Do have to set some knda of restriction? I can't find many examples in my book of this kind of stuff. Actaully, I'm probably just not making the connection.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,648
    Thanks
    1596
    Awards
    1
    Quote Originally Posted by Danneedshelp View Post
    Let A, B, and C be disjoint denumerable sets. Show that A∪B∪C is also denumerable.
    There are three bijections: \alpha :A \Leftrightarrow \mathbb{N}\;,\;\beta :B \Leftrightarrow \mathbb{N}\;\& \;\chi :C \Leftrightarrow \mathbb{N}.
    Define a new function \Phi :A \cup B \cup C \mapsto \mathbb{N}\;,\;\Phi (x) = \left\{ {\begin{array}{lr}<br />
   {2^{\alpha (x)} ,} & {x \in A}  \\<br />
   {3^{\beta (x)} ,} & {x \in B}  \\<br />
   {5^{\chi (x)} ,} & {x \in C}  \\ \end{array} } \right.

    You must show that the function, \Phi, is well-defined and is an injection.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Danneedshelp's Avatar
    Joined
    Apr 2009
    Posts
    303
    Suppose Φ(x)=Φ(y). We see that x and y must have same parity for or else Φ(x)≠Φ(y). So, suppose x,y∈A. Then, plugging into the definition Φ(x)=2^∝(x)=2^∝(y)=Φ(y). ln(2^∝(x))=ln(2^∝(y)) ⇒ ∝ln(2)x=∝ln(2)y ⇒ x=y. Therefore, Φ(x) is injective when x∈A.
    Let y be an element of the codomain. By our definition y=2^∝(x). Solving for x we get x=ln(y)/∝ln(2) when y>0. Now, f(ln(y)/∝ln(2))=2^∝(ln(y)/∝ln(2))=y for y∈N. Thus, Φ(x) is surjective.

    Then I proceed to go down the list?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,648
    Thanks
    1596
    Awards
    1
    Quote Originally Posted by Danneedshelp View Post
    By our definition y=2^∝(x). Solving for x we get x=ln(y)/∝ln(2) when y>0. Now, f(ln(y)/∝ln(2))=2^∝(ln(y)/∝ln(2))=y for y∈N. Thus, Φ(x) is surjective.
    Absolutely not! The function \Phi is of course not surjective.
    But it does not have to be in order to prove the theorem.
    All one has to do to prove a set is denumerable is to show that it is infinite and exhibit an injection from the set to \mathbb{N}.
    Last edited by Plato; May 3rd 2009 at 12:02 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,693
    Thanks
    1466
    Plato's method works, of course, but I had a different idea. Since A is countable, there exists a function N->A that is one-to-one and countable so each member of A can be "labeled" a_n. Similarly, members of B and C can be "labeled" b_n and c_n. Now define a function from N to the union of A, B, and C by f(3n)= a_n, f(3n+1)= b_n, and f(3n+2)= c_n. It is easy to show that function is bijective.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member Danneedshelp's Avatar
    Joined
    Apr 2009
    Posts
    303
    Quote Originally Posted by HallsofIvy View Post
    Plato's method works, of course, but I had a different idea. Since A is countable, there exists a function N->A that is one-to-one and countable so each member of A can be "labeled" a_n. Similarly, members of B and C can be "labeled" b_n and c_n. Now define a function from N to the union of A, B, and C by f(3n)= a_n, f(3n+1)= b_n, and f(3n+2)= c_n. It is easy to show that function is bijective.

    Could you maybe expand on this? I am not sure how I would write out the new function H:N⇒A∪B∪C? Would I just list them like piece wise functions?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 2nd 2010, 11:21 AM
  2. Prove that sets are denumerable
    Posted in the Differential Geometry Forum
    Replies: 9
    Last Post: July 4th 2010, 12:02 PM
  3. finite and infinite sets...denumerable
    Posted in the Differential Geometry Forum
    Replies: 15
    Last Post: November 22nd 2009, 05:38 PM
  4. denumerable sets
    Posted in the Advanced Math Topics Forum
    Replies: 15
    Last Post: December 14th 2008, 10:39 PM
  5. denumerable sets
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: February 20th 2008, 10:08 AM

Search Tags


/mathhelpforum @mathhelpforum