What are interesting examples of existential proofs based on cardinality arguments? Probably the most famous example of a proof, where consideration of cardinalities is used to show existence of some object, it the Cantor's proof that there exist transcendental numbers.
What are some other interesting examples of proofs in the similar spirit.
Although my motivation for asking this question is to have something you can show to students, to show them what nice things they already can prove with the results they've learned about cardinals, feel free to add answers on any level.

EDIT: As pointed out by Arthur Fischer in his comment, there already is a rather similar question: Looking for a problem where one could use a cardinality argument to find a solution.
A difference is that the question asks about examples of the type $A\setminus B$, where $B$ is countable and $A$ is uncountable. (But as you can see some answers, including the answer that is accepted, are about larger cardinalities, too.)
 A: Slightly more advanced (and perhaps only tangentially an existential proof), are applications of Jones's Lemma to demonstrate that a topological space is not normal.

Jones's Lemma: Let $X$ is a normal space. If $C \subseteq X$ is a closed discrete subset, and $D \subseteq X$ a dense subset, then $2^{|C|} \leq 2^{|D|}$.

(So for spaces in which there are closed discrete and dense subsets disobeying this rule, you get an existential proof of a pair of disjoint closed subsets which cannot be separated by disjoint open neighbourhoods.)
An elementary application of this is to show that the square of the Sorgenfrey line is not normal.  (The anti-diagonal $\nabla = \{ \langle x , -x \rangle : x \in \mathbb{R} \}$ is a closed discrete subset of size $2^{\aleph_0}$ and $\mathbb{Q} \times \mathbb{Q}$ is a countable dense subset.)  Of course, in this instance it is not too difficult (modulo and application of the Baire Category Theorem) to show that $E = \{ \langle x , -x \rangle : x \in \mathbb{Q} \}$ and $F = \{ \langle x , -x \rangle : x \in \mathbb{R} \setminus \mathbb{Q} \}$ are disjoint closed subsets which cannot be separated by disjoint open neighbourhoods.
More interesting perhaps is reasoning about the (a?) rational sequence topology on $\mathbb{R}$.  In this space $\mathbb{R} \setminus \mathbb{Q}$ is closed discrete, and $\mathbb{Q} $ is dense, and so by Jones's Lemma it is not normal. However trying to give a direct construction of disjoint closed subsets which cannot be separated by disjoint open sets is far from obvious (if even possible without fixing nice rational sequences to begin with).
