Results 1 to 4 of 4
Like Tree2Thanks
  • 1 Post By jakncoke
  • 1 Post By Drexel28

Math Help - Proving equal cardinality of sets using Cantor-Bernstein theorem

  1. #1
    Junior Member
    Joined
    Nov 2012
    From
    Poland
    Posts
    40

    Proving equal cardinality of sets using Cantor-Bernstein theorem

    Hello,

    I have to prove, that the sets Z \times N^{+}, which is a set containing Cartesian product of elements from the set of integers and from the set of positive natural numbers, has the same cardinality as  Q , a set of rational numbers using Cantor-Bernstein theorem, which states that two sets have the same cardinality, if we can create two injective functions, one from the first set to the other, and the second from the second set to the first.

    So in my opinion these are the two functions:

     f1: Z \times N^{+} \rightarrow Q

    For  <a,b> \in Z \times N^{+} the function gives a  q \in Q such that:

    1)if  a>0 then  q=\frac{(b+1)^{a}}{b}}

    2)if  a<0 then  q=\frac{-(b+1)^{-a}}{b}}

    Because if  b=1 we will get integers, but no other b in natural numbers divides b+1, so we will get fractions, and because every time  a is different, so the prime factors of the whole thing will be different, so we will get a different rational number every time.

    3)if  a=0 then  q=\frac{(1)}{b}}

    Because  b \in N^{+} so b+1>=2 every time in my formula, so when  a=0 we can put 1 in the numerator.

     f2: Q \rightarrow Z \times N^{+}

    For any  q \in Q we choose  m,n  \in N such that  \frac{m}{n}=|q| and :
    1) if q>=0 we return <m,n>
    2) if q<0 we return <-m,n>.


    Are those two function correct?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member jakncoke's Avatar
    Joined
    May 2010
    Posts
    387
    Thanks
    80

    Re: Proving equal cardinality of sets using Cantor-Bernstein theorem

    Your mapping from  \mathbb{Z} \times \mathbb{N^{+}} \to \mathbb{Q} is good.

    The mapping for  \mathbb{Q} \to \mathbb{Z} \times \mathbb{N^{+}} also looks good.
    Thanks from MachinePL1993
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2012
    From
    Poland
    Posts
    40

    Re: Proving equal cardinality of sets using Cantor-Bernstein theorem

    For the first injection is following map also correct?

     f1: Z \times N^{+} \rightarrow Q

    For  <a,b> \in Z \times N^{+} the function gives a  q \in Q such that:

     q=\frac{2^{a}}{3^{b}}}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Re: Proving equal cardinality of sets using Cantor-Bernstein theorem

    Quote Originally Posted by MachinePL1993 View Post
    For the first injection is following map also correct?

     f1: Z \times N^{+} \rightarrow Q

    For  <a,b> \in Z \times N^{+} the function gives a  q \in Q such that:

     q=\frac{2^{a}}{3^{b}}}
    That is correct. Probably the most natural thing to have done here would be to define \mathbb{Z}\times\mathbb{N}\to\mathbb{Q} by exactly (a,b)\mapsto 2^a 3^b which is an injection by the fundamental theorem of arithmetic. Then, the backwards injection could have been \frac{a}{b}\mapsto (a,b) where a,b are coprime and b\in\mathbb{N}.
    Thanks from MachinePL1993
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving Equal Cardinality
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 12th 2011, 12:41 PM
  2. Proving cardinality of sets
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: April 29th 2011, 10:54 AM
  3. Proving two sets are equal
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 22nd 2010, 10:21 AM
  4. [SOLVED] Cantor-Schroder-Bernstein
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 13th 2009, 09:14 AM
  5. Proving two sets equal
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 25th 2008, 08:26 AM

Search Tags


/mathhelpforum @mathhelpforum