2
$\begingroup$

If $A$ is an infinite set then $\mathcal{F}(A),$ the set of finite subsets of $A$ has the same cardinality as $A$. Is the following proof of the above fact correct?

Note that $|A_k|\leq |A^k|$ for any $k\geq 0,$ where $A_k$ is the set of subsets of $A$ of cardinality $k$ since the map $f : A_k\to A^k, f(\{a_1,\cdots, a_k\}) = (a_1,\cdots, a_k)$ is injective (indeed for two different subsets, at least one element differs, so that element will be mapped to a different tuple by $f$). Then $\mathcal{F}(A) = \cup_{k\geq 0} A_k$, which is a disjoint union as $A_i \cap A_j = \emptyset$ for $i\neq j$ (the cardinality of a finite set is unique). So $|\mathcal{F}(A)| = \sum_{k\geq 0} |A_k| \leq \sum_{k\geq 0}|A^k| = \sum_{k\geq 1}|A^k| = \sum_{k\geq 1} |A| = \aleph_0 |A|$. Also, $g : A\to A_1, g(a) = \{a\}$ is clearly a bijection, so $|A| = |A_1| \leq |\mathcal{F}(A)|$ as $A_1\subseteq \mathcal{F}(A)$ and if $B\subseteq A$ then there is clearly an injective (identity) function from $B$ to $A.$ So $|\mathcal{F}(A)| = |A|$ by transitivity (for infinite sets this also applies).

$\endgroup$
1
$\begingroup$

Small issue: the function $f : A_k \to A^k$ you wrote down is not well-defined! For example, should $f(\{2,3\}) = f(\{3,2\})$ be $(2,3)$ or $(3,2)$? You gave no way to decide. You could try to fix this in a few ways:

  1. Put a total order on $A$ (if you assume the axiom of choice, this is always possible), and then define $f$ so that it lists the elements in ascending order.
  2. Put a total order on every element of $A_k$ (if you assume the axiom of choice, this is always possible), and then define $f$ so that it lists the elements in ascending order.
  3. Redesign the argument: instead build a surjection $A^k \to A_k$.

To me, approach #3 feels most natural -- there is an "obvious map" $(a_1, \dots, a_k) \mapsto \{a_1, \dots, a_k\}$ that feels like it should be a surjection. The only issue is that $\lvert \{a_1, \dots, a_k\} \rvert$ need not equal $k$! So we have the wrong codomain: instead, this is a surjection $A^k \to A_{\leq k}$. This shows $\lvert A_{\leq k} \rvert \leq \lvert A^k \rvert$, and we also have $\lvert A_k \rvert \leq \lvert A_{\leq k} \rvert$, so transitively $\lvert A_k \rvert \leq \lvert A^k \rvert$.

Another small issue: you definitely showed $\lvert \mathcal{F}(A) \rvert \leq \aleph_0 \lvert A \rvert$, and that $\lvert A \rvert \leq \lvert \mathcal{F}(A) \rvert$. For your proof to be complete, you should say somewhere that $\aleph_0 \lvert A \rvert = \lvert A \rvert$.

Edit: as a side note, I should also mention that it's necessary to assume the axiom of choice here: choice is equivalent to the claim that $a^2 = a$ for all infinite cardinals $a$, and if we had $\lvert A \rvert^2 > \lvert A \rvert$ here the claim would be false.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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