The cardinality of the set of all finite subsets of an infinite set

  1. How do I prove that the set of all finite subsets of an infinite set has the same cardinality as that infinite set?
     
  2. jcsd
  3. morphism

    morphism 2,020
    Science Advisor
    Homework Helper

    What have you tried?
     
  4. You can't because its not true. Take the reals which have aleph-one cardinality, the subset {1} has cardinality 1 which is not aleph-one. Same goes for infinite subsets, naturals are a subset of reals but naturals have cardinality aleph-null.
     
  5. morphism

    morphism 2,020
    Science Advisor
    Homework Helper

    Careful. The OP wants to prove that the set of all finite subsets of X has the same cardinality as X. This is certainly true whenever X is infinite.

    Also, the cardinality of the reals is 2^aleph-0, and if the continuum hypothesis isn't assumed, this is generally not aleph-1.
     
  6. I know that it is not true that every finite subset of an infinite set has the same cardinality as the infinite set. No finite subset of an infinite set has the same cardinality as the infinite set. The question was about the set of ALL finite subsets of an infinite set.
     
  7. O.k.

    If K is an infinite set, then form U K^n for natural numbers n. We know that if card K = lKl, then K^2 has card lKl. We know that for any finite natural number, K^n has cardinality lKl. The union of all K^n is equivalent to lKl + lKl with the operation repeated countably many times. The sum must have cardinality lKl. It is clear that for every subset of elements {b1,...., bm}, there is injection that maps that set to an ordered set <b1,....,bm>. There are "more" ordered sets actually. It has to be true that the set of finite subsets is < or = the set of ordered n-tuples, which has cardinality lKl.
     
  8. Sorry I misread the post. You could try it this way (assuming CH): you know that if S is the set of all finite sets then [tex] a_i \in X \qquad \{\{a_1\},\{a_2\},...\} \subset S[/tex] thus the cardinality of S is greater of equal to the cardinality of X. Now S is a subset of P(X) thus the cardinality of S is less than or equal to [tex] 2^{|X|} [/tex]. I think you may be able to construct a proof to make that last inequality strict (perhaps by Cantors diagonal argument), then you have that |S|=|X|.

    Hope this is more helpful :blushing:
     
  9. Hurkyl

    Hurkyl 16,089
    Staff Emeritus
    Science Advisor
    Gold Member

    Your proof looks right, including this assertion here as well. But from the way you phrased it, I'm not entirely sure your justification for this assertion is correct. Would you elaborate?
     
  10. For any infinite K, K^n has the same cardinality as K provided n is finite. Then U{K^n : n in N} has a card equal to lK^1 + K^2 + K^3 ... + K^n....l for all natural numbers n. Each K^n has card lKl so this calculation is equivalent to lKl . aleph_0 which equals lKl because lKl is infinite. I can conclude that card U{K^n : n in N} = lKl.

    The cardinality of the set of all ordered finite n-tuples is lKl and there are at least as many finite n-tuples as there are finite subsets. There should be a way to injectively map a finite subset {b1,....,bn} to some finite ordering of the elements b1,...,bn using choice if there are many such ordered tuples. This would show that the set of finite subsets has a cardinality less than or equal to the set of finite tuples.

    We know that it is easy to define an injective function from K to the set of all finite subsets of K. Simply map each element of K to its singleton. Call the set of all finite subsets S and the set of all finite n-tuples T. lSl ≤ lTl, lKl ≤ lSl, lTl = lKl, so lSl ≤ lKl. Because lKl ≤ lSl and lSl ≤ lKl, lKl = lSl.

    Hopefully that makes sense.
     
  11. Thanks, but I want to do this without CH. I should not need more than plain old ZFC.
     
  12. any comments?
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?