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

In summary: 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|.
  • #1
Edward357
6
0
How do I prove that the set of all finite subsets of an infinite set has the same cardinality as that infinite set?
 
Physics news on Phys.org
  • #2
What have you tried?
 
  • #3
Edward357 said:
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.
 
  • #4
Focus said:
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.
 
  • #5
Focus said:
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.
 
  • #6
morphism said:
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.
 
  • #7
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:
 
  • #8
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?
 
  • #9
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.
 
  • #10
Focus said:
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:

Thanks, but I want to do this without CH. I should not need more than plain old ZFC.
 
  • #11
any comments?
 

What is the cardinality of the set of all finite subsets of an infinite set?

The cardinality of this set is equal to the cardinality of the infinite set itself. This means that the number of elements in the set of all finite subsets is the same as the number of elements in the infinite set.

How can the cardinality of a set of finite subsets be equal to an infinite set?

This is due to the concept of "counting" infinite sets. While we may think that an infinite set has an infinite number of elements, certain infinite sets can be counted in a similar way to finite sets. In this case, the infinite set and the set of finite subsets have the same number of elements, making their cardinalities equal.

Does this mean that the set of all finite subsets of an infinite set is also infinite?

No, the set of all finite subsets is not infinite. It has a finite number of elements, even though it may seem like it would have an infinite number due to being a subset of an infinite set.

Can the cardinality of the set of all finite subsets ever be greater than the cardinality of the infinite set?

No, the cardinality of the set of all finite subsets can never be greater than the cardinality of the infinite set. This is because the set of finite subsets is a subset of the infinite set and therefore cannot have more elements than the infinite set.

What implications does the cardinality of the set of finite subsets have on the study of infinite sets?

The concept of "counting" infinite sets and the equal cardinality of the set of finite subsets and infinite sets have significant implications in the study of infinite sets. It allows for the comparison and classification of different types of infinite sets, as well as the understanding of the size and structure of infinite sets.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
22
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
21
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
665
  • Set Theory, Logic, Probability, Statistics
Replies
19
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
16
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
20
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
17
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
966
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
Back
Top