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
-
4Aren't we just saying that total functions are, in particular, partial functions? – 2012-08-20
-
2Your 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}$? – 2012-08-20
-
0To Benoît: Yes. – 2012-08-20
-
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
-
0what about its inverse? – 2012-09-01
-
1if $f(x)$ is not defined, then $g(x)=0$ else $g(x)=f(x)+1$ – 2012-09-02