Partial function

Written by Patrick Stevens last updated

A partial function is like a function , but where we relax the requirement that must be defined for all . That is, it must still be the case that " and is defined" implies " is defined and ", but now we no longer need to be defined everywhere. We can write [1]to denote that is a partial function with domain and codomain : that is, whenever is defined then we have and .

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 of ordered pairs such that:

  • every appears as the first element of some ordered pair in
  • if is an ordered pair in then and
  • if and are ordered pairs in , then

so we can define a partial function as a set of ordered pairs such that:

  • if is an ordered pair in then and
  • if and are ordered pairs in , then

(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 may be viewed as computing some function , by defining to be the state of the tape after has been allowed to execute on the tape which has been initialised with the value .

However, if does not terminate on input (for example, it may be the machine "if then return ; otherwise loop indefinitely"), then this "morally correct" state of affairs is not accurate: how should we define ? The answer is that we should instead view as a partial function which is just undefined if fails to halt on the input in question. So with the example above, is the partial function which is only defined at , and .

  1. ^︎

    In LaTeX, this symbol is given by \rightharpoonup.

Parents: