Difference between revisions of "Partial function"

From formulasearchengine
Jump to navigation Jump to search
en>Arthur Rubin
(→‎In abstract algebra: unlink redlinks that, if created, would be likely to link _here_)
 
Line 1: Line 1:
 +
{{moreinline|date=August 2014}}
 
{{Distinguish2|partial function of a [[multilinear map]] or the mathematical concept of a [[piecewise function]]}}
 
{{Distinguish2|partial function of a [[multilinear map]] or the mathematical concept of a [[piecewise function]]}}
 +
{{Functions}}
 
{| align="right"
 
{| align="right"
 
|-
 
|-
 
|[[Image:Partial function.svg|thumb|200px|An example of partial function that is injective.]]  
 
|[[Image:Partial function.svg|thumb|200px|An example of partial function that is injective.]]  
 
|-
 
|-
|[[Image:Total function.svg|thumb|200px|An example of total function that is not-injective.]]
+
|[[Image:Total function.svg|thumb|200px|An example of total function that is not injective.]]
 
|}
 
|}
  
In [[mathematics]], a '''partial function''' from ''X'' to ''Y'' (written as ''f: X ↛ Y'') is a [[function (mathematics)|function]] ''f: X' → Y'', where '' X' '' is a [[subset]] of&nbsp;''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''<nowiki>'</nowiki> 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 of a function|domain]], '' X' '', is not known (e.g. many functions in [[computability theory]]).
+
In [[mathematics]], a '''partial function''' from ''X'' to ''Y'' (written as ''f'': ''X'' ''Y'') is a [[function (mathematics)|function]] ''f'': ''X<nowiki>'</nowiki>'' → ''Y'', for some [[subset]] ''X<nowiki>'</nowiki>'' of&nbsp;''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<nowiki>'</nowiki>'' of ''X''). If ''X<nowiki>'</nowiki>'' = ''X'', then ''f'' is called a '''total function''' and is equivalent to a function. Partial functions are often used when the exact [[domain of a function|domain]], ''X<nowiki>'</nowiki>'', is not known (e.g. many functions in [[computability theory]]).
  
 
Specifically, we will say that for any ''x''&nbsp;∈&nbsp;''X'', either:
 
Specifically, we will say that for any ''x''&nbsp;∈&nbsp;''X'', either:
Line 19: Line 21:
 
Thus ''g''(''n'') is only defined for ''n'' that are [[square number|perfect squares]] (i.e.&nbsp;0,&nbsp;1,&nbsp;4,&nbsp;9,&nbsp;16,&nbsp;...). So, ''g''(25)&nbsp;=&nbsp;5, but ''g''(26) is undefined.
 
Thus ''g''(''n'') is only defined for ''n'' that are [[square number|perfect squares]] (i.e.&nbsp;0,&nbsp;1,&nbsp;4,&nbsp;9,&nbsp;16,&nbsp;...). So, ''g''(25)&nbsp;=&nbsp;5, but ''g''(26) is undefined.
  
