Partial function

A partial function of the set by the set is a right unambiguous relation , that is, a relation in which each element of the set is assigned at most one element of the set . The concept of partial function is widespread in theoretical computer science , especially in computability theory . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$

The concept of partial function is a generalization of the concept of function . A function from to is understood to be a left-total , right-unambiguous relation, i.e. a relation in which each element of exactly one element of is assigned. Every function from to is in particular a partial function from to , namely a (left-) total partial function, but not vice versa. In this respect, the term partial function can be misleading. To express that a partial function is actually a function in the strict sense, one sometimes says that it is a total function . The difference between partial functions and (total) functions is: For partial functions holds true , for (total) functions holds true . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle f\colon \;X\rightharpoonup Y}$ ${\displaystyle \operatorname {Def} (f)\subseteq X}$ ${\displaystyle f\colon \;X\to Y}$ ${\displaystyle \operatorname {Def} (f)=X}$

The domain of definition of the partial function is the set of all those elements from which an element from is assigned. A partial function is a function if and only if holds. ${\displaystyle \operatorname {Def} (f)}$ ${\displaystyle f}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle f}$ ${\displaystyle {\mbox{Def}}(f)=X}$

A partial function from to can be modeled as a function in two ways: ${\displaystyle f}$ ${\displaystyle X}$ ${\displaystyle Y}$

1. as a function or ${\displaystyle f|_{\operatorname {Def} (f)}\colon \;\operatorname {Def} (f)\to Y,x\mapsto f(x),\quad }$
2. as a function ${\displaystyle {\bar {f}}\colon \;X\to Y\cup \{\bot \},\;x\mapsto {\begin{cases}f(x),&{\text{ falls }}x\in \operatorname {Def} (f),\\\bot ,&{\text{ sonst.}}\end{cases}}}$

The value ("undefined") must not be in . ${\displaystyle \bot }$ ${\displaystyle Y}$

Spellings

For “ is a partial function from to ” one writes: or , alternatively also , or . Not recommended are a. the notations as well as , because the former is defined as a (total) function and the latter is easy to be confused with, which means, however, that no (total) function is from to . However, like the former, this is generally not the case. ${\displaystyle f}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle f\colon \;X\rightharpoonup Y}$ ${\displaystyle f\colon \;X\rightsquigarrow Y}$ ${\displaystyle f\colon \;\subseteq X\to Y}$ ${\displaystyle f\colon \;X\to _{p}Y}$ ${\displaystyle f\colon \;X{\mbox{ ⇢ }}Y}$ ${\displaystyle f\colon \;X\to Y}$ ${\displaystyle f\colon \;X\;{\,\,\shortmid \;\!\!\!\!\!\to }\;Y}$ ${\displaystyle f}$ ${\displaystyle f\colon \;X\nrightarrow Y}$ ${\displaystyle f}$ ${\displaystyle X}$ ${\displaystyle Y}$

The spelling “ is undefined” or even “ ” is problematic because the expression is then not allowed. It is clearer to say " is undefined at the point " or as a formula " ". ${\displaystyle f(x)}$ ${\displaystyle f(x)={\text{undefiniert}}}$ ${\displaystyle f(x)}$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle x\notin {\mbox{Def}}(f)}$

Examples

• The partial function is undefined at this point because division by is not permitted in the real numbers. One can educate ${\displaystyle f\colon \;\mathbb {R} \rightharpoonup \mathbb {R} ,x\mapsto {\frac {1}{x}},}$ ${\displaystyle x=0}$ ${\displaystyle 0}$

${\displaystyle f|_{\mathbb {R} \setminus \{0\}}\colon \;\mathbb {R} \setminus \{0\}\to \mathbb {R} ,x\mapsto {\tfrac {1}{x}},}$

or

${\displaystyle {\bar {f}}\colon \;\mathbb {R} \to \mathbb {R} \cup \{\bot \},\;x\mapsto {\begin{cases}{\tfrac {1}{x}},&{\text{ falls }}x\neq 0,\\\bot ,&{\text{ sonst.}}\end{cases}}}$

• partially recursive functions
• an unbounded linear operator

Applications

If an algorithm accepts inputs from the set and delivers outputs from the set , then it computes a partial function of after . The domain of this function is the set of all elements for which the algorithm returns a value. In order to deliver a value, it has to come to an end ( terminate ) with its calculation . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$

Individual evidence

1. ↑ Technical University of Braunschweig Partial and total functions (PDF; 112 kB).
2. ↑ ^{a b} Thomas Holder: partial map classifier , on: nLab, July 3, 2015