1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Problem on power set of N

  1. Jan 17, 2012 #1
    Hi

    Here is the problem I am doing. Prove that

    [tex]^{\mathbb{Z^+}}\mathcal{P}(\mathbb{Z^+})\sim \mathcal{P}(\mathbb{Z^+})[/tex]

    Where [itex]^{\mathbb{Z^+}}\mathcal{P}(\mathbb{Z^+})[/itex] is the set of functions
    from [itex]\mathbb{Z^+}[/itex] to [itex]\mathcal{P}(\mathbb{Z^+})[/itex].

    To prove this I will need to come up with some bijection from [itex]^{\mathbb{Z^+}}\mathcal{P}(\mathbb{Z^+})[/itex] to [itex]\mathcal{P}(\mathbb{Z^+})[/itex]

    I am having hard time with this bijection. How do you map a subset of [itex]\mathbb{Z^+}[/itex] to some function from [itex]\mathbb{Z^+}[/itex] to
    [itex]\mathcal{P}(\mathbb{Z^+})[/itex]

    I have been able to get some insight into the problem so far. I have proven that
    [itex]\mathcal{P}(\mathbb{Z^+}) [/itex] is uncountable. So it means that any function
    from [itex]\mathbb{Z^+}[/itex] to [itex]\mathcal{P}(\mathbb{Z^+}) [/itex] can not be onto.

    I would appreciate further insight to attack the problem.

    thanks
     
  2. jcsd
  3. Jan 18, 2012 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Maybe you can start by proving that

    [tex]\mathcal{P}(\mathbb{Z}^+)\cong {}^{\mathbb{Z}^+}\{0,1\}[/tex]
     
  4. Jan 18, 2012 #3
    micromass

    I have already proved that for any set A

    [tex]\mathcal{P}(A)\sim \; ^{A}\{\mbox{ yes,no }\}[/tex]

    So putting yes=1 and no=0 and letting [itex]A= \mathbb{Z^+}[/itex] , we get what you
    are saying. I have also proved that for any sets A,B,C

    [tex]^{(A\times B)}C\;\sim \; ^{A}( ^{B}C) [/tex]

    So how do things help me ?
     
  5. Jan 18, 2012 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Now it suffices to show

    [tex]\mathbb{Z}^+\times \mathbb{Z}^+ \cong \mathbb{Z}^+[/tex]
     
  6. Jan 18, 2012 #5
    ok I think I got it

    I have already shown that [itex]\mathbb{Z^+}\times \mathbb{Z^+}\;\sim\; \mathbb{Z^+}[/itex]

    Also I have shown previously that for any sets A,B,C,D if [itex]A\sim B[/itex] and [itex]C\sim D[/itex] then it follows that

    [tex]^{A}C \;\sim \;^{B}D\cdots\;(1)[/tex]

    and

    [tex]\mathcal{P}(A)\;\sim\;\mathcal{P}(B)[/tex]

    So it follows that

    [tex]\mathcal{P}(\mathbb{Z^+})\;\sim\;\mathcal{P}( \mathbb{Z^+}\times \mathbb{Z^+})\cdots\;(2)[/tex]

    Since for any set A

    [tex]\mathcal{P}(A)\;\sim\; ^{A}\{0,1\}[/tex]

    we have

    [tex]\mathcal{P}(\mathbb{Z^+}\times \mathbb{Z^+})\;\sim\; ^{(\mathbb{Z^+}\times \mathbb{Z^+} )} \{0,1\} \cdots\;(3)[/tex]

    But for any sets A,B,C we have

    [tex]^{(A\times B)}C\;\sim\; ^{A}( ^{B}C) [/tex]

    So we have

    [tex]^{(\mathbb{Z^+}\times \mathbb{Z^+} )} \{0,1\}\;\sim\; ^{\mathbb{Z^+}}(^{\mathbb{Z^+}} \{0,1\} )\cdots\;(4)[/tex]

    so using equations 2, 3 and 4 ,due to transitivity of [itex]\sim[/itex] we can say that

    [tex]\mathcal{P}(\mathbb{Z^+})\;\sim\; ^{\mathbb{Z^+}}(^{\mathbb{Z^+}} \{0,1\} )
    \cdots\;(5)[/tex]

    Now

    [tex]\mathbb{Z^+}\;\sim \mathbb{Z^+}[/tex]

    and

    [tex]\mathcal{P}(\mathbb{Z^+})\;\sim\; ^{\mathbb{Z^+}}\{0,1\} [/tex]

    It follows from 1 that

    [tex]^{\mathbb{Z^+}}\mathcal{P}(\mathbb{Z^+})\;\sim\; ^{\mathbb{Z^+}}(^{\mathbb{Z^+}} \{0,1\} )[/tex]

    Now using 5 , we can say that


    [tex]^{\mathbb{Z^+}}\mathcal{P}(\mathbb{Z^+})\;\sim\; \mathcal{P}(\mathbb{Z^+})[/tex]

    thanks micromass, that was a lot of typing :cry:

    I was thinking of coming up with some bijection. I think that's probably lot more difficult
    in this case.
     
  7. Jan 21, 2012 #6
    By the way I was wondering, if any bijection could be found between
    [itex]^{\mathbb{Z^+}}\mathcal{P}(\mathbb{Z^+})[/itex] and [itex]\mathcal{P}(\mathbb{Z^+})[/itex] ?
     
  8. Jan 21, 2012 #7

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Yes, I think so. Notice that every element of [itex]\mathcal{P}(\mathbb{Z}^+)[/itex] is determined by a sequence of 0 and 1 (where 1 means that the corresponding element is in the subset). For example, the subset

    [tex]\{1,4,5,10\}[/tex] is

    [tex]1,0,0,1,1,0,0,0,0,1,0,0,0,0,...[/tex]

    Now, given an element of [itex]{}^{\mathbb{Z}^+}\mathcal{P}(\mathbb{Z}^+)[/itex]. Such an element is a countable list of sequences. So such an element is given by

    [tex]x_{1,1},x_{1,2},x_{1,3},x_{1,4},x_{1,5},...[/tex]
    [tex]x_{2,1},x_{2,2},x_{2,3},x_{2,4},x_{2,5},...[/tex]
    [tex]x_{3,1},x_{3,2},x_{3,3},x_{3,4},x_{3,5},...[/tex]
    [tex]x_{4,1},x_{4,2},x_{4,3},x_{4,4},x_{4,5},...[/tex]
    [tex]x_{5,1},x_{5,2},x_{5,3},x_{5,4},x_{5,5},...[/tex]

    We wish to make an element of [itex]\mathcal{P}(\mathbb{Z}^+)[/itex] of that. So we wish to make one sequence of it. This is possible by following the diagonals. So an associated sequence would be

    [tex]x_{1,1},x_{1,2},x_{2,1},x_{1,3},x_{2,2},x_{3,1},...[/tex]
     
  9. Jan 21, 2012 #8
    Micromass, but how do we make sure that every element of [itex]\mathcal{P}(\mathbb{Z}^+)[/itex] has an element associated in [itex]{}^{\mathbb{Z}^+}\mathcal{P}(\mathbb{Z}^+)[/itex] ?

    For example consider [itex]\{1\} \in \mathcal{P}(\mathbb{Z}^+)[/itex] . How does your
    diagonal argument work here ?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Problem on power set of N
  1. Power Sets (Replies: 4)

  2. The Power Set (Replies: 1)

  3. Power set (Replies: 2)

  4. Power set? (Replies: 4)

Loading...