A partial function is like a function $f:A\to B$, but where we relax the requirement that $f\left(a\right)$ must be defined for all $a\in A$. That is, it must still be the case that "$a=b$ and $f\left(a\right)$ is defined" implies "$f\left(b\right)$ is defined and $f\left(a\right)=f\left(b\right)$", but now we no longer need $f\left(a\right)$ to be defined everywhere. We can write $f:A\rightharpoonup B$ ^[1]to denote that $f$ is a partial function with domain $A$ and codomain $B$: that is, whenever $f\left(x\right)$ is defined then we have $x\in A$ and $f\left(x\right)\in B$.

This idea is essentially the "flip side" to the distinction between the codomain vs image dichotomy.

Implementation in set theory

Just as a function can be implemented as a set $f$ of ordered pairs $(a,b)$ such that:

• every $x\in A$ appears as the first element of some ordered pair in $f$
• if $(a,b)$ is an ordered pair in $f$ then $a\in A$ and $b\in B$
• if $(a,b)$ and $(a,c)$ are ordered pairs in $f$, then $b=c$

so we can define a partial function as a set $f$ of ordered pairs $(a,b)$ such that:

• if $(a,b)$ is an ordered pair in $f$ then $a\in A$ and $b\in B$
• if $(a,b)$ and $(a,c)$ are ordered pairs in $f$, then $b=c$

(That is, we omit the first listed requirement from the definition of a bona fide function.)

Relationship to Turing machines

Morally speaking, every Turing machine $T$ may be viewed as computing some function $f:N\to N$, by defining $f\left(n\right)$ to be the state of the tape after $T$ has been allowed to execute on the tape which has been initialised with the value $n$.

However, if $T$ does not terminate on input $n$ (for example, it may be the machine "if $n=3$ then return $1$; otherwise loop indefinitely"), then this "morally correct" state of affairs is not accurate: how should we define $f\left(4\right)$? The answer is that we should instead view $f$ as a partial function which is just undefined if $T$ fails to halt on the input in question. So with the example $T$ above, $f$ is the partial function which is only defined at $3$, and $f\left(3\right)=1$.

1. ^{^︎}

   In LaTeX, this symbol is given by \rightharpoonup.