0
$\begingroup$

What is the cardinality of the set of all higher order functions mapping real functions to real functions?

To be specific, this set includes all higher order functions with the type signature: $(\mathbb{R} \rightarrow \mathbb{R}) \rightarrow (\mathbb{R} \rightarrow \mathbb{R}) $, an example of which being the differential operator (i.e. taking the derivative of some function). Since the cardinality of the set of all functions $\mathbb{R} \rightarrow \mathbb{R} $ is $\aleph_2$, I'd assume it's $\aleph_3$, but I'm not sure.

$\endgroup$
  • 2
    $\begingroup$ The cardinality of the set of all functions $\mathbb{R}\mapsto\mathbb{R}$ is $2^\mathfrak{c}$, with of course $\mathfrak{c}=2^{\aleph_0}$; this is only $\aleph_2$ if you assume the continuum hypothesis. You're essentially correct in that the set of all functions from real functions to real functions is of size $2^{2^\mathfrak{c}}$, though; this is sometimes referred to as $\beth_3$ (the definition is that $\beth_0=\aleph_0$ and $\beth_{n+1} = 2^{\beth_n}$) $\endgroup$ – Steven Stadnicki Jun 23 '14 at 4:05
  • 2
    $\begingroup$ No, not even the continuum hypothesis makes this $\aleph_2$. $\endgroup$ – Andrés E. Caicedo Jun 23 '14 at 6:07
  • $\begingroup$ @AndresCaicedo Very true, but GCH is a bit TOO big a hammer for it and I didn't want to get too far afield. I probably should have said "(a slight generalization of) CH". $\endgroup$ – Steven Stadnicki Jun 23 '14 at 17:22
  • 1
    $\begingroup$ @StevenStadnicki Better not to say anything unless you give the precise statement, many times the symbols are used without knowing their meaning, and so people say that something has size $\aleph_1$, not because they are assuming $\mathsf{CH}$ but simply because they do not know the appropriate terminology. $\endgroup$ – Andrés E. Caicedo Jun 23 '14 at 17:48
2
$\begingroup$

First, let me correct you. The cardinality of functions from $\Bbb R$ to itself is not $\aleph_2$ in general. This is a common mistake, but the aleph numbers are not defined by taking power sets, but rather by climbing up the ordinals until we increased the cardinality. So we can only prove that $\aleph_1\leq|\Bbb R|$, but we can't prove equality.

To ease up on notation, we have the $\beth$ numbers which are defined using power sets, so $\beth_0=\aleph_0=|\Bbb N|$, and then we define $\beth_{n+1}=2^{\beth_n}$ (I'll spare you the full definition). So now we have that $|\Bbb R|=\beth_1$, and $|\Bbb{R^R}|=\beth_2$.

But again, we can only prove that $\aleph_n\leq\beth_n$, and we cannot prove equality. The reason is that it is consistent that the inequality is strict. But let us not dwell on that, since it doesn't matter for the purpose of this question. What matters is that you can't claim the cardinality is $\aleph$ this or $\aleph$ that, but you can definitely say what it is in terms of $\beth$ numbers.


What we can prove is this:

If $X$ is infinite, then the set of all functions from $X$ to itself, denoted by $X^X$, has the same cardinality as $\mathcal P(X)$, namely $2^{|X|}$. The proof is simple if you are familiar with cardinal arithmetic (in particular exponentiation laws), but uses the axiom of choice.

$$X<2^X\leq X^X\implies X^X\leq 2^{X^2}\leq X^{X^2}=X^X$$

The axiom of choice was used to have that $X^2$ and $X$ have the same cardinality. However in the case of $\Bbb R$ and the sets we are interested in, we can prove that this property is true without appealing to the axiom of choice. Therefore in the case of our interest, we can prove without the axiom of choice that:

$$\Bbb{\left|\left(R^R\right)^{R^R}\right|}=|\cal P(P(P(\Bbb N)))|=\beth_3.$$

$\endgroup$

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.