# 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.)

-
I am not entirely sure that this will be a good question - maybe we will only received a list of examples which are very similar to each other. But I hope I will be surprised and I will learn several interesting things I did not know before from the answers. –  Martin Sleziak Apr 10 '14 at 6:26
This question is at least related to the current one. –  Arthur Fischer Apr 10 '14 at 6:26
I am not sure whether this should be CW or not. Although most of the big-list questions with many answers are CWs, the discussion on meta on this topic did not seem to give clear guidance in either way. I've decided not to flag this for CW-fication, feel free to do so, if you think it should be CW. –  Martin Sleziak Apr 10 '14 at 6:28
@ArthurFischer I am unsure whether this should be closed as a duplicate or not. This question is more general (the other question asks only about countable/uncountable), but clearly the answers given in the other question include higher cardinalities, too. –  Martin Sleziak Apr 10 '14 at 6:36
@MartinSleziak: I'm not convinced they are duplicates either. But it seemed appropriate to point out that previous question. Pointing out the intended difference between the questions (as you have done) will go a long way to diffuse the "duplicateness" of this question. –  Arthur Fischer Apr 10 '14 at 7:05

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

-
To be honest, I'm not certain if this is "in the same spirit" as Cantor's proof, but at least I find it interesting. –  Arthur Fischer Apr 10 '14 at 7:29
Well, the phrase "in the same spirit" is a little vague, but is definitely an interesting proof using cardinality argument. BTW congratulations on your general-topology golden badge. –  Martin Sleziak Apr 17 '14 at 11:41
Thanks, @Martin! (Unfortunately, I think my gold topology badge is due in large part to Brian's extended absence from the site.) –  Arthur Fischer Apr 19 '14 at 12:32