Función parcial

En matemáticas , una función parcial $f$ de un conjunto $X$ a un conjunto $Y$ es una función de un subconjunto $S$ de $X$ (posiblemente el conjunto $X$ completo ) a $Y.$ El subconjunto $S$ , es decir, el dominio de $f$ considerado como una función, se denomina dominio de definición o dominio natural de $f$ . Si $S$ es igual $a X$ , es decir, si $f$ está definida en cada elemento de $X$ , entonces se dice que $f es una$ función total .

En otras palabras, una función parcial es una relación binaria entre dos conjuntos que asocia a cada elemento del primer conjunto, como máximo, un elemento del segundo; por lo tanto, es una relación univalente . Esto generaliza el concepto de función (total) al no requerir que cada elemento del primer conjunto esté asociado a un elemento del segundo.

Una función parcial se usa a menudo cuando se desconoce su dominio de definición exacto o es difícil de especificar. Sin embargo, incluso cuando se conoce el dominio de definición exacto, las funciones parciales se usan con frecuencia por simplicidad o brevedad. Este es el caso en cálculo , donde, por ejemplo, el cociente de dos funciones es una función parcial cuyo dominio de definición no puede contener los ceros del denominador; en este contexto, una función parcial generalmente se llama simplemente función .

En la teoría de la computabilidad , una función recursiva general es una función parcial de los números enteros a los números enteros; no puede existir ningún algoritmo para decidir si una función arbitraria de este tipo es, de hecho, total.

Cuando se utiliza la notación de flechas para funciones, una función parcial $f$ de $X$ a $Y$ a veces se escribe como $f:X\rightharpoonup Y,$ $f:X\nrightarrow Y,$ o $f:X\hookrightarrow Y.$ Sin embargo, no existe una convención general, y la segunda notación se usa más comúnmente para mapas de inclusión o incrustaciones .

Específicamente, para una función parcial $f:X\rightharpoonup Y,$ y cualquier $x\in X,$ uno tiene una de las siguientes opciones:

$f(x)=y\in Y$ (es un único elemento en $Y$ ), o
$f(x)$ no está definido.

Por ejemplo, si $f$ ¿La función de raíz cuadrada está restringida a los números enteros?

f:\mathbb {Z} \to \mathbb {N} ,

definido por:

f(n)=m

si, y solo si,

m^{2}=n,

m\in \mathbb {N} ,n\in \mathbb {Z} ,

entonces $f(n)$ solo se define si $n$ es un cuadrado perfecto (es decir, $0,1,4,9,16,\ldots$ ). Entonces $f(25)=5$ pero $f(26)$ no está definido.

Conceptos básicos

Una función parcial surge de la consideración de aplicaciones entre dos conjuntos $X$ e $Y$ que pueden no estar definidas en todo el conjunto $X.$ ^{[ 1 ]} Un ejemplo común es la operación de raíz cuadrada en los números reales . $\mathbb {R}$ : debido a que los números reales negativos no tienen raíces cuadradas reales, la operación puede verse como una función parcial de $\mathbb {R}$ a $\mathbb {R} .$ El dominio de definición de una función parcial es el subconjunto $S$ de $X$ sobre el cual se define la función parcial; en este caso, la función parcial también puede verse como una función de $S$ a $Y.$ En el ejemplo de la operación de raíz cuadrada, el conjunto $S$ consta de los números reales no negativos. $[0,+\infty ).$

La noción de función parcial resulta particularmente conveniente cuando se desconoce o incluso se desconoce el dominio exacto de definición. Para un ejemplo de esto último en informática, véase el problema de la parada .

En caso de que el dominio de definición $S$ sea igual al conjunto completo $X$ , se dice que la función parcial es total . Por lo tanto, las funciones parciales totales de $X$ a $Y$ coinciden con las funciones de $X$ a $Y.$

Muchas propiedades de las funciones pueden extenderse en el sentido apropiado de las funciones parciales. Se dice que una función parcial es inyectiva , sobreyectiva o biyectiva cuando la función resultante de restringir la función parcial a su dominio de definición es inyectiva, sobreyectiva o biyectiva, respectivamente.

Dado que una función es trivialmente sobreyectiva cuando se restringe a su imagen, el término biyección parcial denota una función parcial que es inyectiva. ^{[ 2 ]}

Una función parcial inyectiva puede invertirse para obtener otra función parcial inyectiva, y una función parcial que es tanto inyectiva como sobreyectiva tiene una función inyectiva como inversa. Además, una función inyectiva puede invertirse para obtener una función parcial biyectiva.

The notion of transformation can be generalized to partial functions as well. A partial transformation is a function $f:A\rightharpoonup B,$ where both $A$ and $B$ are subsets of some set $X.$ ^[2]

Function spaces

For convenience, denote the set of all partial functions $f:X\rightharpoonup Y$ from a set $X$ to a set $Y$ by $[X\rightharpoonup Y].$ This set is the union of the sets of functions defined on subsets of $X$ with same codomain $Y$ :

