# Why $(\mathbb{N} \rightarrow \mathbb{N}) \subseteq (\mathbb{N} \leadsto \mathbb{N})$?

Written in natural language, the sets of all total functions from naturals to naturals is a subset of the sets of all partial functions of such. $$(\mathbb{N} \rightarrow \mathbb{N}) \subseteq (\mathbb{N} \leadsto \mathbb{N})$$ We see that $\mathbb{N} \leadsto \mathbb{N}$ has more mappings since $\mathsf{domain}(f) \in \mathcal{P}(\mathbb{N})$, and there is no bijection between $\mathbb{N}$ and $\mathcal{P}(\mathbb{N})$. Would someone give a formal proof?

-
Aren't we just saying that total functions are, in particular, partial functions? –  Sean Eberhard Aug 20 '12 at 11:54
Your question is unclear to me. Do you want to know wether the cardinal of $\mathbb{N}\to\mathbb{N}$ is lesser than that of $\mathbb{N} \leadsto \mathbb{N}$? –  Benoît Kloeckner Aug 20 '12 at 11:54
To Benoît: Yes. –  MeadowMuffins Aug 20 '12 at 13:02
The cardinal is the same –  Xoff Aug 20 '12 at 18:03

Sean Eberhard has answered it. By definition, "$A \subseteq B"$ means that every element of $A$ is an element of $B$. Because every total function is a "partial function", the set of total functions is a subset of the set of partial functions.

-

However the two sets are in bijection. Consider the following bijection $\phi$ for total functions to partial functions :

$$\phi(f)(x)=\left\{\begin{array}{l}\mbox{if } f(x)>0 \mbox{ then } f(x)-1\\ \mbox{else undefined} \end{array}\right.$$

This is a trivial bijection between the set of total functions and the set of partial functions

-
if $f(x)$ is not defined, then $g(x)=0$ else $g(x)=f(x)+1$ –  Xoff Sep 2 '12 at 12:14