53
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ You have used the assumption that the Cardinality of power set of R is equal to the Cardinality of functions from real to {0,1}. How to we prove that as well? $\endgroup$
    – user39246
    Sep 2, 2012 at 10:59
  • $\begingroup$ @krishnanem: Please ask new questions in a new thread, rather than as an answer to a previous question. Furthermore, this question was asked and answered several times before. $\endgroup$
    – Asaf Karagila
    Sep 2, 2012 at 11:17
  • $\begingroup$ @AsafKaragila: I have moved this non-answer to a comment so that krishnanem can pose it as a new question and can read your comment. $\endgroup$
    – robjohn
    Sep 2, 2012 at 20:39
  • $\begingroup$ @robjohn: I think Michael's comment would have been a more suitable choice over mine. $\endgroup$
    – Asaf Karagila
    Sep 2, 2012 at 21:44
  • $\begingroup$ @AsafKaragila: The point is to have krishnanem post the comment as a new question. Your comment solely addresses that point. Michael's also addresses the misplaced question and might encourage a reply. $\endgroup$
    – robjohn
    Sep 3, 2012 at 3:18

4 Answers 4

58
$\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
  • $\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
42
$\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
  • 2
    $\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

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.