53
$\begingroup$

How does one compute the cardinality of the set of functions $f:\mathbb{R} \to \mathbb{R}$ (not necessarily continuous)?

$\endgroup$
0

4 Answers 4

61
$\begingroup$

All you need is a few basics of cardinal arithmetic: if $\kappa$ and $\lambda$ are cardinals, none of them zero, and at least one of them is infinite, then $\kappa+\lambda = \kappa\lambda = \max\{\kappa,\lambda\}$. And cardinal exponentiation satisfies some of the same laws as regular exponentiation; in particular, $(\kappa^{\lambda})^{\nu} = \kappa^{\lambda\nu}$.

The cardinality of the set of all real functions is then $$|\mathbb{R}|^{|\mathbb{R}|} =\mathfrak{c}^{\mathfrak{c}} = (2^{\aleph_0})^{2^{\aleph_0}} = 2^{\aleph_02^{\aleph_0}} = 2^{2^{\aleph_0}} = 2^{\mathfrak{c}}.$$ In other words, it is equal to the cardinality of the power set of $\mathbb{R}$.

With a few extra facts, you can get more. In general, if $\kappa$ is an infinite cardinal, and $2\leq\lambda\leq\kappa$, then $\lambda^{\kappa}=2^{\kappa}$. This follows because: $$2^{\kappa} \leq \lambda^{\kappa} \leq (2^{\lambda})^{\kappa} = 2^{\lambda\kappa} = 2^{\kappa},$$ so you get equality throughout. The extra information you need for this is to know that if $\kappa$, $\lambda$, and $\nu$ are nonzero cardinals, $\kappa\leq\lambda$, then $\kappa^{\nu}\leq \lambda^{\nu}$.

In particular, for any infinite cardinal $\kappa$ you have $\kappa^{\kappa} = 2^{\kappa}$.

$\endgroup$
2
  • $\begingroup$ Sorry if this is a trivial question, but why is the cardinality $|\mathbb R|^{|\mathbb R|}$? $\endgroup$
    – VIVID
    Apr 23, 2021 at 3:53
  • 1
    $\begingroup$ @VIVID: By definition, $X^Y$ is the set of functions from $Y$ to $X$; and cardinal exponentiation is defined precisely so that $|X|^|Y| = |X^Y|$. $\endgroup$ Apr 23, 2021 at 10:25
43
$\begingroup$

I guess that you know that $|\mathbb{N}| = |\mathbb{N}\times\mathbb{N}|$ and thus $|\mathbb{R}| = |2^{\mathbb{N}}| = |2^{\mathbb{N}\times\mathbb{N}}| = |2^\mathbb{N}\times 2^\mathbb{N}| = |\mathbb{R}\times\mathbb{R}|$

This means that $|P(\mathbb{R})| = |P(\mathbb{R}\times\mathbb{R})|$. Since $f\colon\mathbb{R}\to\mathbb{R}$ is an element of $P(\mathbb{R}\times\mathbb{R})$ you have that $\mathbb{R}^\mathbb{R}$ (all the functions from $\mathbb{R}$ to itself) is of cardinality less or equal to the one of $P(\mathbb{R}\times\mathbb{R})$ which in turn means that $|\mathbb{R}^\mathbb{R}|\le |P(\mathbb{R})|$.

Now, since $|P(\mathbb{R})| = |2^\mathbb{R}|$ which is the set of all functions from $\mathbb{R}$ to $\{0,1\}$, and clearly every function from $\mathbb{R}$ into $\{0,1\}$ is in particular a function from $\mathbb{R}$ into itself, we have: $$|P(\mathbb{R})| = |2^\mathbb{R}| \le |\mathbb{R}^\mathbb{R}| \le |P(\mathbb{R}\times\mathbb{R})| = |P(\mathbb{R})|$$

So all in all we have that $|\mathbb{R}^\mathbb{R}| = |P(\mathbb{R})| = |2^\mathbb{R}|$.

$\endgroup$
7
  • 2
    $\begingroup$ Did you mean $|P(\mathbb{R})|$ at the end of your second paragraph? $\endgroup$ Jan 17, 2011 at 23:51
  • 2
    $\begingroup$ @AsafKaraglia: Could you please detail how and why $|\mathbb{R}| = |\mathbb{R}\times\mathbb{R}|$ and $ \mathbb{R} \neq \mathbb{R}\times\mathbb{R} $ $\Longrightarrow |P(\mathbb{R})| = |P(\mathbb{R}\times\mathbb{R})|$? I made an incidental edits which I hope will help and referenced math.stackexchange.com/questions/29366/…. $\endgroup$
    – user53259
    Nov 7, 2013 at 1:10
  • 1
    $\begingroup$ @LePressentiment: Don't add color to my posts. Thank you. $\endgroup$
    – Asaf Karagila
    Nov 7, 2013 at 5:36
  • 2
    $\begingroup$ @AsafKaragila: No problem at all. I'll post my edition separately below. In your previous version (rollback) above, you write that $\mathbb{R}^\mathbb{R}$ = all the functions from $\mathbb{R}$ to itself. Should this be the set of all such functions? Also, will you please to let me know of my previous comment, preceding your comment? $\endgroup$
    – user53259
    Nov 7, 2013 at 9:48
  • 1
    $\begingroup$ @LePressentiment: The alternative notation comes from the fact that sometimes $\kappa$ and $\lambda$ are cardinals (and so they are also sets), and then using the notation $\kappa^\lambda$ is reserved for cardinal exponentiation, rather than the set of functions. So $|{}^\lambda\kappa|=\kappa^\lambda$. $\endgroup$
    – Asaf Karagila
    Nov 7, 2013 at 10:18
