Register to reply

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

by Edward357
Tags: cardinality, finite, infinite, subsets
Share this thread:
Edward357
#1
Aug8-08, 06:32 PM
P: 6
How do I prove that the set of all finite subsets of an infinite set has the same cardinality as that infinite set?
Phys.Org News Partner Science news on Phys.org
Sapphire talk enlivens guesswork over iPhone 6
Geneticists offer clues to better rice, tomato crops
UConn makes 3-D copies of antique instrument parts
morphism
#2
Aug8-08, 06:43 PM
Sci Advisor
HW Helper
P: 2,020
What have you tried?
Focus
#3
Aug8-08, 06:52 PM
P: 284
Quote Quote by Edward357 View Post
How do I prove that the set of all finite subsets of an infinite set has the same cardinality as that infinite set?
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
#4
Aug8-08, 06:59 PM
Sci Advisor
HW Helper
P: 2,020
The cardinality of the set of all finite subsets of an infinite set

Quote Quote by Focus View Post
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.
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
#5
Aug8-08, 07:01 PM
P: 6
Quote Quote by Focus View Post
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.
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
#6
Aug8-08, 07:30 PM
P: 6
Quote Quote by morphism View Post
What have you tried?
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
#7
Aug9-08, 12:03 PM
P: 284
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
#8
Aug9-08, 01:11 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,098
The union of all K^n is equivalent to lKl + lKl with the operation repeated countably many times. The sum must have cardinality lKl.
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
#9
Aug9-08, 09:29 PM
P: 6
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
#10
Aug9-08, 09:33 PM
P: 6
Quote Quote by Focus View Post
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
Thanks, but I want to do this without CH. I should not need more than plain old ZFC.
Edward357
#11
Aug10-08, 05:50 PM
P: 6
any comments?


Register to reply

Related Discussions
Cardinality of a basis of an infinite-dimensional vector space Linear & Abstract Algebra 7
Splitting an infinite set into two equal infinite subsets. General Math 34
Cardinality of Infinite Sets Calculus & Beyond Homework 2
Sums of Reciprocals of Infinite Subsets of Primes General Math 16
Think Infinite and not the finite General Discussion 14