# Cardinality of the set of all (real) discontinuous functions

This is a question from the book Introduction to Set Theory (Hrbacek and Jech), chapter 5, question 2.6.

(Show that) The cardinality of the set of all discontinuous functions is $2^{2^{\aleph_0}}$. [Hint: Using exercise 2.5, show that $|\mathbb{R}^\mathbb{R}-C|=2^{2^{\aleph_0}}$ whenever $|C|\leq 2^{\aleph_0}$.]

Exercise 2.5, as referred to in the hint, provides the following result:

For $n>0$, $n \cdot 2^{2^{\aleph_0}} = \aleph_0 \cdot 2^{2^{\aleph_0}} = 2^{\aleph_0} \cdot 2^{2^{\aleph_0}} = 2^{2^{\aleph_0}} \cdot 2^{2^{\aleph_0}} = (2^{2^{\aleph_0}})^n = (2^{2^{\aleph_0}})^{\aleph_0} = (2^{2^{\aleph_0}})^{2^{\aleph_0}}=2^{2^{\aleph_0}}$.

The only way I could answer this question was by making use of two theorems stated later in the same textbook. First, it is easy to prove that $|\mathbb{R}^\mathbb{R}-C|$ is an infinite set, since if it was finite we would have $$2^{2^{\aleph_0}}=|\mathbb{R}^\mathbb{R}|=|\mathbb{R}^\mathbb{R}-C|+|C| \leq n+2^{\aleph_0}=2^{\aleph_0}< 2^{2^{\aleph_0}},$$which is a contradiction. Now I make use of a theorem requiring the axiom of choice: For every infinite set $S$ there exists a unique aleph $\aleph_\alpha$ such that $|S|=\aleph_\alpha$. So I let $|\mathbb{R}^\mathbb{R}-C|=\aleph_\alpha$ for some ordinal $\alpha$. Now assume $\aleph_\alpha < 2^{2^{\aleph_0}}$. Here I make use of another theorem, which i am not sure I am allowed to do: For every $\alpha$ and $\beta$ such that $\alpha \leq \beta$, we have $\aleph_\alpha+\aleph_\beta=\aleph_\beta$. So I basically then say either $|\mathbb{R}^\mathbb{R}-C|+|C|=\aleph_\alpha$ or $|\mathbb{R}^\mathbb{R}-C|+|C|=2^{\aleph_0}$, depending on whether $\aleph_\alpha \leq 2^{\aleph_0}$ or vice-versa. The assumption I am making is that $2^{\aleph_0}=\aleph_1$, which as I understand it is basically equivalent to the continuum hypothesis, as we are saying that the least uncountable number is $\aleph_1$ (but by the previous theorem requiring the axiom of choice this seems reasonable?). So anyway assuming I can do that, we again have a contradiction since then we are saying $|\mathbb{R}^\mathbb{R}|=2^{\aleph_0}<2^{2^{\aleph_0}}$ or $|\mathbb{R}^\mathbb{R}|=\aleph_\alpha < 2^{2^{\aleph_0}}$.

My main problem with my proof is that I am not making use of the result given in exercise 2.5 as suggested in the hint. Can anyone help with a proof making use of this result (stated in the second block quote above).

• Assuming CH is absolutely not necessary. Nor do you have to go via aleph's. Jan 25 '15 at 18:40
• For the record, it's actually pretty easy to just build a injection from the set of nowhere continuous functions to the set of sets of reals . . . Feb 26 '15 at 8:48

Sorry for bothering you. I just came up with a new solution to this problem without using AC.

As we can see, $$|\mathbb{R}^{\mathbb{R}}|=2^{2^{\aleph_0}}=2^{|\mathbb{R}|}=|\mathcal{P}(\mathbb{R})|$$.

Recall that $$|\mathcal{P}(\mathbb{N})|=2^{\aleph_0}$$, we can see that $$|C|\leq|\mathcal{P}(\mathbb{N})|$$.

