# Abstract Nonsense

## On The Cardinality of Function Spaces (Pt. I Real Functions)

Point of post: This post will be one of a few that I will post in my free time about the cardinality of certain function spaces. Thus, for example in this post we will show that

$\text{card }\mathbb{R}^{\mathbb{R}}=2^{2^{\aleph_0}}$

without using cardinal arithmetic, just basic injection, bijection stuff. From here we will proceed with a few more specific examples, ending with a general result that bounds the cardinality of $C\left[X,X\right]$ (space of continuous functions) for a Hausdorff space $X$.

Motivation

Often in mathematics one can ask questions which, at first seem unanswerable. For example, ask a freshman analysis student what the cardinality of $C[a,b]$ and it looks practically impossible. That said, often interesting questions such as these have answers, just not one’s apparent at first glance. In this post we will start out easy and find the cardinality of $\Omega^\Omega$ for a given infinite set $\Omega$, a corollary of which will state that:

$\mathbb{R}^{\mathbb{R}}=\left\{f\mid f:\mathbb{R}\to\mathbb{R}\right\}$

Remark: This is meant just to be informative, and fun. That said, I do not consider deeply set-theoretic topics, in particular I shall speak freely of sets without mentioning their universe and I will not explicitly mention the axiom of choice, etc. when invoked.

Theorem: Let $\Omega$ be a set with $\text{card }\Omega=\kappa\geqslant\aleph_0$. Then, $\text{card }\Omega^{\Omega}=2^{\kappa}$.

Proof: Note that since $\text{card }\mathscr{P}\left(\Omega\right)=2^{\kappa}$ it suffices to prove that $\Omega^{\Omega}\simeq\mathscr{P}\left(\Omega\right)$. To do this, we first note that we may evidently define

$F:\mathcal{P}\left(\Omega\right)\to{\Omega}^{\Omega}:S\mapsto \mathbf{1}_S$

where, as usual, $\mathbf{1}_S$ is the indicator function given by

$\mathbf{1}_S:\mathbb{R}\to\mathbb{R}:x\mapsto\begin{cases}0 & \mbox{if}\quad x\notin S\\ 1 & \mbox{if}\quad x\in S\end{cases}$

This is evidently injective since if $S\ne S'$ then we may assume without loss of generality that $S-S'\ne\varnothing$ and so choosing $x\in S-S'$ we see that $\mathbf{1}_{S}(x)=1\ne0=\mathbf{1}_{S'}(x)$ so that $F(S)=\mathbf{1}_S\ne\mathbf{1}_{S'}=F(S')$. Conversely, we recall the basic fact that $X\simeq Y\implies\mathscr{P}\left(X\right)\simeq\mathscr{P}\left(Y\right)$. In particular, since $\Omega\simeq\Omega^2$ we know that $\mathscr{P}\left(\Omega\right)\simeq\mathscr{P}\left(\Omega^2\right)$. With this said, we consider the function

$G:\Omega^{\Omega}\to\mathscr{P}\left(\Omega^2\right):f\mapsto \Gamma_f$

where $\Gamma_f=\left\{(x,f(x)):x\in\Omega\right\}$, the graph of $f$. This is also evidently injective since if $f\ne g$ then $g(x)\ne f(x)$ for some $x\in \Omega$ and so $(x,g(x))\in\Gamma_g$ but $(x,g(x))\notin\Gamma_f$. Thus, it follows that if $H$ is the guaranteed bijection $\mathscr{P}\left(\Omega^2\right)\to\mathscr{P}\left(\Omega\right)$ that $H\circ F:\Omega^{\Omega}\to\mathscr{P}\left(\Omega\right)$ is an injection.

It follows from the Schroeder-Bernstein theorem $\Omega^\Omega=\mathscr{P}\left(\Omega\right)$ as desired. $\blacksquare$

Remark: Note that this implies that $\text{card }\mathbb{R}^{\mathbb{R}}=2^{2^{\aleph_0}}=\beth_2$ where $\beth_2$ is the third Beth number.

References:

1. Jech, Thomas J. Set Theory. Berlin: Springer, 2003. Print.

November 10, 2010 - Posted by | Analysis, Set Theory

1. basically you are saying it is \aleph_2 = | {\mathbf{R} }^{\mathbf{R}}|
Which is fine, however, can you show that this F is dense in recursive functions?

Comment by Noga | November 21, 2011 | Reply

• Noga,

I’m not even sure what that means haha. Please elaborate!

Best,
Alex

Comment by Alex Youcis | November 22, 2011 | Reply