# Comparing the cardinality of sets

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|$ ?

-
Do you know what $|A|\neq|B|$ means? –  Chris Eagle Nov 9 '12 at 17:29
Probably not ... –  joachim Nov 9 '12 at 17:31
You should probably find that out before attempting this question then. –  Chris Eagle Nov 9 '12 at 17:32

## 4 Answers

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

-
Can you give me a hint for a injective function from $\mathbb{R}^2$ to $\mathbb{R}$? –  joachim Nov 10 '12 at 16:44
@joachim: It’s sufficient to find one from $(0,1)^2$ to $(0,1)$. Try $$\langle 0.a_1a_2a_3\dots,0.b_1,b_2b_3\dots\rangle\mapsto\langle0.a_1b_1a_2b_2a_3b_3\dots‌​\rangle\;.$$ If you get completely stuck, take a look at this answer, which even shows how to get a bijection. –  Brian M. Scott Nov 10 '12 at 16:53

Sure. $|B|\leq |A|$ means that there exists an injective function $f:B\to A$. If you can prove that there is no injective function $f:B\to A$ then $|B|\not\leq |A|$, in particular $|B|\neq|A|$

-

Of course if you could show that there is no injection from $B$ to $A$, then it it would also mean that there is no bijection from $B$ to $A$, so $|A|$ wouldn't be equal to $|B|$.

Still, it is not the case in your problem. Here is a hint about sets $A$ and $B$: prove that $|\mathbb{R}^n| = |\mathbb{R}|$. Then think how to use this knowledge about $\mathbb{R}^n$ to analyze $\mathbb{R}[x]$.

As for $C$, I would suggest looking at Cantor's diagonal argument.

-

If you can show that there is no injective function $X\to Y$ and you already know there is an injection $Y\to X$ then you can conclude that $|Y|\leq|X|$ and $|Y|\neq|X|$. Or in short, $|Y|<|X|$.

You could in fact prove that for $A$ and $C$, Cantor's theorem comes to mind.

As for $A$ and $B$, as you say there is an obvious injection $A\to B$, but there is indeed an injection from $B$ to $A$.

Note that $|A|=2^{\aleph_0}$; and $|B|=|\bigcup_{n=1}^\infty\mathbb R^n|\leq(2^{\aleph_0})^{\aleph_0}$, using basic cardinal arithmetics one can deduce the wanted equality.

-