1
$\begingroup$

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 \begin{equation}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}},\end{equation}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).

$\endgroup$
2
  • $\begingroup$ Assuming CH is absolutely not necessary. Nor do you have to go via aleph's. $\endgroup$ Jan 25, 2015 at 18:40
  • $\begingroup$ 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 . . . $\endgroup$ Feb 26, 2015 at 8:48

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Jan 2, 2020 at 6:15
  • 1
    $\begingroup$ @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) $\endgroup$
    – user735816
    Jan 2, 2020 at 20:14
1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$ Jan 25, 2015 at 18:36
  • $\begingroup$ I did use the exercise, in $(2^{\aleph_0})^{2^{\aleph_0}} = 2^{2^{\aleph_0}}$ $\endgroup$ Jan 25, 2015 at 18:38
  • $\begingroup$ 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? $\endgroup$ Jan 25, 2015 at 18:40
  • $\begingroup$ 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... $\endgroup$ Jan 25, 2015 at 18:41
  • $\begingroup$ 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. $\endgroup$ Jan 25, 2015 at 18:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .