Looking for a problem where one could use a cardinality argument to find a solution.

Question

I would like to find an exercise of the type: Find some $x$ in $A\setminus B$. Solution: since $A$ is uncountable and $B$ is countable such $x$ exists...

Answer 1

• There is a function $f : \mathbb{N} \to \mathbb{N}$ not computable by a Turing machine. (Or there is a real number whose decimal expansion cannot be so computed.)
• There is a non-Borel subset of $\mathbb{R}$. (Cardinality $\mathfrak{c} = 2^{\aleph_0}$ vs. cardinality $2^{\mathfrak{c}}$.)

Answer 2

Some ideas:

1. Prove that there exists an irrational number.
2. Prove that there exists a sequence of irrational numbers converging to any real number.
3. Prove that there exists a subset of the integers which is neither finite nor co-finite.
4. Prove that there exists a function $f\colon\Bbb{R\to R}$ which is discontinuous everywhere (replace "countable" with "size continuum" and uncountable with "larger than the continuum").
5. There exists a number in the Cantor set which is not the endpoint of an interval disjoint from the Cantor set (the complement of the Cantor set can be written as a countable union of disjoint intervals, so there are only a countable number of endpoints which are elements of the Cantor set).
6. There exists a normal number.
7. There exists a linear functional on $(\Bbb R[x])^\ast$ which is not an evaluation functional (the dimension of $\Bbb R[x]$ is countable, and therefore the dimension of the evaluation functionals is countable; but $(\Bbb R[x])^{**}$ has an uncountable dimension).

Answer 3

The classical result presented by Cantor himself: Prove that there exists a real number that is not algebraic.

Remark: the fact that non-algebraic numbers exist was known before, but Cantor presented the proof of the uncountability of the reals and derived from it a very simple existence proof exactly using what you are asking about, using such a technique for the first time.