Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
Aren't we just saying that total functions are, in particular, partial functions? –  Sean Eberhard Aug 20 '12 at 11:54
2  
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
1  
The cardinal is the same –  Xoff Aug 20 '12 at 18:03

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer

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

share|improve this answer
    
what about its inverse? –  MeadowMuffins Sep 1 '12 at 18:53
1  
if $f(x)$ is not defined, then $g(x)=0$ else $g(x)=f(x)+1$ –  Xoff Sep 2 '12 at 12:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.