Thus, it suffices to show that $$|\mathcal{P}(\mathbb{R})-\mathcal{P}(\mathbb{N})|=2^{2^{\aleph_0}}$$, which is kind of easier to prove.

Since $$|\mathbb{R}-\mathbb{N}|=2^{\aleph_0}$$, we can see that

$$2^{2^{\aleph_0}}=|\mathcal{P}(\mathbb{R}-\mathbb{N})|\leq|\mathcal{P}(\mathbb{R})-\mathcal{P}(\mathbb{N})|\leq|\mathcal{P}(\mathbb{R})|=2^{2^{\aleph_0}}.$$

Thus, by Cantor-Schroeder-Bernstein theorem, the equality follows.

• Thanks for your answer...I'm just not sure about $|\mathcal{P}(\mathbb{R}-\mathbb{N})|\leq|\mathcal{P}(\mathbb{R})-\mathcal{P}(\mathbb{N})|$. Do you perhaps have a reference on this? Jan 2 '20 at 6:15
• @ChristiaanHattingh Since $\mathbb{N}\subsetneq\mathbb{R}$, it follows that every nonempty subset of $\mathbb{R}-\mathbb{N}$ is also a subset of $\mathbb{R}$ but never a subset of $\mathbb{N}$. In other words, we have $\mathcal{P}(\mathbb{R}-\mathbb{N})\subsetneq(\mathcal{P}(\mathbb{R})-\mathcal{P}(\mathbb{N}))\cup\{\emptyset\}$. (The proper inclusion is very clear) Thus, $|\mathcal{P}(\mathbb{R}-\mathbb{N})|\leq|\mathcal{P}(\mathbb{R})-\mathcal{P}(\mathbb{N})|+1=|\mathcal{P}(\mathbb{R})-\mathcal{P}(\mathbb{N})|$. (The equality holds because it is infinite)
– user735816
Jan 2 '20 at 20:14

$$C$$ is the set of contiuous functions, so the set of discontinuous functions has size $$|\mathbb{R}^{\mathbb{R}} - C|$$.

Now the set of $$\mathbb{R}^\mathbb{R}$$ has size $$(2^{\aleph_0})^{2^{\aleph_0}} = 2^{2^{\aleph_0}}$$. So you're left with showing that $$|C| = 2^{\aleph_0}$$. The constant functions show it's at least that size, and the fact that two continuous functions that agree on the rationals agree on $$\mathbb{R}$$, shows that $$f \rightarrow f|_\mathbb{Q}$$ from $$C$$ to $$\mathbb{R}^\mathbb{Q}$$ is injective...

Then if $$2^{2^{\aleph_0}} = |\mathbb{R}^\mathbb{R} - C| + |C| = \max(|C|,|\mathbb{R}^\mathbb{R} - C|)$$ (this uses AC, which might be avoidable), and as $$|C| = 2^{\aleph_0} < 2^{2^{\aleph_0}}$$, the latter by Cantor's theorem, we have that $$|\mathbb{R}^\mathbb{R} - C| = 2^{2^{\aleph_0}}$$.

• Thank you, but this proof is essentially the same as mine, and you do not make use of the exercise 2.5 in the hints as requested Jan 25 '15 at 18:36
• I did use the exercise, in $(2^{\aleph_0})^{2^{\aleph_0}} = 2^{2^{\aleph_0}}$ Jan 25 '15 at 18:38
• Did your book already cover $\kappa + \lambda = \max(\kappa, \lambda)$ for cardinals (which is equivalent to AC, I think)? Are you forbidden from using AC? Jan 25 '15 at 18:40
• I don't think I am forbidden to use it...it is covered in a later chapter, but it seems as if the question hints at a way to avoid it... Jan 25 '15 at 18:41
• hmmm...i see, but the problem is I think it is assumed that we don't have to derive $\mathbb{R}^{\mathbb{R}}=2^{2^{\aleph_0}}$ as the theorem is given before in the section. Jan 25 '15 at 18:43