28
$\begingroup$

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?

  • 0
    same question: http://www.physicsforums.com/showthread.php?t=2490762011-03-15

2 Answers 2

30

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|$.

  • 1
    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?2011-03-15
  • 1
    @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.2011-03-15
  • 0
    @Arturo: Thank you very much.2011-03-15
  • 0
    In Schecter's Handbook of Analysis and its Foundations, comparability of all cardinals is equivalent to AC (pg 145)2011-03-15
  • 1
    @Ross: The statement that for every two sets $X$ and $Y$ there is either an injection from $X$ to $Y$ or an injection from $Y$ to $X$ (sometimes called "comparability of cardinals") is equivalent to AC. However, one defines ordinals without having to have AC, and then one defines cardinals to be ordinals that cannot be bijected with any smaller ordinals. These definitions make sense even in the absence of AC, and all of cardinal arithmetic goes through without needing AC. It is the statement that every set is bijectable with a cardinal (in this sense) that is equivalent to AC. (cont...)2011-03-15
  • 0
    @ya09d: No; that's not it.2011-03-15
  • 1
    @Ross: (cont...) It's the difference between "cardinality" and "cardinals." Cardinals are specific sets, well-defined in ZF. Saying that every set has a cardinality (i.e., is bijectable with a cardinal) is equivalent to AC, as is saying that for every $X$ and $Y$, either $X\preceq Y$ or $Y\preceq X$ ($\preceq=$there is an injection) which is probably what Shecter's saying. (Bernstein's Theorem, aka comparability of cardinals). See also Bergman's handout "The Axiom of Choice, Zorn's Lemma, and all that" at http://math.berkeley.edu/~gbergman/grad.hndts/2011-03-15
  • 0
    Thanks. A good set of notes.2011-03-15
  • 0
    That any two sets are comparable (i.e., there is an injection from one of them into the other) is equivalent to choice. In fact, given any $n\ge 2$, choice is equivalent to the statement that given any $n$ sets, at least 2 are comparable.2011-03-15
  • 0
    Arturo, there is at least some choice in this answer. The claim that $|X|\ge\aleph_0$ requires at least countable choice. Furthermore, the cardinality of $X$ is not specified, and Tarski tells us that if for every cardinality $|X|\times |X| = |X|$ then the axiom of choice holds, and you assume even more. So in fact the answer requires full blown choice.2011-03-15
  • 0
    @Asaf: I always forget the latter; but if we replace $X$ and $|X|$ with an aleph, then surely we don't need countable choice for $\aleph_{\alpha}\geq \aleph_0$. And I'm pretty sure that choice is not required for $\aleph_{\alpha}\times\aleph_{\alpha}=\aleph_{\alpha}$; is it? That's what I meant when I said "replace it with a cardinal".2011-03-15
  • 0
    @Asaf: Wait: Tarski's Theorem is that |X\times X# bijectable with $X$ for all infinite $X$ is equivalent to AC, right? (I always think of $|X|$ as meaning "the aleph/cardinal to which $X$ is bijectable", but that is probably not standard)2011-03-15
  • 0
    $\aleph_\alpha\times\aleph_\alpha=\aleph_\alpha$ doesn't require choice, but the fact that $\Sigma_{n\in\omega}\aleph_\alpha$ is well defined requires choice. That is, to show that $|\bigcup_{n<\omega}S_n|=\aleph_0\times|X|$ requires at least some choice: We know that for every $n$ there exist a bijection between $S_n$ and $X$. But to create the couples we need to *choose* a bijection for every $n$. Thus we need countable choice.2011-03-15
  • 0
    @Arturo, when you assume that every cardinality is some $\aleph$ number you literally assume choice. Without AC sets which are not well-orderable are not bijectible with any $\aleph$ number (in the sense of initial ordinals at least) and then the point of the $\aleph$'s is somewhat amiss.2011-03-15
  • 0
    @Asaf: I think we have a clash of nomenclature. I am aware that assuming that every set is bijectable with a cardinal (an aleph) is equivalent to choice. I understand the difference between "equipollence" and "cardinality" is that the latter assumes bijectability with an aleph, while the former does not. With AC, they amount to the same thing, but without AC there are sets that have well-defined "cardinality" (bijectability with alephs) and perhaps others that do not (for which we can talk about equipollence, etc, but not "cardinality").2011-03-15
  • 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.2011-03-15
  • 1
    @Asaf: So, I'm using nonstandard terminology. I shall endeavor to stop, then, and stick to "alephs" when I mean cardinals. Thanks!2011-03-15
6

This is an old post, but because Arturo's otherwise good answer is a bit cavalier on choice usage and the comments don't make the exact level of choice needed entirely clear, I thought I'd explain my own approach to the question in a ZF framework.

We can establish the following with no well-orderability assumptions:

Lemma: If $X$ is a nonempty set and $X\times X\approx X$ (meaning there is a bijection from $X\times X$ to $X$), then $\bigcup_{n\in\omega}X^n\approx\omega\times X$.

Proof: Fix a bijection $f:X\times X\to X$ and $x_0\in X$. Then we can define

$$g_0:x\in X^0\mapsto x_0$$ $$g_{n+1}:x\in X^{n+1}\mapsto f(g_n(x\restriction n), x_n)$$

Then by induction we have that $g_n$ is an injection from $X^n$ to $X$, and then $$h:x\in\bigcup_{n\in\omega}X^n\mapsto \langle \operatorname{dom}x,g_{\operatorname{dom}x}(x)\rangle$$

is an injection from $\bigcup_{n\in\omega}X^n$ to $\omega\times X$. (We use that $X^n$ for different $n$ are disjoint because $x\in X^n$ implies $x:n\to X$ so that $\operatorname{dom}x=n$.) For the reverse inequality, define

$$j:n\in\omega,x\in X\mapsto(z\in n+1\mapsto x).$$

Then if $j(n,x)=j(m,y)$ we have $(z\in n+1\mapsto x)=(z\in m+1\mapsto y)$ so the domains of the functions are equal, i.e. $n+1=m+1\Rightarrow n=m$, and also $x=j(n,x)(0)=j(m,y)(0)=y$.


Adding an assumption of well-ordering allows us to simplify the statement to what we are after:

If $X$ is an infinite well-orderable set, then the set $[X]^{<\omega}$ of finite subsets of $X$ is equipollent to $X$.

Proof: Since singletons are in $[X]^{<\omega}$ and naturally bijective with $X$, $X\preceq[X]^{<\omega}$. For the converse, we have $X\times X\approx X$ because $X$ is infinite well-orderable, so by the lemma $$\bigcup_{n\in\omega}X^n\approx\omega\times X\preceq X\times X\approx X;$$ thus $\bigcup_{n\in\omega}X^n$ is also well-orderable, so we can reverse the surjection $f:\bigcup_{n\in\omega}X^n\to[X]^{<\omega}$ which maps each function to its range to get an injection. Thus, $X\preceq [X]^{<\omega}\preceq\bigcup_{n\in\omega}X^n\preceq X$.