In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a partial function from a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
to a set is a function from a
subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
of (possibly itself) to . The subset , that is, the
domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
**Domain of definition of a partial function
**Natural domain of a partial function
**Domain of holomorphy of a function
* Do ...
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
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
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 type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
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 mathematical study of continuous change, in the same way that geometry is the study of shape, and algebra is the study of generalizations of arithm ...
, where, for example, the
quotient
In arithmetic, a quotient (from lat, quotiens 'how many times', pronounced ) is a quantity produced by the division of two numbers. The quotient has widespread use throughout mathematics, and is commonly referred to as the integer part of a ...
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 continuous functions, limit (mathematics), limits, and related theories, such as Derivative, differentiation, Integral, integration, measure (mathematics), measure, infinite sequences, series (m ...
, a partial function is generally called simply a . In
computability theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since e ...
, 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 – as well as i ...
is a partial function from the integers to the integers; no
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
can exist for deciding whether an arbitrary such function is in fact total.
When
arrow notation is used for functions, a partial function
from
to
is sometimes written as
or
However, there is no general convention, and the latter notation is more commonly used for
inclusion map
In mathematics, if A is a subset of B, then the inclusion map (also inclusion function, insertion, or canonical injection) is the function \iota that sends each element x of A to x, treated as an element of B:
\iota : A\rightarrow B, \qquad \iot ...
s or
embedding
In mathematics, an embedding (or imbedding) is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup.
When some object X is said to be embedded in another object Y, the embedding is gi ...
s.
Specifically, for a partial function
and any
one has either:
*
(it is a single element in ), or
*
is undefined.
For example, if
is the
square root
In mathematics, a square root of a number is a number such that ; in other words, a number whose ''square'' (the result of multiplying the number by itself, or ⋅ ) is . For example, 4 and −4 are square roots of 16, because .
E ...
function restricted to the
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s
:
defined by:
:
if, and only if,
then
is only defined if
is a
perfect square
''Perfect Square'' is a 2004 concert film of the alternative rock Musical ensemble, band R.E.M. (band), R.E.M., filmed on July 19, 2003, at the bowling green, Bowling Green in Wiesbaden, Germany. It was released by Warner Reprise Video on March 9, ...
(that is,
). So
but
is undefined.
Basic concepts
A partial function arises from the consideration of maps between two sets and that may not be defined on the entire set . A common example is the square root operation on the real numbers
: because negative real numbers do not have real square roots, the operation can be viewed as a partial function from
to
The ''domain of definition'' of a partial function is the subset of on which the partial function is defined; in this case, the partial function may also be viewed as a function from to . In the example of the square root operation, the set consists of the nonnegative real numbers
The notion of partial function is particularly convenient when the exact domain of definition is unknown or even unknowable. For a computer-science example of the latter, see ''Halting problem''.
In case the domain of definition is equal to the whole set , the partial function is said to be ''total''. Thus, total partial functions from to coincide with functions from to .
Many properties of functions can be extended in an appropriate sense of partial functions. A partial function is said to be
injective
In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositiv ...
,
surjective
In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of i ...
, or
bijective
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
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, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
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
where both
and
are
subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
s of some set
Function spaces
For convenience, denote the set of all partial functions
from a set
to a set
by
This set is the union of the sets of functions defined on subsets of
with same codomain
:
:
the latter also written as
In finite case, its cardinality is
:
because any partial function can be extended to a function by any fixed value
not contained in
so that the codomain is
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 to the base of the mathematical constant , which is an irrational and transcendental number approximately equal to . The natural logarithm of is generally written as , , or sometimes, if ...
function mapping the
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
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, the set of positive real numbers, \R_ = \left\, is the subset of those real numbers that are greater than zero. The non-negative real numbers, \R_ = \left\, also include zero. Although the symbols \R_ and \R^ are ambiguously used fo ...
(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 ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal n ...
(non-negative
integers
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language o ...
) can be viewed as a partial function:
:
:
It is defined only when
Bottom element
In
denotational semantics
In computer science, denotational semantics (initially known as mathematical semantics or Scott–Strachey semantics) is an approach of formalizing the meanings of programming languages by constructing mathematical objects (called ''denotations'' ...
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 dually, that is, it is an eleme ...
when it is undefined.
In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
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 for floating-point arithmetic established in 1985 by the Institute of Electrical and Electronics Engineers (IEEE). The standard addressed many problems found in ...
standard defines a
not-a-number
Nan or NAN may refer to:
Places China
* Nan County, Yiyang, Hunan, China
* Nan Commandery, historical commandery in Hubei, China
Thailand
* Nan Province
** Nan, Thailand, the administrative capital of Nan Province
* Nan River
People Given name ...
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 system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
where function parameters are
statically typed
In computer programming, a type system is a logical system comprising a set of rules that assigns a property called a type to every "term" (a word, phrase, or other set of symbols). Usually the terms are various constructs of a computer progra ...
, a function may be defined as a partial function because the language's
type system
In computer programming, a type system is a logical system comprising a set of rules that assigns a property called a type to every "term" (a word, phrase, or other set of symbols). Usually the terms are various constructs of a computer progra ...
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 is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, cate ...
, when considering the operation of
morphism
In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms a ...
composition in
concrete categories
In mathematics, a concrete category is a category that is equipped with a faithful functor to the category of sets (or sometimes to another category, ''see Relative concreteness below''). This functor makes it possible to think of the objects of t ...
, the composition operation
is a 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
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
*''Equivale ...
to but not
isomorphic
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
with the category of
pointed set
In mathematics, a pointed set (also based set or rooted set) is an ordered pair (X, x_0) where X is a set and x_0 is an element of X called the base point, also spelled basepoint.
Maps between pointed sets (X, x_0) and (Y, y_0) – called based ma ...
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 compactification In the mathematical field of topology, the Alexandroff extension is a way to extend a noncompact topological space by adjoining a single point in such a way that the resulting space is compact. It is named after the Russian mathematician Pavel Ale ...
) and in
theoretical computer science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumsc ...
."
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, a partial algebra is a generalization of universal algebra to partial operations.
Example(s)
* partial groupoid
* field
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultu ...
generalizes the notion of
universal algebra
Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures.
For instance, rather than take particular groups as the object of study, ...
to partial
operations. 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 grass ...
, in which the multiplicative inversion is the only proper partial operation (because
division by zero
In mathematics, division by zero is division (mathematics), division where the divisor (denominator) is 0, zero. Such a division can be formally expression (mathematics), expressed as \tfrac, where is the dividend (numerator). In ordinary ari ...
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,
forms a
regular semigroup In mathematics, a regular semigroup is a semigroup ''S'' in which every element is regular, i.e., for each element ''a'' in ''S'' there exists an element ''x'' in ''S'' such that . Regular semigroups are one of the most-studied classes of semigroup ...
called the semigroup of all partial transformations (or the partial transformation semigroup on
), typically denoted by
The set of all partial bijections on
forms the
symmetric inverse semigroup __NOTOC__
In abstract algebra, the set of all partial bijections on a set ''X'' ( one-to-one partial transformations) forms an inverse semigroup, called the symmetric inverse semigroup (actually a monoid) on ''X''. The conventional notation for the ...
.
Charts and atlases for manifolds and fiber bundles
Charts in the
atlases
An atlas is a collection of maps; it is typically a bundle of maps of Earth or of a region of Earth.
Atlases have traditionally been bound into book form, but today many atlases are in multimedia formats. In addition to presenting geographic ...
which specify the structure of
manifold
In mathematics, a manifold is a topological space that locally resembles Euclidean space near each point. More precisely, an n-dimensional manifold, or ''n-manifold'' for short, is a topological space with the property that each point has a n ...
s and
fiber bundle
In mathematics, and particularly topology, a fiber bundle (or, in Commonwealth English: fibre bundle) is a space that is a product space, but may have a different topological structure. Specifically, the similarity between a space E and a p ...
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, particularly topology, one describes a manifold using an atlas. An atlas consists of individual ''charts'' that, roughly speaking, describe individual regions of the manifold. If the manifold is the surface of the Earth, then an a ...
, 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 (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 ...
(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