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

Edward357

How do I prove that the set of all finite subsets of an infinite set has the same cardinality as that infinite set?

morphism

What have you tried?

Focus

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.

morphism

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.

Edward357

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.

Edward357

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.

Focus

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

Hurkyl

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?

Edward357

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.

Edward357

Thanks, but I want to do this without CH. I should not need more than plain old ZFC.

Edward357

any comments?