Partial function: Difference between revisions

Revision as of 07:36, 15 December 2022

Latest revision as of 16:59, 20 May 2025

(44 intermediate revisions by 21 users not shown)

Line 3:

{{more footnotes|date=August 2014}}

In [[mathematics]], a '''partial function''' {{mvar|f}} from a [[Set (mathematics)|set]] {{mvar|X}} to a set {{mvar|Y}} is a [[function (mathematics)|function]] from a [[subset]] {{mvar|S}} of {{mvar|X}} (possibly the whole {{mvar|X}} itself) to {{mvar|Y}}. The subset {{mvar|S}}, that is, the ''[[Domain of a function|___domain]]'' of {{mvar|f}} viewed as a function, is called the '''___domain of definition''' or '''natural ___domain''' of {{mvar|f}}. If {{mvar|S}} equals {{mvar|X}}, that is, if {{mvar|f}} is defined on every element in {{mvar|X}}, then {{mvar|f}} is said to be a '''total function'''.

MoreIn technicallyother words, a partial function is a [[binary relation]] over two [[Set (mathematics)|sets]] that associates to every element of the first set to ''at most'' one element of the second set; it is thus a [[Binary relation#Special types of binary relations|functional binaryunivalent relation]]. ItThis generalizes the concept of a (total) [[Function (mathematics)|function]] by not requiring ''every'' element of the first set to be associated to ''exactly'' onean element of the second set.

A partial function is often used when its exact ___domain of definition is not known, or is difficult to specify. However, even when the exact ___domain of definition is known, partial functions are often used for simplicity or brevity. This is the case in [[calculus]], where, for example, the [[quotient]] of two functions is a partial function whose ___domain of definition cannot contain the [[Zero of a function|zeros]] of the denominator.; Forin this reason, in calculus, and more generally in [[mathematical analysis]]context, a partial function is generally simply called simply a {{em|function}}.

In [[computability theory]], a [[general recursive function]] is a partial function from the integers to the integers; for many of them no [[algorithm]] can exist for deciding whether theyan arearbitrary such function is in fact total.

When [[Function (mathematics)#Arrow notation|arrow notation]] is used for functions, a partial function <math>f</math> from <math>X</math> to <math>Y</math> is sometimes written as <math>f : X \rightharpoonup Y,</math> <math>f : X \nrightarrow Y,</math> or <math>f : X \hookrightarrow Y.</math> However, there is no general convention, and the latter notation is more commonly used for [[inclusion map]]s or [[embedding]]s.{{citation needed|reason=Provide a few example citations for each notation.|date=July 2019}}

Line 38 ⟶ 40:

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-251">{{cite book|author=Christopher Hollings|title=Mathematics across the Iron Curtain: A History of the Algebraic Theory of Semigroups|url=https://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 inverted to an injective partial function, and a partial function which is both injective and surjective has an injective function as inverse. Furthermore, a function which is injective may be inverted to ana injectivebijective partial function.

The notion of [[Transformation (function)|transformation]] can be generalized to partial functions as well. A '''partial transformation''' is a function <math>f : A \rightharpoonup B,</math> where both <math>A</math> and <math>B</math> are [[subset]]s of some set <math>X.</math><ref name="Hollings2014-251"/>

Line 44 ⟶ 46:

== Function spaces ==

TheFor convenience, denote the set of all partial functions <math>f : X \rightharpoonup Y</math> from a set <math>X</math> to a set <math>Y,</math> denoted by <math>[X \rightharpoonup Y,].</math> This set is the union of allthe sets of functions defined on subsets of <math>X</math> with same codomain <math>Y</math>:

: <math>[X \rightharpoonup Y] = \bigcup_{D \subseteq{ X}} ([D \to Y)],</math>

the latter also written as <math display="inline">\bigcup_{D\subseteq{X}} Y^D.</math> In finite case, its cardinality is

: <math>|[X \rightharpoonup Y]| = (|Y| + 1)^{|X|},</math>

because any partial function can be extended to a function by any fixed value <math>c</math> not contained in <math>Y,</math> so that the codomain is <math>Y \cup \{ c \},</math> an operation which is injective (unique and invertible by restriction).

Line 59 ⟶ 61:

=== Subtraction of natural numbers ===

Subtraction of [[natural numbers]] (in which <math>\mathbb{N}</math> is the non-negative [[integers]]) can be viewed asis a partial function:

: <math>f : \N \times \N \rightharpoonup \N</math>

: <math>f(x,y) = x - y.</math>

Line 75 ⟶ 77:

=== In category theory ===

In [[category theory]], when considering the operation of [[morphism]] composition in [[concrete categories]], the composition operation <math>\circ \;:\; \hom(C) \times \hom(C) \to \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>

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>

Line 94 ⟶ 96:

== See also ==

{{Functions}}

* {{annotated link|Analytic continuation}}

* {{annotated link|Multivalued function}}

Line 101 ⟶ 102:

== References ==

{{reflist|group=note}}

{{reflist}}

{{commons category|Partial mappings}}

* [[Martin Davis (mathematician)|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.

=== Notes ===

{{reflist|group=note}}

{{reflist}}

{{Functions navbox}}

[[Category:Mathematical relations]]

[[Category:Functions and mappings]]

[[Category:Properties of binary relations]]