[X\rightharpoonup Y]=\bigcup _{D\subseteq X}[D\to Y],

the latter also written as ${\textstyle \bigcup _{D\subseteq {X}}Y^{D}.}$ In finite case, its cardinality is

|[X\rightharpoonup Y]|=(|Y|+1)^{|X|},

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

Discussion and examples

The first diagram at the top of the article represents a partial function that is not a 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 function since every element on the left-hand set is associated with exactly one element in the right hand set.

Natural logarithm

The natural logarithm function mapping the real numbers to themselves is a partial function, but not a (total) function, since it is undefined for non-positive real inputs. 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 function.

Subtraction of natural numbers

Subtraction of natural numbers (in which $\mathbb {N}$ is the non-negative integers) is a partial function:

f:\mathbb {N} \times \mathbb {N} \rightharpoonup \mathbb {N}

f(x,y)=xy.

It is defined only when $x\geq y.$

Bottom element

In denotational semantics a partial function is considered as returning the bottom element when it is undefined.

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 domain of definition of the function.

In category theory

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

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 set, $X,$ 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]

Charts and atlases for manifolds and fiber bundles

Charts in the atlases which specify the structure of manifolds and fiber bundles are partial functions. In the case of manifolds, the domain is the point set of the manifold. In the case of fiber bundles, the domain is the space of the fiber bundle. In these applications, the most important construction is the transition map, which is the composite of one chart with the inverse of another. The initial classification of manifolds and fiber bundles is largely expressed in terms of constraints on these transition maps.

The reason for the use of partial functions instead of functions is to permit general global topologies to be represented by stitching together local patches to describe the global structure. The "patches" are the domains where the charts are defined.

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.

Notes

↑Garrett Birkhoff & Thomas Bartee (1970) Modern Applied Algebra, page 13, McGraw-Hill Book Company
1 2Christopher 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.
↑Lutz Schröder (2001). "Categories: a free tour". In Jürgen Koslowski and Austin Melton (ed.). Categorical Perspectives. Springer Science & Business Media. p. 10. ISBN 978-0-8176-4186-3.
↑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.
↑Francis Borceux (1994). Handbook of Categorical Algebra: Volume 2, Categories and Structures. Cambridge University Press. p. 289. ISBN 978-0-521-44179-7.
↑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.
↑Peter Burmeister (1993). "Partial algebras – an introductory survey". In Ivo G. Rosenberg; Gert Sabidussi (eds.). Algebras and Orders. Springer Science & Business Media. ISBN 978-0-7923-2143-9.
1 2 Alfred Hoblitzelle Clifford; GB Preston (1967). La teoría algebraica de los semigrupos. Volumen II . American Mathematical Soc. pág. xii. ISBN 978-0-8218-0272-4.
1 2 Peter M. Higgins (1992). Técnicas de la teoría de semigrupos . Oxford University Press, Incorporated. pág. 4. ISBN 978-0-19-853577-5.
↑ Olexandr Ganyushkin; Volodymyr Mazorchuk (2008). Semigrupos de transformación finita clásica: una introducción . Springer Science & Business Media. págs. 16 y 24. ISBN 978-1-84800-281-4.

[1] Garrett Birkhoff & Thomas Bartee (1970) Modern Applied Algebra, page 13, McGraw-Hill Book Company

[Hollings2014-251-2] 1 2Christopher 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.

[KoslowskiMelton2001-3] Lutz Schröder (2001). "Categories: a free tour". In Jürgen Koslowski and Austin Melton (ed.). Categorical Perspectives. Springer Science & Business Media. p. 10. ISBN 978-0-8176-4186-3.

[KoblitzZilber2009-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.

[Borceux1994-5] Francis Borceux (1994). Handbook of Categorical Algebra: Volume 2, Categories and Structures. Cambridge University Press. p. 289. ISBN 978-0-521-44179-7.

[Grandis2012-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.

[RosenbergSabidussi1993-7] Peter Burmeister (1993). "Partial algebras – an introductory survey". In Ivo G. Rosenberg; Gert Sabidussi (eds.). Algebras and Orders. Springer Science & Business Media. ISBN 978-0-7923-2143-9.

[CliffordPreston1967-8] 1 2 Alfred Hoblitzelle Clifford; GB Preston (1967). La teoría algebraica de los semigrupos. Volumen II . American Mathematical Soc. pág. xii. ISBN 978-0-8218-0272-4.

[Higgins1992-9] 1 2 Peter M. Higgins (1992). Técnicas de la teoría de semigrupos . Oxford University Press, Incorporated. pág. 4. ISBN 978-0-19-853577-5.

[GanyushkinMazorchuk2008-10] Olexandr Ganyushkin; Volodymyr Mazorchuk (2008). Semigrupos de transformación finita clásica: una introducción . Springer Science & Business Media. págs. 16 y 24. ISBN 978-1-84800-281-4.

[ 1 ]

[ 2 ]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]