1
$\begingroup$

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?

  • 1
    The cardinal is the same2012-08-20

2 Answers 2

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

  • 1
    if $f(x)$ is not defined, then $g(x)=0$ else $g(x)=f(x)+1$2012-09-02