# Prove that the cardinality of the reals and all binary funcions is not equal

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

• No, $|S|>|\Bbb R|$. Do you know the theorem that for any set $X$, $|X|<|\wp(X)|$? – Brian M. Scott Nov 15 '13 at 13:44
• Um no, I never saw that symbol you used either "\wp" I mean. – GinKin Nov 15 '13 at 13:49
• 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? – Jonathan Y. Nov 15 '13 at 13:52
• I see and no we haven't covered that theorem I guess. How can you apply the power of a set here ? – 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$.

• 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. – GinKin Nov 15 '13 at 15:04
• @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)$.) – 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$).

• 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. – GinKin Nov 15 '13 at 14:17
• @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. – Jonathan Y. Nov 15 '13 at 20:11