Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
4  
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
2  
You should probably find that out before attempting this question then. –  Chris Eagle Nov 9 '12 at 17:32

4 Answers 4

up vote 2 down vote accepted

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

share|improve this answer
    
Can you give me a hint for a injective function from $\mathbb{R}^2$ to $\mathbb{R}$? –  joachim Nov 10 '12 at 16:44
1  
@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|$

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.