Partial function

From formulasearchengine
Revision as of 03:38, 9 September 2014 by en>Arthur Rubin (→‎In abstract algebra: unlink redlinks that, if created, would be likely to link _here_)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Template:Moreinline Template:Distinguish2 Template:Functions

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

In mathematics, a partial function from X to Y (written as f: XY) is a function f: X'Y, for some subset X' of X. It generalizes the concept of a function f: XY 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: AB, 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:

It is only defined when .

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

  1. {{#invoke:citation/CS1|citation |CitationClass=book }}
  2. {{#invoke:citation/CS1|citation |CitationClass=book }}
  3. {{#invoke:citation/CS1|citation |CitationClass=book }}
  4. {{#invoke:citation/CS1|citation |CitationClass=book }}
  5. {{#invoke:citation/CS1|citation |CitationClass=book }}
  6. {{#invoke:citation/CS1|citation |CitationClass=book }}
  7. {{#invoke:citation/CS1|citation |CitationClass=book }}
  8. 8.0 8.1 {{#invoke:citation/CS1|citation |CitationClass=book }}
  9. 9.0 9.1 {{#invoke:citation/CS1|citation |CitationClass=book }}
  10. {{#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.