Let $S$ be the the set of all real functions that bring back only two values: 0 and 1 (Binary functions).

If $f\in S$ then $f:\mathbb{R}\rightarrow \left\{0,1\right\}$.

Prove that $|\mathbb{R}| \neq |S| $.

I tried to start with a proof by contradiction that there's no one to to correspondence but I got stuck. I also assume that by the end of the proof we show that $|S|=\aleph_0 \ne C=|\mathbb{R}|$.

Thanks in advance.

  • 1
    $\begingroup$ No, $|S|>|\Bbb R|$. Do you know the theorem that for any set $X$, $|X|<|\wp(X)|$? $\endgroup$ – Brian M. Scott Nov 15 '13 at 13:44
  • $\begingroup$ Um no, I never saw that symbol you used either "\wp" I mean. $\endgroup$ – GinKin Nov 15 '13 at 13:49
  • $\begingroup$ It's a symbol for the power set of $X$, the set consisting of all subsets of $X$. Are you familiar with the theorem @BrianM.Scott referenced? $\endgroup$ – Jonathan Y. Nov 15 '13 at 13:52
  • $\begingroup$ I see and no we haven't covered that theorem I guess. How can you apply the power of a set here ? $\endgroup$ – GinKin Nov 15 '13 at 13:55

If you’ve not seen Cantor’s theorem before, this is a fairly hard problem. Suppose that $\varphi:\Bbb R\to S$ is an injection (one-to-one function). I claim that $\varphi$ cannot be a surjection (onto function). If true, this means that there is no bijection from $\Bbb R$ to $S$ and hence that $|\Bbb R|\ne|S|$.

For each $r\in\Bbb R$ let $f_r=\varphi(r)$; $f_r$ is a function from $\Bbb R$ to $\{0,1\}$. To show that $\varphi$ is not surjective, we’ll find a function $g:\Bbb R\to\{0,1\}$ that is different from $f_r$ for every $r\in\Bbb R$. Or rather, I’ll tell you how to construct it and let you finish the details, including the verification that $g\ne f_r$ for every $r\in\Bbb R$. This will show that $g$ is not in the range of $\varphi$ and hence that $\varphi$ is not a surjection.

The idea is simple but powerful: for each $r\in\Bbb R$ choose $g(r)\in\{0,1\}$ so that $g(r)\ne f_r(r)$. That doesn’t give you much choice, since $\{0,1\}$ has only two elements; in fact, it completely defines the function $g$.

  • $\begingroup$ I'm not sure how write the verification that $g\ne f_r$ you mentioned but other than that I think I understood. Basically we show that there's no bijection between the two sets therefore their cardinality cannot be equal. Thank you. $\endgroup$ – GinKin Nov 15 '13 at 15:04
  • $\begingroup$ @GinKin: Just note that for each $r\in\Bbb R$ we have by definition $g(r)\ne f_r(r)$, and therefore $g\ne f_r$: to functions that disagree at some point of their common domain, in this case the point $r$, cannot be the same function. (You can even say that $g(r)=1-f_r(r)$.) $\endgroup$ – Brian M. Scott Nov 15 '13 at 15:07

HINT: Show that $S$ and $\mathcal P(\Bbb R)$ have the same cardinality, and use Cantor's theorem. (Or use the proof of Cantor's theorem directly on $S$).

  • $\begingroup$ I have no idea how to show the $S$ and $\mathcal P(\Bbb R)$ have the same cardinality, nor how you had the intuition to do it. $\endgroup$ – GinKin Nov 15 '13 at 14:17
  • $\begingroup$ @GinKin, it's worth spending time on that concept even after BrianM.Scott's terrific answer. There's a natural isomorphism that identifies a function $f:S\to\{0,1\}$ with that subset of $S$ which is given by $A_f = \{s\in S\mid f(s)=1\}$. Where either is known, the other is readily given. $\endgroup$ – Jonathan Y. Nov 15 '13 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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