Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Quick Question

  1. Mar 13, 2007 #1
    How can I prove that
    [tex]\left| {\left\{ {A \subset \mathbb{N}:\left| A \right| \in \mathbb{N}} \right\}} \right| = \left| \mathbb{N} \right|[/tex]
    ?
     
  2. jcsd
  3. Mar 13, 2007 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    By counting them. How many subsets of size n are there in N? So how many subsets do you have unioning over all n?

    Or just enumerate them directly - a subset is the same as an indicator function. A finite subset is just an indicator function that is 1 finitely many times, that is a sequence such as

    {0,..,0,1,0,..,0,1,0....,0,1,0,.......}

    The place where you put the 1s corresponds to the elements in the set. eg the set {1,2,4} is the indicator/sequence

    {1,1,0,1,0,0,0,.....}

    It is easy to put these in bijection with N. In fact these are usually put in bijection with N by crackpots in an attempt to disprove the uncountability of the reals since they mistakenly believe that N all subsets of N have finitely many elements.
     
  4. Mar 13, 2007 #3

    JasonRox

    User Avatar
    Homework Helper
    Gold Member

    I prefer to just create an injective map into the rationals.

    Say for example A is the set {1,2,5,6}, then map it to 0.1256. And so on.

    We can see it's one-to-one into the rationals. Since the rationals are countable, then is the collection of all the finite subsets of N.
     
  5. Mar 13, 2007 #4

    JasonRox

    User Avatar
    Homework Helper
    Gold Member

    Nevermind, this is wrong. I'll leave it here just so readers and understand why.

    Anyways, if you can prove that the countable union of a collection of countable sets is countable then all you must do is show that...

    All sets of cardinality n is countable.

    So, that you have all finite sets of cardinality 1, 2, 3, ..., n,... and union them all to get the collection of all finite sets of N. Since it is a countable union of a collection of countable sets then the collection of all finite sets of N is countable.

    Note: matt_grime's method is definitely solid. I just like thinking of different ways to go about it. There's no doubt a lot of ways to do this.
     
  6. Mar 13, 2007 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    That was my method 1. I gave two methods.
     
  7. Mar 13, 2007 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    A method like that will almost always be wrong. There is a way to correct it, though, that is very useful. The problem is that in general the lack of uniqueness of decompositions (here 1256 decomposes as 1|2|5|6, and 12|56 amongst many other options). But we know something where we do have uniqueness - prime decomposition, and there are infinitely many primes. So send {1,2,5,6} to

    p_1*p_2*p_5*p_6

    for p_i the i'th prime (i.e. 2*3*11*13)
     
  8. Mar 13, 2007 #7

    JasonRox

    User Avatar
    Homework Helper
    Gold Member

    Nice. I was thinking of a different approach to make it work, such as primes. You beat me to it. :smile:
     
  9. Mar 13, 2007 #8
    What is confusing you? Is it that the power set of N is uncountable? Note how here we have a further restriction that all the sets we are considering have finite cardinality.
     
  10. Mar 23, 2007 #9
    Indeed, if Axiom of Choice is assumed, the set of all finite subsets of an infinite set [tex]\alpha[/tex] has the same cardinality as [tex]\alpha[/tex].
    This is seen in this way: Call the set of all finite subsets [tex]F(\alpha)[/tex].
    [tex]|F(\alpha)|=\displaystyle \sum_{n\in\mathbb N}|\alpha^n|\\
    = \displaystyle \sum_{n\in\mathbb N}|\alpha| = \aleph_0\cdot|\alpha|=|\alpha|[/tex]
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Quick Question
  1. Quick question (Replies: 3)

  2. Quick pdf question (Replies: 2)

Loading...