Partial function

From Wikipedia, the free encyclopedia
  (Redirected from Partial functions)
Jump to: navigation, search
Not to be confused with partial function of a multilinear map or the mathematical concept of a piecewise function.
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

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

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

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

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 \circ : \operatorname{Hom}(C) \times \operatorname{Hom}(C) \to \operatorname{Hom}(C) is a total function if and only if \operatorname{Ob}(C) has one element. The reason for this is that two morphisms f:X\to Y and g:U\to V can only be composed as g \circ f if Y=U, that is, the codomain of f must equal the domain of g.

Discussion and examples[edit]

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

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

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.

Bottom type[edit]

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

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

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, typically denoted by \mathcal{PT}_X.[8][9] The set of all partial bijections on X forms the symmetric inverse semigroup.[8]

See also[edit]

References[edit]

  1. ^ Christopher Hollings (2014). Mathematics across the Iron Curtain: A History of the Algebraic Theory of Semigroups. American Mathematical Society. p. 251. ISBN 978-1-4704-1493-1. 
  2. ^ Christopher Hollings (2014). Mathematics across the Iron Curtain: A History of the Algebraic Theory of Semigroups. American Mathematical Society. p. 251. ISBN 978-1-4704-1493-1. 
  3. ^ Lutz Schröder (2001). "Categories: a free tour". In Jürgen Koslowski and Austin Melton. Categorical Perspectives. Springer Science & Business Media. p. 10. ISBN 978-0-8176-4186-3. 
  4. ^ Neal Koblitz; B. Zilber; Yu. I. Manin (2009). A Course in Mathematical Logic for Mathematicians. Springer Science & Business Media. p. 290. ISBN 978-1-4419-0615-1. 
  5. ^ Francis Borceux (1994). Handbook of Categorical Algebra: Volume 2, Categories and Structures. Cambridge University Press. p. 289. ISBN 978-0-521-44179-7. 
  6. ^ Marco Grandis (2012). Homological Algebra: The Interplay of Homology with Distributive Lattices and Orthodox Semigroups. World Scientific. p. 55. ISBN 978-981-4407-06-9. 
  7. ^ Peter Burmeister (1993). "Partial algebras – an introductory survey". In Ivo G. Rosenberg and Gert Sabidussi. Algebras and Orders. Springer Science & Business Media. ISBN 978-0-7923-2143-9. 
  8. ^ a b Alfred Hoblitzelle Clifford; G. B. Preston (1967). The Algebraic Theory of Semigroups. Volume II. American Mathematical Soc. p. xii. ISBN 978-0-8218-0272-4. 
  9. ^ Olexandr Ganyushkin; Volodymyr Mazorchuk (2008). Classical Finite Transformation Semigroups: An Introduction. Springer Science & Business Media. pp. 16 and 24. ISBN 978-1-84800-281-4. 
  • 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.