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?
Why $(\mathbb{N} \rightarrow \mathbb{N}) \subseteq (\mathbb{N} \leadsto \mathbb{N})$?
1
$\begingroup$
elementary-set-theory
-
1The cardinal is the same – 2012-08-20
2 Answers
5
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.
5
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
-
1if $f(x)$ is not defined, then $g(x)=0$ else $g(x)=f(x)+1$ – 2012-09-02