World Library  
Flag as Inappropriate
Email this Article

Partial function

Article Id: WHEBN0000023577
Reproduction Date:

Title: Partial function  
Author: World Heritage Encyclopedia
Language: English
Subject: Semicomputable function, Function (mathematics), Register machine, Groupoid, Computable function
Collection: Functions and Mappings, Mathematical Relations
Publisher: World Heritage Encyclopedia
Publication
Date:
 

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

Contents

  • Basic concepts 1
  • Total function 2
  • Discussion and examples 3
    • Natural logarithm 3.1
    • Subtraction of natural numbers 3.2
    • Bottom type 3.3
    • In category theory 3.4
    • In abstract algebra 3.5
  • See also 4
  • References 5

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

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:

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

It is only defined when x \ge y.

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

See also

References

  1. ^ Christopher Hollings (2014). Mathematics across the Iron Curtain: A History of the Algebraic Theory of Semigroups. American Mathematical Society. p. 251.  
  2. ^ Christopher Hollings (2014). Mathematics across the Iron Curtain: A History of the Algebraic Theory of Semigroups. American Mathematical Society. p. 251.  
  3. ^ Lutz Schröder (2001). "Categories: a free tour". In Jürgen Koslowski and Austin Melton. Categorical Perspectives. Springer Science & Business Media. p. 10.  
  4. ^ Neal Koblitz; B. Zilber; Yu. I. Manin (2009). A Course in Mathematical Logic for Mathematicians. Springer Science & Business Media. p. 290.  
  5. ^ Francis Borceux (1994). Handbook of Categorical Algebra: Volume 2, Categories and Structures. Cambridge University Press. p. 289.  
  6. ^ Marco Grandis (2012). Homological Algebra: The Interplay of Homology with Distributive Lattices and Orthodox Semigroups. World Scientific. p. 55.  
  7. ^ Peter Burmeister (1993). "Partial algebras – an introductory survey". In Ivo G. Rosenberg and Gert Sabidussi. Algebras and Orders. Springer Science & Business Media.  
  8. ^ a b Alfred Hoblitzelle Clifford; G. B. Preston (1967). The Algebraic Theory of Semigroups. Volume II. American Mathematical Soc. p. xii.  
  9. ^ a b Peter M. Higgins (1992). Techniques of semigroup theory. Oxford University Press, Incorporated. p. 4.  
  10. ^ Olexandr Ganyushkin; Volodymyr Mazorchuk (2008). Classical Finite Transformation Semigroups: An Introduction. Springer Science & Business Media. pp. 16 and 24.  
  • 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.
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.