Partial function

From Wikipedia, the free encyclopedia

Jump to: navigation, search
Not to be confused with partial function of a multilinear map.
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 from X to Y is a function f: X' → Y, where X' is a subset of X. It generalizes the concept of a function by not forcing f to map every element of X to an element of Y (only some subset X^\prime \subseteq 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 \in X, either:

  • f(x) = y \in 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

g\colon \mathbb{Z} \to \mathbb{Z}
g(n) = \sqrt{n}

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

Contents

[edit] Domain of a partial function

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.

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

[edit] 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.

[edit] 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.

[edit] Subtraction of natural numbers

Subtraction of natural numbers (non-negative integers) can be viewed as a partial function:

f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}
f(x,y) = x − y

It is only defined when x \ge y.

[edit] 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.

[edit] See also

[edit] 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.
Retrieved from "http://en.wikipedia.org/wiki/Partial_function"