Register to reply 
The cardinality of the set of all finite subsets of an infinite set 
Share this thread: 
#1
Aug808, 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?



#2
Aug808, 06:43 PM

Sci Advisor
HW Helper
P: 2,020

What have you tried?



#3
Aug808, 06:52 PM

P: 284




#4
Aug808, 06:59 PM

Sci Advisor
HW Helper
P: 2,020

The cardinality of the set of all finite subsets of an infinite set
Also, the cardinality of the reals is 2^aleph0, and if the continuum hypothesis isn't assumed, this is generally not aleph1. 


#5
Aug808, 07:01 PM

P: 6




#6
Aug808, 07:30 PM

P: 6

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 ntuples, which has cardinality lKl. 


#7
Aug908, 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 


#8
Aug908, 01:11 PM

Emeritus
Sci Advisor
PF Gold
P: 16,099




#9
Aug908, 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 ntuples is lKl and there are at least as many finite ntuples 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 ntuples T. lSl ≤ lTl, lKl ≤ lSl, lTl = lKl, so lSl ≤ lKl. Because lKl ≤ lSl and lSl ≤ lKl, lKl = lSl. Hopefully that makes sense. 


#10
Aug908, 09:33 PM

P: 6




#11
Aug1008, 05:50 PM

P: 6

any comments?



Register to reply 
Related Discussions  
Cardinality of a basis of an infinitedimensional 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 