# Partial function

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

Parents: