1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Problem on power set of N

  1. Jan 17, 2012 #1

    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

    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.

  2. jcsd
  3. Jan 18, 2012 #2
    Maybe you can start by proving that

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

    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
    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]



    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\} )


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


    [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
    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


    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


    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

  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 ?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook