HOME

TheInfoList




In
mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
, a partial function from a set to a set is a function from a
subset In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...

subset
of (possibly itself) to . The subset , that is, the
domain Domain may refer to: Mathematics *Domain of a function In mathematics, the domain of a Function (mathematics), function is the Set (mathematics), set of inputs accepted by the function. It is sometimes denoted by \operatorname(f), where is th ...
of viewed as a function, is called the domain of definition of . If equals , that is, if is defined on every element in , then is said to be total. More technically, a partial function is a
binary relation Binary may refer to: Science and technology Mathematics * Binary number In mathematics and digital electronics Digital electronics is a field of electronics The field of electronics is a branch of physics and electrical engineeri ...
over two sets that associates every element of the first set to ''at most'' one element of the second set; it is thus a functional binary relation. It generalizes the concept of a (total)
function Function or functionality may refer to: Computing * Function key A function key is a key on a computer A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations automatically. Modern comp ...
by not requiring every element of the first set to be associated to ''exactly'' one element of the second set. A partial function is often used when its exact domain of definition is not known or difficult to specify. This is the case in
calculus Calculus, originally called infinitesimal calculus or "the calculus of infinitesimals", is the mathematics, mathematical study of continuous change, in the same way that geometry is the study of shape and algebra is the study of generalizations ...

calculus
, where, for example, the
quotient In arithmetic Arithmetic (from the Ancient Greek, Greek wikt:en:ἀριθμός#Ancient Greek, ἀριθμός ''arithmos'', 'number' and wikt:en:τική#Ancient Greek, τική wikt:en:τέχνη#Ancient Greek, έχνη ''tiké échne' ...
of two functions is a partial function whose domain of definition cannot contain the zeros of the denominator. For this reason, in calculus, and more generally in
mathematical analysis Analysis is the branch of mathematics dealing with Limit (mathematics), limits and related theories, such as Derivative, differentiation, Integral, integration, Measure (mathematics), measure, sequences, Series (mathematics), series, and analytic ...
, a partial function is generally called simply a . In
computability theory Computability theory, also known as recursion theory, is a branch of mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. ...
, a
general recursive function In mathematical logic and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense. If the function ...
is a partial function from the integers to the integers; for many of them no
algorithm In and , an algorithm () is a finite sequence of , computer-implementable instructions, typically to solve a class of problems or to perform a computation. Algorithms are always and are used as specifications for performing s, , , and other ...

algorithm
can exist for deciding whether they are in fact total. When arrow notation is used for functions, a partial function f from X to Y is sometimes written as f : X \rightharpoonup Y, , f : X \nrightarrow Y, or f : X \hookrightarrow Y. However, there is no general convention, and the latter notation is more commonly used for
injective function In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

injective function
s.. Specifically, for a partial function f : X \rightharpoonup Y, and any x \in X, one has either: * f(x) = y \in Y (it is a single element in ), or * f(x) is undefined. For example, if f is the
square root In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities ...

square root
function restricted to the
integer An integer (from the Latin Latin (, or , ) is a classical language A classical language is a language A language is a structured system of communication Communication (from Latin ''communicare'', meaning "to share" or "to ...
s : f : \Z \to \N, defined by: : f(n) = m if, and only if, m^2 = n, m \in \N, n \in \Z, then f(n) is only defined if n is a perfect square (that is, 0, 1, 4, 9, 16, \ldots). So f(25) = 5 but f(26) is undefined.


Basic concepts

A partial function is said to be
injective In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

injective
,
surjective In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...

surjective
, or
bijective In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

bijective
when the function given by the restriction of the partial function to its domain of definition is injective, surjective, bijective respectively. Because a function is trivially surjective when restricted to its image, the term
partial bijection In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
denotes a partial function which is injective. 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 an injective partial function. The notion of
transformation Transformation may refer to: Science and mathematics In biology and medicine * Metamorphosis, the biological process of changing physical form after birth or hatching * Malignant transformation, the process of cells becoming cancerous * Trans ...
can be generalized to partial functions as well. A partial transformation is a function f : A \rightharpoonup B, where both A and B are
subset In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...

subset
s of some set X.


Function

A
function Function or functionality may refer to: Computing * Function key A function key is a key on a computer A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations automatically. Modern comp ...
is a binary relation that is
functional Functional may refer to: * Movements in architecture: ** Functionalism (architecture) In architecture File:Plan d'exécution du second étage de l'hôtel de Brionne (dessin) De Cotte 2503c – Gallica 2011 (adjusted).jpg, upright=1.45, alt=Pl ...
(also called right-unique) and
serial Serial may refer to: Arts, entertainment, and media The presentation of works in sequential segments * Serial (literature), serialised fiction in print * Serial (publishing), periodical publications and newspapers * Serial (radio and television), ...
(also called left-total). This is a stronger definition than that of a partial function which only requires the functional property.


Function spaces

The set of all partial functions f : X \rightharpoonup Y from a set X to a set Y, denoted by \rightharpoonup Y is the union of all functions defined on subsets of X with same codomain Y: : \rightharpoonup Y= \bigcup_ \to Y the latter also written as \bigcup_ Y^D. In finite case, its cardinality is : , \rightharpoonup Y = (, Y, + 1)^, 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 \, 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 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

Consider the
natural logarithm The natural logarithm of a number is its logarithm In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained ( ...
function mapping the
real number In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no g ...
s 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 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 In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and the ...
(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 mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and total order, ordering (as in "this is the ''third'' largest city in the country"). In common mathematical terminology, w ...

natural numbers
(non-negative
integers An integer (from the Latin Latin (, or , ) is a classical language belonging to the Italic languages, Italic branch of the Indo-European languages. Latin was originally spoken in the area around Rome, known as Latium. Through the power ...

integers
) can be viewed as a partial function: : f : \N \times \N \rightharpoonup \N : f(x,y) = x - y. It is defined only when x \geq y.


Bottom element

In
denotational semantics In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of compu ...
a partial function is considered as returning the
bottom element In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S that is greater than every other element of S. The term least element is defined duality (order theory), dually, ...
when it is undefined. In
computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , , and . Computer science ...
a partial function corresponds to a subroutine that raises an exception or loops forever. The
IEEE floating point The IEEE Standard for Floating-Point Arithmetic (IEEE 754) is a technical standard A technical standard is an established norm (social), norm or requirement for a repeatable technical task which is applied to a common and repeated use of rules, ...
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 A programming language is a formal language In logic, mathematics, computer science, and linguistics, a formal language consists of string (computer science), words whose symbol (formal), letters are taken from an alphabet (computer science) ...

programming language
where function parameters are
statically typed In programming language A programming language is a formal language In logic, mathematics, computer science, and linguistics, a formal language consists of string (computer science), words whose symbol (formal), letters are taken from a ...
, a function may be defined as a partial function because the language's
type system In programming language A programming language is a formal language In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra) ...
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 Category theory formalizes mathematical structure In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and ...
, when considering the operation of
morphism In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...

morphism
composition in concrete categories, the composition operation \circ \;:\; \hom(C) \times \hom(C) \to \hom(C) is a function if and only if \operatorname(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 Equivalence or Equivalent may refer to: Arts and entertainment *Album-equivalent unit, a measurement unit in the music industry *Equivalence class (music) *''Equivalent VIII'', or ''The Bricks'', a minimalist sculpture by Carl Andre *''Equivalent ...
to but not
isomorphic In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
with the category of
pointed set In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
s and point-preserving maps. 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 compactificationIn the mathematical field of topology s, which have only one surface and one edge, are a kind of object studied in topology. In mathematics, topology (from the Greek language, Greek words , and ) is concerned with the properties of a mathematic ...
) and in
theoretical computer science Theoretical computer science (TCS) is a subset of general computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for the ...

theoretical computer science
." The category of sets and partial bijections is equivalent to its
dual Dual or Duals may refer to: Paired/two things * Dual (mathematics), a notion of paired concepts that mirror one another ** Dual (category theory), a formalization of mathematical duality *** see more cases in :Duality theories * Dual (grammatical ...
. It is the prototypical inverse category.


In abstract algebra

Partial algebra In abstract algebra In algebra, which is a broad division of mathematics, abstract algebra (occasionally called modern algebra) is the study of algebraic structures. Algebraic structures include group (mathematics), groups, ring (mathematics), r ...
generalizes the notion of
universal algebra Universal algebra (sometimes called general algebra) is the field of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spa ...
to partial
operations Operation or Operations may refer to: Science and technology * Surgical operation Surgery ''cheirourgikē'' (composed of χείρ, "hand", and ἔργον, "work"), via la, chirurgiae, meaning "hand work". is a medical or dental specialty that ...
. An example would be a
field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grassl ...
, in which the multiplicative inversion is the only proper partial operation (because
division by zero In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...
is not defined). The set of all partial functions (partial
transformation Transformation may refer to: Science and mathematics In biology and medicine * Metamorphosis, the biological process of changing physical form after birth or hatching * Malignant transformation, the process of cells becoming cancerous * Trans ...
s) on a given base set, X, forms a
regular semigroup In mathematics, a regular semigroup is a semigroup In mathematics, a semigroup is an algebraic structure consisting of a Set (mathematics), set together with an associative binary operation. The binary operation of a semigroup is most often denote ...
called the semigroup of all partial transformations (or the partial transformation semigroup on X), typically denoted by \mathcal_X. The set of all partial bijections on X forms the
symmetric inverse semigroup __NOTOC__ In abstract algebra In algebra, which is a broad division of mathematics, abstract algebra (occasionally called modern algebra) is the study of algebraic structures. Algebraic structures include group (mathematics), groups, ring (mathe ...
.


Charts and atlases for manifolds and fiber bundles

Charts in the
atlases An atlas is a collection of map A map is a symbol A symbol is a mark, sign, or that indicates, signifies, or is understood as representing an , , or . Symbols allow people to go beyond what is n or seen by creating linkages betw ...
which specify the structure of
manifold In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...

manifold
s and
fiber bundle In mathematics, and particularly topology, a fiber bundle (or, in English in the Commonwealth of Nations, Commonwealth English: fibre bundle) is a Space (mathematics), space that is ''locally'' a product space, but ''globally'' may have a dif ...
s 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 In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
, 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.


See also

* * *


References

*
Martin Davis Martin Davis may refer to: * Martin Davis (Australian footballer) (born 1936), Australian rules footballer * Martin Davis (Jamaican footballer) (born 1996), Jamaican footballer * Martin Davis (mathematician) Martin David Davis (born March 8, 1 ...
(1958), ''Computability and Unsolvability'', McGraw–Hill Book Company, Inc, New York. Republished by Dover in 1982. . *
Stephen Kleene Stephen Cole Kleene ( ; January 5, 1909 – January 25, 1994) was an American mathematician. One of the students of Alonzo Church, Kleene, along with Rózsa Péter, Alan Turing, Emil Post, and others, is best known as a founder of the branch of m ...
(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. Mathematical relations Functions and mappings