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\) noteIn 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

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\).