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

maybe this should be under Turing machine rather than partial function?

Morally speaking, every Turing machine $T$ may be viewed as computing some function $f : N \to N$ , by defining $f (n)$ 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 (4)$ ? 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 (3) = 1$ .

^{^︎}
In LaTeX, this symbol is given by \rightharpoonup.

Partial function