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!

Set of finite subsets of Z+ is denumerable

  1. Jan 22, 2012 #1
    Hi

    I am trying to prove that

    [tex]P=\{X\in\mathcal{P}(\mathbb{Z^+})\;|\;X\mbox{ is finite }\} [/tex]

    is denumerable. Now here is the strategy I am using. Let

    [tex]A_n=\{X\in\mathcal{P}(\mathbb{Z^+})\;|\; |X|=n\;\} [/tex]

    So [itex]A_n[/itex] are basically sets of subsets of [itex]\mathbb{Z^+}[/itex] with cardinality
    n. So we see that

    [tex]P=A_0\cup A_1\cup A_2\cdots[/tex]

    I am trying to get help of the following theorem which is proved in the section of the book
    (Velleman's How to prove it, section 7.2 )

    Theorem: If [itex]\mathcal{F}[/itex] is a family of sets, [itex]\mathcal{F}[/itex] is countable
    , and also every element of [itex]\mathcal{F}[/itex] is countable , then [itex]\bigcup\mathcal{F}[/itex] is countable .

    So in this direction , lets define a family of sets [itex]\mathcal{F}[/itex]

    [tex]\mathcal{F}=\{A_n\;|\;n\in \mathbb{N}\} [/tex]

    [tex]\therefore \bigcup\mathcal{F}= P[/tex]

    So to use the theorem quoted, I need to prove first that for all n in N, [itex]A_n[/itex] is
    countable. How would I go about this ?

    Thanks
     
  2. jcsd
  3. Jan 22, 2012 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Try and think of a relation between [itex]A_n[/itex] and [itex] ( \mathbb{Z^+} )^n[/itex] (the cartesian product of n copies of [itex] \mathbb{Z^+} [/itex]).
     
  4. Jan 23, 2012 #3
    Dick

    I could show that [itex] ( \mathbb{Z^+} )^n[/itex] is denumerable using induction. But
    are you suggesting that I prove [itex]A_n \sim \;( \mathbb{Z^+} )^n[/itex] ? Now
    [itex] ( \mathbb{Z^+} )^n[/itex] has ordered pairs and [itex]A_n[/itex] has sets as elements, which are unordered. So how would we map it for the bijection ?
     
  5. Jan 23, 2012 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Don't worry about a bijection. Figure out an injection of the sets into the tuples. Define ordering as part of the mapping.
     
  6. Jan 23, 2012 #5
    Ok

    So I can map an element of [itex]A_n[/itex] into an element of [itex] ( \mathbb{Z^+} )^n[/itex] such that an element of [itex] ( \mathbb{Z^+} )^n[/itex] is sorted in an increasing order and all the members of n-tuple belong to the element of [itex]A_n[/itex] which is being mapped. That way I can prove the injection from [itex]A_n[/itex] to
    [itex] ( \mathbb{Z^+} )^n[/itex]. So how would I put that formally ?
     
  7. Jan 23, 2012 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I think you just did. Given a set, sort it in increasing order. That gives a unique tuple in [itex] ( \mathbb{Z^+} )^n[/itex]. So given a set you can construct the corresponding ordered tuple. You don't have to spell out how you would sort it or anything. That's enough of a definition of a function for me. If you can explain to a computer programmer how to construct the correspondence then you've defined it.
     
  8. Jan 23, 2012 #7
    Dick, I know that I gave the correct outline. I will try to formulate it using mathematical symbols now.
     
  9. Jan 23, 2012 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You sure did. I don't think every proof has to be Principia Mathematica. But go ahead.
     
  10. Jan 25, 2012 #9
    ok So I have proved an injection from [itex]A_n[/itex] to [itex] ( \mathbb{Z^+} )^n[/itex].
    Also I said in post # 3 , we can prove a bijection from [itex] ( \mathbb{Z^+} )^n[/itex] to
    [itex]\mathbb{Z^+} [/itex]. That means we can prove an injection from [itex]A_n[/itex]
    to [itex]\mathbb{Z^+}[/itex]. So for all n, [itex]A_n[/itex] is denumerable and hence countable. So I have proved that every element of [itex]\mathcal{F}[/itex] is countable.
    I still have to prove that [itex]\mathcal{F}[/itex] itself is countable to use that theorem I stated in post # 1. How would I do that ?
     
    Last edited: Jan 25, 2012
  11. Jan 25, 2012 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    The [itex]n[/itex] in [itex]A_n[/itex] is nonnegative integer since it's a finite cardinality. Doesn't that make it obvious?
     
  12. Jan 25, 2012 #11
    oh i missed that. so define a function

    [tex]h=\{(b,k)\in \mathcal{F}\times \mathbb{Z^+}|k=1+\mbox{ cardinality of any set in }b\;\} [/tex]

    We can prove that [itex]h:\mathcal{F}\to \mathbb{Z^+}[/itex] and that h is a bijection.
    So this proves that [itex]\mathcal{F}[/itex] is denumerable and hence countable. So using the theorem mentioned in post # 1, we see that P itself is countable. To prove that P is denumerable, I will still need to prove that P is infinite. To do that, I need to find a proper subset of P such that P is equipotent/equinumerous with that subset...

    How would I do that ?
     
  13. Jan 25, 2012 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You can prove P is infinite by proving [itex]A_1[/itex] is infinite. And I think you are cluttering up a fairly simple proof with notationally complicated proofs of the obvious. If this were homework I was required to read, I wouldn't like that.
     
  14. Jan 25, 2012 #13
    Dick , I am doing the problem from Daniel Velleman's "How to prove it" . The book is teaching to do proofs. As for the author, he is the student of Mary Ellen Rudin, who in turn was a student of Robert Lee Moore. And I have heard on other forums that these people were heckler for definitions. May be that's a school of thought.
     
  15. Jan 25, 2012 #14

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Oh, alright. I'll stop fussing about what I see as clutter. Maybe some people do like it.
     
  16. Jan 25, 2012 #15

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    oops, scratch that
     
    Last edited: Jan 25, 2012
  17. Jan 25, 2012 #16

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You're overthinking the proof that P is infinite. P contains all the singletons {n}, where n is any positive integer, so obviously it is not finite.
     
  18. Jan 26, 2012 #17
    Yes that makes sense....
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook