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$~$.