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: