Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $X$ be an infinite set of cardinality $|X|$, and let $S$ be the set of all finite subests of $X$. How can we show that Card($S$)$=|X|$? Can anyone help, please?

share|improve this question
    
same question: physicsforums.com/showthread.php?t=249076 –  PEV Mar 15 '11 at 3:18
add comment

1 Answer

up vote 14 down vote accepted

The cardinality is at least $|X|$, since $S$ contains all singletons.

Let $S_n$ be the subset of $S$ consisting of all subsets of cardinality exactly $n$. Then $S$ is the disjoint union of the $S_n$.

Now, for any positive integer $n$, the number of subsets of $X$ of cardinality $n$ is at most $|X|^n = |X|$ (equality since $|X|$ is infinite); because an $n$-tuple of elements of $X$ determines a subset of $X$ of cardinality at most $n$; and every subset with $n$ elements determines only finitely many distinct $n$-tuples of elements of $X$ (namely, $n!$). So $|S_n|\leq n!|X|^n = |X|$ for all $n$.

Therefore: \begin{align*} |X| &\leq |S| = \left|\bigcup_{n=0}^{\infty} S_n\right| = \sum_{n=0}^{\infty}|S_n|\\ &= \sum_{n=1}^{\infty}|S_n| \leq \sum_{n=1}^{\infty}|X|\\ &= \aleph_0|X| = |X|, \end{align*} with the last equality since $|X|\geq\aleph_0$.

Thus, $|X|\leq |S|\leq |X|$, so $|S|=|X|$.

share|improve this answer
    
Do I have it right that this requires some choice, as in the absence of AC, the reals could be a countable union of countable sets? –  Ross Millikan Mar 15 '11 at 4:02
    
@Ross: I don't think so. In the absence of AC, you do not know that a countable union of countable sets is countable (the fact that $\mathbb{R}$ may be a countable union of countable sets show shows such unions need not be countable without AC). Here, we are assuming $X$ has a cardinal, and cardinal arithmetic does not usually require AC. Though I worked with $X$, you could simply work with the corresponding cardinals, which are already well-ordered, so that should allow you to avoid AC. But if we don't assume $X$ has a cardinality, I expect $S$ does not either. –  Arturo Magidin Mar 15 '11 at 4:05
    
@Arturo: Thank you very much. –  yaa09d Mar 15 '11 at 4:22
    
In Schecter's Handbook of Analysis and its Foundations, comparability of all cardinals is equivalent to AC (pg 145) –  Ross Millikan Mar 15 '11 at 4:28
2  
@Arturo, as far as I've seen the term cardinality means the equivalence class under the relation "there exists a bijection", while assuming AC it reduces to $\aleph$ numbers, and without AC it becomes a different beast altogether. –  Asaf Karagila Mar 15 '11 at 13:55
show 12 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.