Partial function

An example of a partial function that is not a total function.

An example of a partial function that is also a total function.

In mathematics, a partial function is a binary relation that associates elements of a set, sometimes called its domain, with at most one element of another (possibly the same) set, called its codomain. However, not every element of the domain has to be associated with an element of the codomain.

An example of a partial function with domain and codomain equal to the integers, is given by

$g(n)={\sqrt {n}},$

where g(n) is only defined for those nonnegative integers which are perfect squares, that is are equal to the square of some integer.

If every element of the domain of a binary relation f is associated to exactly one element of its codomain, then f is termed a total function, or simply a "function". Note that a total function is a partial function; this is consistent with the concept that the whole is a part of itself (see subset).

The term partial function may also refer to other meanings: In the context of multilinear maps, one speaks of the partial function with respect to the k-th argument, when all other arguments are fixed.

Domain of a partial function

There are two distinct meanings in current mathematical usage for the notion of the domain of a partial function. One, probably the less common, but favored by category theorists, is the one alluded to above: The domain of a partial function f:X→Y is X. Some authors may refer to the domain of definition as those values on which the function is defined, and consider it distinct from the domain.

Many other mathematicians, including recursion theorists, prefer to reserve the term "domain of f" for the set of all values x such that f(x) is defined. In this terminology, a partial function on a set S is simply a function whose domain is a subset of S.

Discussion and examples

The first diagram above represents a partial function that is not a total function since the element 1 in the left-hand set is not associated with anything in the right-hand set.

Natural logarithm

Consider the natural logarithm function mapping the real numbers to themselves. The logarithm of a non-positive real is not a real number, so the natural logarithm function doesn't associate any real number in the codomain with any non-positive real number in the domain. Therefore, the natural logarithm function is not a total function when viewed as a function from the reals to themselves, but it is a partial function. If the domain is restricted to only include the positive reals (that is, if the natural logarithm function is viewed as a function from the positive reals to the reals), then the natural logarithm is a total function.

Subtraction of natural numbers

Subtraction of natural numbers (including zero) can be viewed as a partial function from the Cartesian product N×N to N; f:(x,y) → x - y. It is only defined when x≥y.

Davis (1958) considered a Turing-code equivalent to this partial function to demonstrate the notions of "computable" versus "partially-computable" functions. He showed that when the Turing machine encounters improper data (x < y) caused the machine to enter an infinite loop. This approach was also studied by Kleene 1952. Davis then goes on to produce code that would provide 0 as an output when x < y; the function is then "computable". Thus he shows that any partially computable function f(x) can be completed by setting $g(x)={\begin{cases}f(x)&{\mbox{where }}f(x){\mbox{ is defined}}\\0,&{\mbox{otherwise}}.\end{cases}}$

See also

• Bijection
• Injective function
• Surjective function
• Multivalued function
• Symmetric inverse semigroup

References

• Martin Davis (1958), Computability and Unsolvability, McGraw-Hill Book Company, Inc, New York. Republished by Dover in 1982. ISBN 0-486-61471-9.
• Stephen Kleene (1952), Introduction to Meta-Mathematics, North-Holland Publishing Company, Amsterdam, Netherlands, 10th printing with corrections added on 7th printing (1974). ISBN 0-7204-2103-9.
• Harold S. Stone (1972), Introduction to Computer Organization and Data Structures, McGraw-Hill Book Company, New York.