7
$\begingroup$

This answer is based on, but differs slightly from, user Asaf Karaglia's above.


First, observe that by definition, $\{\text{all real functions of real variable}\}:= \{f: \; f: \mathbb{R}\to\mathbb{R}\} := \mathbb{R}^\mathbb{R}$.

The question is about $|\{\text{all real functions of real variable}\}|$, so examine an arbitrary real function of real variable: $f\,\colon\,\mathbb{R}\to\mathbb{R}.$
By inspection, $f\,\colon\,\mathbb{R}\to\mathbb{R} := \{(r, f(r)) : r \in \mathbb{R}\} \quad \subseteq \quad P(\mathbb{R} \times \mathbb{R})$.
Thus, $\color{green}{|\mathbb{R}^{\mathbb{R}}| \le |P(\mathbb{R}\times\mathbb{R})|}$.

Before continuing, let's try to simplify $|P(\mathbb{R}\times\mathbb{R})|$. Observe that $|\mathbb{R}| = |\mathbb{R}^k| \, \forall \, k \in \mathbb{N}$. Its proof by mathematical induction requires the induction hypothesis of $|\mathbb{R}| = |\mathbb{R}^2|$, one proof of which is : $|\mathbb{N}| = |\mathbb{N}\times\mathbb{N}| \implies |\mathbb{R}| = |2^{\mathbb{N}}| = |2^{\mathbb{N}\times\mathbb{N}}| = |2^\mathbb{N}\times 2^\mathbb{N}| = |\mathbb{R}\times\mathbb{R}|$.

Verily, $\mathbb{R} \neq \mathbb{R}^2$. Howbeit, for infinite sets $A,B$: $|A| = |B| \Longrightarrow \require{cancel} \cancel{\Longleftarrow} |P(A)| = |P(B)|$.
(The converse is discussed here.)

Thus, $|P(\mathbb{R})| = |P(\mathbb{R}\times\mathbb{R})| \implies \color{green}{|\mathbb{R}^\mathbb{R}| \le |P(\mathbb{R}\times\mathbb{R})|} = |P(\mathbb{R})|$. Now scrutinise $|P(\mathbb{R})|$:

● $\color{#A9057D}{|P(\mathbb{R})| = |2^{\mathbb{R}}|}$, where $2^{\mathbb{R}} := \{f : \; f: \mathbb{R} \to \{0,1\}\}$,
● Every $f: \mathbb{R} \to \{0,1\}$ is a particular case of a function from $\mathbb{R}$ to $\mathbb{R}$, thus $\color{#EC5021}{2^{\mathbb{R}} \subsetneq \mathbb{R}^\mathbb{R}}$.

Altogether, $\color{#A9057D}{|P(\mathbb{R})| =} \color{#EC5021}{|2^\mathbb{R}| \le} \color{green}{|\mathbb{R}^\mathbb{R}| \le |P(\mathbb{R}\times\mathbb{R})|} = |P(\mathbb{R})|$

$\implies |P(\mathbb{R})| \qquad \qquad \quad \leq |\mathbb{R}^\mathbb{R}| \leq |P(\mathbb{R})| \implies \color{#A9057D}{\underbrace{|P(\mathbb{R})|}_{= |2^\mathbb{R}|}} = |\mathbb{R}^\mathbb{R}| $.

$\endgroup$
2
  • 3
    $\begingroup$ Downvoters, pursuant to my edit, please let me know of further sugggestions which would be more instructive than a mere downvote. $\endgroup$
    – user53259
    Nov 8, 2013 at 7:35
  • 6
    $\begingroup$ Use less colors, so people with disabilities could read this without getting a headache. $\endgroup$
    – Asaf Karagila
    Nov 8, 2013 at 8:31
5
$\begingroup$

This is irrelevent here, still it is 'relevent'. The cardinality of set of all continuous function from $\mathbb{R}$ to $\mathbb{R}$ $(C(\mathbb{R},\mathbb{R}))$ is $2 ^ \mathbb{N_0} = \mathfrak{c}$ because any such function is determined by its value on rationals. hence #$(C(\mathbb{R},\mathbb{R}))$ = # $\mathbb{R}^\mathbb{Q}$ which has cardinality $2^\mathbb{N_0}$.

$\endgroup$
1
  • 4
    $\begingroup$ Yes, it's relevant, because it sets a lower bound on the cardinality of the question, i.e., $|\mathbb{R}^{\mathbb{R}}| \geq |\mathbb{R}| = \mathfrak{c}$. Moreover, it is a nice, easy-to-understand, result :) $\endgroup$ Apr 29, 2017 at 21:48

You must log in to answer this question.

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