# Partial function

Template:Moreinline Template:Distinguish2 Template:Functions

In mathematics, a **partial function** from *X* to *Y* (written as *f*: *X* ↛ *Y*) is a function *f*: *X'* → *Y*, for some subset *X'* of *X*. It generalizes the concept of a function *f*: *X* → *Y* by not forcing *f* to map *every* element of *X* to an element of *Y* (only some subset *X'* of *X*). If *X'* = *X*, then *f* is called a **total function** and is equivalent to a function. Partial functions are often used when the exact domain, *X'*, is not known (e.g. many functions in computability theory).

Specifically, we will say that for any *x* ∈ *X*, either:

*f*(*x*) =*y*∈*Y*(it is defined as a single element in*Y*) or*f*(*x*) is undefined.

For example we can consider the square root function restricted to the integers

Thus *g*(*n*) is only defined for *n* that are perfect squares (i.e. 0, 1, 4, 9, 16, ...). So, *g*(25) = 5, but *g*(26) is undefined.

## Basic concepts

There are two distinct meanings in current mathematical usage for the notion of the domain of a partial function. Most mathematicians, including recursion theorists, use the term "domain of *f*" for the set of all values *x* such that *f*(*x*) is defined (*X'* above). But some, particularly category theorists, consider the domain of a partial function *f*:*X* → *Y* to be *X*, and refer to *X'* as the **domain of definition**. Similarly, the term range can refer to either the codomain or the *image* of a function.

Occasionally, a partial function with domain *X* and codomain *Y* is written as *f*: *X* ⇸ *Y*, using an arrow with vertical stroke.

A partial function is said to be injective or surjective when the total function given by the restriction of the partial function to its domain of definition is. A partial function may be both injective and surjective.

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

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 total function which is injective may be inverted to an injective partial function.

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

## Total function

Total function is a synonym for function. The use of the prefix "total" is to suggest that it is a special case of a partial function. For example, when considering the operation of morphism composition in Concrete Categories, the composition operation is a total function if and only if has one element. The reason for this is that two morphisms and can only be composed as if , that is, the codomain of must equal the domain of .

## 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. Whereas, the second diagram represents a total function since every element on the left-hand set is associated with exactly one element 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 (non-negative integers) can be viewed as a partial function:

### Bottom type

In some automated theorem proving systems a partial function is considered as returning the bottom type when it is undefined. The Curry–Howard correspondence uses this to map proofs and computer programs to each other.

In computer science a partial function corresponds to a subroutine that raises an exception or loops forever. The IEEE floating point standard defines a not-a-number value which is returned when a floating point operation is undefined and exceptions are suppressed, e.g. when the square root of a negative number is requested.

In a programming language where function parameters are statically typed, a function may be defined as a partial function because the language's type system cannot express the exact domain of the function, so the programmer instead gives it the smallest domain which is expressible as a type and contains the true domain.

### In category theory

The category of sets and partial functions is equivalent to but not isomorphic with the category of pointed sets and point-preserving maps.^{[3]} One textbook notes that "This formal completion of sets and partial maps by adding “improper,” “infinite” elements was reinvented many times, in particular, in topology (one-point compactification) and in theoretical computer science."^{[4]}

The category of sets and partial bijections is equivalent to its dual.^{[5]} It is the prototypical inverse category.^{[6]}

### In abstract algebra

Partial algebra generalizes the notion of universal algebra to partial operations. An example would be a field, in which the multiplicative inversion is the only proper partial operation (because division by zero is not defined).^{[7]}

The set of all partial functions (partial transformations) on a given base *X* set forms a regular semigroup called the semigroup of all partial transformations (or the partial transformation semigroup on *X*), typically denoted by .^{[8]}^{[9]}^{[10]} The set of all partial bijections on *X* forms the symmetric inverse semigroup.^{[8]}^{[9]}

## See also

## References

- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑
^{8.0}^{8.1}{{#invoke:citation/CS1|citation |CitationClass=book }} - ↑
^{9.0}^{9.1}{{#invoke:citation/CS1|citation |CitationClass=book }} - ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}

- 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.