Which set is greater in cardinality, the set of all functions from $\mathbb R$(the real numbers) into $\mathbb N$(the natural numbers) or the set of all functions from $\mathbb N$ into $\mathbb R$? I have a feeling that the set of all functions from $\mathbb R$ into $\mathbb N$ is equinumerous to the power set of $\mathbb R$ and that the set of all functions from $\mathbb N$ into $\mathbb R$ is equinumerous to the set $\mathbb R$. Can someone please provide me an answer with proof?
|
|
In fact, the number of functions from $\Bbb N$ to $\Bbb R$ is the same as the number of reals. Remember the number of functions $A \to B$ is $|B|^{|A|}$ because you have $|B|$ choices of where to send each element of $A$, so make that choice $|A|$ times. Since $|\Bbb R|=2^{\aleph_0}$ the number of functions from $\Bbb N$ to $\Bbb R$ is $(2^{\aleph_o})^{\aleph_0}=2^{\aleph_o\cdot \aleph_0}=2^{\aleph_o}$. The number of functions from $\Bbb R$ to $\Bbb N$ is $\aleph_0^{(2^{\aleph_0})}$ which is equivalent to the power set of $\Bbb R$ |
|||||
|
|
This answer is elementary: it doesn't require any cardinal arithmetic beyond Cantor-Schröder-Bernstein. We'll use $\mathcal{P}(\mathbb{N})$ instead of $\mathbb{R}$ when convenient, since it's simpler. Let's take $\mathbb{N} = \{1,2,\dots\}$. The set of functions $\mathbb{N} \to \mathcal{P}(\mathbb{N})$ is equinumerous with $\mathcal{P}(\mathbb{N})$. Indeed, given a subset $A$ of the naturals, we can create a unique function $\mathbb{N} \to \mathcal{P}(\mathbb{N})$ which sends $n \mapsto A$; conversely, given a function $\mathbb{N} \to \mathcal{P}(\mathbb{N})$ we can create a unique subset of the naturals by taking the elements of $f(1)$, $f(2)$, $f(3)$, and so on, and distinguishing them by powers of primes: $$\{2^a, 3^b, 5^c, \dots : a \in f(1), b \in f(2), c \in f(3), \dots \}$$ So by Cantor-Schröder-Bernstein, there is a bijection between $\mathbb{N} \to \mathcal{P}(\mathbb{N})$ and $\mathcal{P}(\mathbb{N})$. However, $\mathbb{R} \to \mathbb{N}$ is at least as big as $\mathcal{P}(\mathbb{R})$. The injection is easy: given a set $A$ of reals, define a function $\mathbb{R} \to \mathbb{N}$ by $r \mapsto 1$ if $r \in A$, and $r \mapsto 2$ otherwise. In fact, $\mathbb{R} \to \mathbb{N}$ is exactly as big as $\mathcal{P}(\mathbb{R})$; you can prove this by using the same "powers of primes" trick as above (using $\mathcal{P}(\mathbb{N})$ instead of $\mathbb{R}$), but it goes one level deeper. Exercise for you. |
||||
|
|
