Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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? –  user39246 Sep 2 '12 at 10:59
    
@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. –  Asaf Karagila Sep 2 '12 at 11:17
    
@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. –  robjohn Sep 2 '12 at 20:39
    
@robjohn: I think Michael's comment would have been a more suitable choice over mine. –  Asaf Karagila Sep 2 '12 at 21:44
    
@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. –  robjohn Sep 3 '12 at 3:18
add comment

4 Answers

up vote 16 down vote accepted

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}$.

share|improve this answer
add comment

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}|$.

share|improve this answer
2  
Did you mean $|P(\mathbb{R})|$ at the end of your second paragraph? –  Arturo Magidin Jan 17 '11 at 23:51
1  
@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/…. –  LePressentiment Nov 7 '13 at 1:10
    
@LePressentiment: Don't add color to my posts. Thank you. –  Asaf Karagila Nov 7 '13 at 5:36
2  
@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? –  LePressentiment Nov 7 '13 at 9:48
    
@LePressentiment: I don't know what you mean by that. $|A|=|B|$ implies that $|\mathcal P(A)|=|\mathcal P(B)|$. That's a simple exercise in the definition of cardinalities. And yes $A^B$ is the set of all functions from $B$ into $A$, although it is sometimes denoted by ${}^BA$. –  Asaf Karagila Nov 7 '13 at 10:02
show 2 more comments

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}| $.

share|improve this answer
    
Downvoters, pursuant to my edit, please let me know of further sugggestions which would be more instructive than a mere downvote. –  LePressentiment Nov 8 '13 at 7:35
    
Use less colors, so people with disabilities could read this without getting a headache. –  Asaf Karagila Nov 8 '13 at 8:31
add comment

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} = 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}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.