An exercise is the following:
Compare the cardinality of the following sets:
- The class of all real numbers $\mathbb{R} =: A$
- The class of all polynomials $\mathbb{R}[X] =: B$
- The class of all real functions $f:\mathbb{R} \to \{0,1\} =: C$
- …
The hint is to use the Cantor-Schröder-Bernstein-Theorem. Is it also possible to show that two sets $A,B$ satisfy $|A| \leq |B|$ and $|A| \neq |B|$? Obviously there is a injective function $f: A \to B$. But if you could show that there is no injective function $f: B \to A$ would that imply $|A| \neq |B|$ ?
Best Answer
Yes, it would. If $A$ and $B$ had the same cardinality, there would by definition by a bijection (and therefore an injection) $f:B\to A$. It follows immediately that if there is no such injection, then $|A|\ne|B|$.
Thus, if you have an injection from $A$ to $B$, then either there is an injection from $B$ to $A$, in which case $|A|=|B|$ by the Cantor-Schröder-Bernstein theorem, or there is no injection from $B$ to $A$, in which case $|A|<|B|$.
In your specific problem there are fairly obvious injections from $A$ to $B$ and to $C$. It is possible to find an injection from $B$ to $A$ directly, but that is not how I would approach the problem. I would (1) note that for each $n$ there is a bijection between the polynomials of degree $n$ and $\Bbb R^{n+1}$; (2) find a bijection between $\Bbb R$ and $\Bbb R^2$; (3) show by induction that $|\Bbb R^n|=|\Bbb R|$ for $n\in\Bbb Z^+$; and (4) use this to show that $|B|=|\Bbb N\times\Bbb R|=|\Bbb R|$. Depending on how much I had already proved about cardinalities, I could skip some of these steps.
I would not that there is an easy bijection between $C$ and $\wp(\Bbb R)$ and apply Cantor’s theorem to deal with $C$.