Abstract Nonsense

Crushing one theorem at a time

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.



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.



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!


      Comment by Alex Youcis | November 22, 2011 | Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: