# Partial function

A par­tial func­tion is like a func­tion $$f: A \to B$$, but where we re­lax the re­quire­ment 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” im­plies “$f(b)$ is defined and $$f(a) = f(b)$$”, but now we no longer need $$f(a)$$ to be defined ev­ery­where. We can write $$f: A \rightharpoonup B$$ noteIn LaTeX, this sym­bol is given by \righthar­poonup.to de­note that $$f$$ is a par­tial func­tion with do­main $$A$$ and codomain $$B$$: that is, when­ever $$f(x)$$ is defined then we have $$x \in A$$ and $$f(x) \in B$$.

This idea is es­sen­tially the “flip side” to the dis­tinc­tion be­tween the codomain vs image di­chotomy.

# Im­ple­men­ta­tion in set theory

Just as a func­tion can be im­ple­mented as a set $$f$$ of or­dered pairs $$(a, b)$$ such that:

• ev­ery $$x \in A$$ ap­pears as the first el­e­ment of some or­dered pair in $$f$$

• if $$(a, b)$$ is an or­dered pair in $$f$$ then $$a \in A$$ and $$b \in B$$

• if $$(a, b)$$ and $$(a, c)$$ are or­dered pairs in $$f$$, then $$b=c$$

so we can define a par­tial func­tion as a set $$f$$ of or­dered pairs $$(a,b)$$ such that:

• if $$(a, b)$$ is an or­dered pair in $$f$$ then $$a \in A$$ and $$b \in B$$

• if $$(a, b)$$ and $$(a, c)$$ are or­dered pairs in $$f$$, then $$b=c$$

(That is, we omit the first listed re­quire­ment from the defi­ni­tion of a bona fide func­tion.)

# Re­la­tion­ship to Tur­ing machines

maybe this should be un­der Tur­ing ma­chine rather than par­tial func­tion?

Mo­rally speak­ing, ev­ery Tur­ing ma­chine $$\mathcal{T}$$ may be viewed as com­put­ing some func­tion $$f: \mathbb{N} \to \mathbb{N}$$, by defin­ing $$f(n)$$ to be the state of the tape af­ter $$\mathcal{T}$$ has been al­lowed to ex­e­cute on the tape which has been ini­tial­ised with the value $$n$$.

How­ever, if $$\mathcal{T}$$ does not ter­mi­nate on in­put $$n$$ (for ex­am­ple, it may be the ma­chine “if $$n = 3$$ then re­turn $$1$$; oth­er­wise loop in­definitely”), then this “morally cor­rect” state of af­fairs is not ac­cu­rate: how should we define $$f(4)$$? The an­swer is that we should in­stead view $$f$$ as a par­tial func­tion which is just un­defined if $$\mathcal{T}$$ fails to halt on the in­put in ques­tion. So with the ex­am­ple $$\mathcal{T}$$ above, $$f$$ is the par­tial func­tion which is only defined at $$3$$, and $$f(3) = 1$$.

Parents: