Partial function

This article includes a list of general references but lacks sufficient corresponding inline citations. Please help improve this article by introducing more precise citations. (August 2014) (Learn how and when to remove this message)

In mathematics, a partial function f from a set X to a set Y is a function from a subset S of X (possibly the whole X itself) to Y. The subset S, that is, the domain of f viewed as a function, is called the domain of definition or natural domain of f. If S equals X, that is, if f is defined on every element in X, then f is said to be a total function.

In other words, a partial function is a binary relation over two sets that associates to every element of the first set at most one element of the second set; it is thus a univalent relation. This generalizes the concept of a (total) function by not requiring every element of the first set to be associated to an element of the second set.

A partial function is often used when its exact domain of definition is not known, or is difficult to specify. However, even when the exact domain of definition is known, partial functions are often used for simplicity or brevity. This is the case in calculus, where, for example, the quotient of two functions is a partial function whose domain of definition cannot contain the zeros of the denominator; in this context, a partial function is generally simply called a function.

In computability theory, a general recursive function is a partial function from the integers to the integers; no algorithm can exist for deciding whether an arbitrary such function is in fact total.

When arrow notation is used for functions, a partial function ${\displaystyle f}$ from ${\displaystyle X}$ to ${\displaystyle Y}$ is sometimes written as ${\displaystyle f:X\rightharpoonup Y,}$ ${\displaystyle f:X\nrightarrow Y,}$ or ${\displaystyle f:X\hookrightarrow Y.}$ However, there is no general convention, and the latter notation is more commonly used for inclusion maps or embeddings.^{[citation needed]}

Specifically, for a partial function ${\displaystyle f:X\rightharpoonup Y,}$ and any ${\displaystyle x\in X,}$ one has either:

• ${\displaystyle f(x)=y\in Y}$ (it is a single element in Y), or
• ${\displaystyle f(x)}$ is undefined.

For example, if ${\displaystyle f}$ is the square root function restricted to the integers

${\displaystyle f:\mathbb {Z} \to \mathbb {N} ,}$

defined by:

${\displaystyle f(n)=m}$ if, and only if, ${\displaystyle m^{2}=n,}$ ${\displaystyle m\in \mathbb {N} ,n\in \mathbb {Z} ,}$

then ${\displaystyle f(n)}$ is only defined if ${\displaystyle n}$ is a perfect square (that is, ${\displaystyle 0,1,4,9,16,\ldots }$). So ${\displaystyle f(25)=5}$ but ${\displaystyle f(26)}$ is undefined.

Basic concepts

A partial function arises from the consideration of maps between two sets X and Y that may not be defined on the entire set X.^[1] A common example is the square root operation on the real numbers ${\displaystyle \mathbb {R} }$: because negative real numbers do not have real square roots, the operation can be viewed as a partial function from ${\displaystyle \mathbb {R} }$ to ${\displaystyle \mathbb {R} .}$ The domain of definition of a partial function is the subset S of X on which the partial function is defined; in this case, the partial function may also be viewed as a function from S to Y. In the example of the square root operation, the set S consists of the nonnegative real numbers ${\displaystyle [0,+\infty ).}$

The notion of partial function is particularly convenient when the exact domain of definition is unknown or even unknowable. For a computer-science example of the latter, see Halting problem.

In case the domain of definition S is equal to the whole set X, the partial function is said to be total. Thus, total partial functions from X to Y coincide with functions from X to Y.

Many properties of functions can be extended in an appropriate sense of partial functions. A partial function is said to be injective, surjective, or bijective when the function given by the restriction of the partial function to its domain of definition is injective, surjective, or bijective, respectively.

Because a function is trivially surjective when restricted to its image, the term partial bijection denotes a partial function which is injective.^[2]

An injective partial function may be inverted to an injective partial function, and a partial function which is both injective and surjective has an injective function as inverse. Furthermore, a function which is injective may be inverted to a bijective partial function.

The notion of transformation can be generalized to partial functions as well. A partial transformation is a function ${\displaystyle f:A\rightharpoonup B,}$ where both ${\displaystyle A}$ and ${\displaystyle B}$ are subsets of some set ${\displaystyle X.}$^[2]

Function spaces

For convenience, denote the set of all partial functions ${\displaystyle f:X\rightharpoonup Y}$ from a set ${\displaystyle X}$ to a set ${\displaystyle Y}$ by ${\displaystyle [X\rightharpoonup Y].}$ This set is the union of the sets of functions defined on subsets of ${\displaystyle X}$ with same codomain ${\displaystyle Y}$:

${\displaystyle [X\rightharpoonup Y]=\bigcup _{D\subseteq X}[D\to Y],}$

the latter also written as ${\textstyle \bigcup _{D\subseteq {X}}Y^{D}.}$ In finite case, its cardinality is

${\displaystyle |[X\rightharpoonup Y]|=(|Y|+1)^{|X|},}$

because any partial function can be extended to a function by any fixed value ${\displaystyle c}$ not contained in ${\displaystyle Y,}$ so that the codomain is ${\displaystyle Y\cup \{c\},}$ an operation which is injective (unique and invertible by restriction).

Discussion and examples

The first diagram at the top of the article represents a partial function that is not a function since the element 1 in the left-hand set is not associated with anything in the right-hand set. Whereas, the second diagram represents a function since every element on the left-hand set is associated with exactly one element in the right hand set.

See also

• Analytic continuation – Extension of the domain of an analytic function (mathematics)
• Multivalued function – Generalized mathematical function
• Densely defined operator – Linear operator on dense subset of its apparent domain

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.