Number of subsets with the same cardinality

Question

Suppose we have a set $S$ with cardinal number $n$, such that $n+n = n$. Consider the set, T, of all subsets with cardinality $n$. How can I show that the cardinality of $T$ is $2^n$? (Without the Axiom of Choice)

Answer 1

Clearly $|T| \leq 2^n$ since $T$ is a subset of $\mathcal{P}(S)$ which has cardinality $2^n$.

As the Cantor-Bernstein Theorem does not require Choice, it suffices to show that the reverse inequality holds.

Since $n + n = n$ the sets $S$ and $S \times \{ 0,1 \}$ have the same cardinality. It follows that the set $X$ of all subsets of $S \times \{0,1\}$ of cardinality $n$ has the same cardinality as the set $T$, so we need only show that $2^n \leq |X|$.

For each subset $A$ of $S$, the set $(A \times \{ 0 \}) \cup (S \times \{ 1 \})$ is a subset of $S \times \{ 0,1 \}$ of cardinality $n$, and so belongs to $X$. The obvious mapping is injective, which then shows that $2^n = | \mathcal{P} (S) | \leq |X|$.