A partial function is like a Function $f: A \to B$, 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 \rightharpoonup B$ %%note:In LaTeX, this symbol is given by \rightharpoonup.%%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

[todo: maybe this should be under Turing machine rather than partial function?]

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

However, if $\mathcal{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 $\mathcal{T}$ fails to halt on the input in question. So with the example $\mathcal{T}$ above, $f$ is the partial function which is only defined at $3$, and $f(3) = 1$.