==Domain of a partial function==
+
== Basic concepts ==
There are two distinct meanings in current mathematical usage for the notion of the [[domain of a function|domain]] of a partial function. Most mathematicians, including [[recursion theory|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 theory|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.
+
There are two distinct meanings in current mathematical usage for the notion of the [[domain of a function|domain]] of a partial function. Most mathematicians, including [[recursion theory|recursion theorists]], use the term "domain of ''f''" for the set of all values ''x'' such that ''f''(''x'') is defined (''X<nowiki>'</nowiki>'' above). But some, particularly [[category theory|category theorists]], consider the domain of a partial function ''f'':''X''&nbsp;&nbsp;''Y'' to be ''X'', and refer to ''X<nowiki>'</nowiki>'' 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.
+
Occasionally, a partial function with domain ''X'' and codomain ''Y'' is written as ''f'': ''X''&nbsp;&nbsp;''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, but the term [[bijection]] generally only applies to total functions.
+
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.<ref name="Hollings2014">{{cite book|author=Christopher Hollings|title=Mathematics across the Iron Curtain: A History of the Algebraic Theory of Semigroups|url=http://books.google.com/books?id=O9wJBAAAQBAJ&pg=PA251|year=2014|publisher=American Mathematical Society|isbn=978-1-4704-1493-1|page=251}}</ref>
  
 
An injective partial function may be [[inverse relation|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.
 
An injective partial function may be [[inverse relation|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 (function)|transformation]] generalized to partial functions as well. A '''partial transformation''' is a function ''f'': ''A'' → ''B'', where both ''A'' and ''B'' are [[subset]]s of some set ''X''.<ref name="Hollings2014-251">{{cite book|author=Christopher Hollings|title=Mathematics across the Iron Curtain: A History of the Algebraic Theory of Semigroups|url=http://books.google.com/books?id=O9wJBAAAQBAJ&pg=PA251|year=2014|publisher=American Mathematical Society|isbn=978-1-4704-1493-1|page=251}}</ref>
  
 
==Total function==
 
==Total function==
Total function is a synonym for [[Function (mathematics)|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 [[Category theory|Concrete Categories]], the composition operation <math>\circ : \operatorname{Hom}(C) \times \operatorname{Hom}(C) \to \operatorname{Hom}(C)</math> is a total function if and only if <math>\operatorname{Ob}(C)</math> has one element. The reason for this is that two morphisms <math>f:X\to Y</math> and <math>g:U\to V</math> can only be composed as <math>g \circ f</math> if <math>Y=U</math>, that is, the codomain of <math>f</math> must equal the domain of <math>g</math>.
+
Total function is a synonym for [[Function (mathematics)|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 [[Category theory|Concrete Categories]], the composition operation <math>\circ : \operatorname{Hom}(C) \times \operatorname{Hom}(C) \to \operatorname{Hom}(C)</math> is a total function if and only if <math>\operatorname{Ob}(C)</math> has one element. The reason for this is that two morphisms <math>f:X\to Y</math> and <math>g:U\to V</math> can only be composed as <math>g \circ f</math> if <math>Y=U</math>, that is, the codomain of <math>f</math> must equal the domain of <math>g</math>.
  
 
==Discussion and examples==
 
==Discussion and examples==
Line 47: Line 53:
 
===Bottom type===
 
===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 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 [[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 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 [[Equivalence of categories|equivalent]] to but not [[Isomorphism of categories|isomorphic]] with the category of [[pointed set]]s and point-preserving maps.<ref name="KoslowskiMelton2001">{{cite book|editor=Jürgen Koslowski and Austin Melton|title=Categorical Perspectives|year=2001|publisher=Springer Science & Business Media|isbn=978-0-8176-4186-3|page=10|author=Lutz Schröder|chapter=Categories: a free tour}}</ref> 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]]."<ref name="KoblitzZilber2009">{{cite book|author1=Neal Koblitz|author2=B. Zilber|author3=Yu. I. Manin|title=A Course in Mathematical Logic for Mathematicians|year=2009|publisher=Springer Science & Business Media|isbn=978-1-4419-0615-1|page=290}}</ref>
 +
 +
The category of sets and partial bijections is equivalent to its [[Opposite category|dual]].<ref name="Borceux1994">{{cite book|author=Francis Borceux|title=Handbook of Categorical Algebra: Volume 2, Categories and Structures|url=http://books.google.com/books?id=5i2v9q0m5XAC&pg=PA289|year=1994|publisher=Cambridge University Press|isbn=978-0-521-44179-7|page=289}}</ref> It is the prototypical [[inverse category]].<ref name="Grandis2012">{{cite book|author=Marco Grandis|title=Homological Algebra: The Interplay of Homology with Distributive Lattices and Orthodox Semigroups|url=http://books.google.com/books?id=TWqhelao4KsC&pg=PA55|year=2012|publisher=World Scientific|isbn=978-981-4407-06-9|page=55}}</ref>
 +
 +
===In abstract algebra===
 +
[[Partial algebra]] generalizes the notion of [[universal algebra]] to partial [[Operation (mathematics)|operations]]. An example would be a [[Field (mathematics)|field]], in which the multiplicative inversion is the only proper partial operation (because [[division by zero]] is not defined).<ref name="RosenbergSabidussi1993">{{cite book|editors=Ivo G. Rosenberg and Gert Sabidussi|title=Algebras and Orders|year=1993|publisher=Springer Science & Business Media|isbn=978-0-7923-2143-9|author=Peter Burmeister|chapter=Partial algebras – an introductory survey}}</ref>
 +
 +
The set of all partial functions (partial [[transformation (function)|transformation]]s) 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 <math>\mathcal{PT}_X</math>.<ref name="CliffordPreston1967">{{cite book|author1=Alfred Hoblitzelle Clifford|author2=G. B. Preston|title=The Algebraic Theory of Semigroups. Volume II|url=http://books.google.com/books?id=756KAwAAQBAJ&pg=PR12|year=1967|publisher=American Mathematical Soc.|isbn=978-0-8218-0272-4|page=xii}}</ref><ref name="Higgins1992">{{cite book|author=Peter M. Higgins|title=Techniques of semigroup theory|year=1992|publisher=Oxford University Press, Incorporated|isbn=978-0-19-853577-5|page=4}}</ref><ref name="GanyushkinMazorchuk2008">{{cite book|author1=Olexandr Ganyushkin|author2=Volodymyr Mazorchuk|title=Classical Finite Transformation Semigroups: An Introduction|year=2008|publisher=Springer Science & Business Media|isbn=978-1-84800-281-4|pages=16 and 24}}</ref> The set of all partial bijections on ''X'' forms the [[symmetric inverse semigroup]].<ref name="CliffordPreston1967"/><ref name="Higgins1992"/>
  
 
== See also ==
 
== See also ==
Line 58: Line 74:
 
* [[Surjective function]]
 
* [[Surjective function]]
 
* [[Multivalued function]]
 
* [[Multivalued function]]
* [[Symmetric inverse semigroup]]
 
 
* [[Densely defined operator]]
 
* [[Densely defined operator]]
  
 
== References ==
 
== References ==
*[[Martin Davis]] (1958), ''Computability and Unsolvability'', McGraw-Hill Book Company, Inc, New York. Republished by Dover in 1982. ISBN 0-486-61471-9.
+
{{Reflist}}
 +
*[[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.
 
*[[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.
+
*[[Harold S. Stone]] (1972), ''Introduction to Computer Organization and Data Structures'', McGraw–Hill Book Company, New York.
  
 
[[Category:Mathematical relations]]
 
[[Category:Mathematical relations]]
 
[[Category:Functions and mappings]]
 
[[Category:Functions and mappings]]

Latest revision as of 03:38, 9 September 2014

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.