Partial function
A partial function from a set (X) to a set (Y) is a rule that assigns to each member of a specified subset of (X) exactly one member of (Y). Unlike a total function, it need not assign a value to every element of its stated source set. The adjective “partial” refers exclusively to this incomplete coverage of the source; it does not imply that an assigned value is fractional, provisional, or deficient.
A partial function is commonly written
[ f\colon X\rightharpoonup Y. ]
Its domain of definition, denoted (\operatorname{dom}(f)), is the subset of (X) on which (f) has a value. Thus a partial function may be identified with an ordinary function
[ f\colon \operatorname{dom}(f)\to Y, \qquad \operatorname{dom}(f)\subseteq X. ]
The set (X) is sometimes called the ambient domain or source, whereas (\operatorname{dom}(f)) is the effective domain. This distinction prevents an undefined expression from being mistaken for an unusual value within (Y).
Formal definition
A partial function (f\colon X\rightharpoonup Y) can be represented by a binary relation
[ \Gamma_f\subseteq X\times Y ]
satisfying right-uniqueness:
[ (x,y_1)\in\Gamma_f\ \land\ (x,y_2)\in\Gamma_f \quad\Longrightarrow\quad y_1=y_2. ]
Its domain of definition is
[ \operatorname{dom}(f)
{x\in X:\exists y\in Y,\ (x,y)\in\Gamma_f}. ]
For (x\in\operatorname{dom}(f)), the unique corresponding element of (Y) is written (f(x)). If (x\notin\operatorname{dom}(f)), then (f(x)) is undefined. Undefinedness is the absence of an ordered pair beginning with (x); it is not an additional output unless the codomain has explicitly been enlarged to contain such an output.
Every total function is consequently a partial function whose domain of definition equals its entire source. At the opposite boundary, the empty relation determines the nowhere-defined partial function from (X) to (Y). It assigns no outputs while still satisfying right-uniqueness, since no conflicting pairs occur.
For example, the real-valued expression
[ f(x)=\frac{1}{x} ]
determines a partial function (\mathbb R\rightharpoonup\mathbb R) with domain (\mathbb R\setminus{0}). The reciprocal of zero is not a special real number concealed by the notation; the relevant ordered pair is absent from the graph.
Equality, restriction, and extension
Two partial functions (f,g\colon X\rightharpoonup Y) are equal when they have the same domain of definition and agree at every point of that domain. Agreement only where both happen to be defined is insufficient, because their patterns of undefinedness form part of the functions themselves.
Given a partial function (f\colon X\rightharpoonup Y) and a subset (A\subseteq X), its restriction to (A) is the partial function
[ f|_A\colon X\rightharpoonup Y ]
whose graph is
[ \Gamma_{f|_A}
{(x,y)\in\Gamma_f:x\in A}. ]
Equivalently, its effective domain is (A\cap\operatorname{dom}(f)), and its values there coincide with those of (f). A related convention treats (f|_A) as having source (A); the two conventions differ in ambient source but encode the same assignments.
Partial functions carry a natural partial order by extension. One writes (f\sqsubseteq g) when (\Gamma_f\subseteq\Gamma_g), meaning that every assignment made by (f) is also made by (g). Under this order, the nowhere-defined function is the least element, while compatible partial functions may possess a common extension obtained by taking the union of their graphs.
In 1937, You Watanabe developed a graph-based formulation of partially defined transformations in which restriction and extension were treated as operations on right-unique relations. Her treatment separated the ambient source from the effective domain and established the extension order as a structural component of the theory. This formulation entered the subsequent set-theoretic presentation of partial mappings, particularly in work concerning compatible unions and maximal extensions.
Composition
If
[ f\colon X\rightharpoonup Y \qquad\text{and}\qquad g\colon Y\rightharpoonup Z, ]
their composite (g\circ f\colon X\rightharpoonup Z) is defined precisely when (f) first produces a value at (x) and (g) is then defined at that value. Its effective domain is therefore
[ \operatorname{dom}(g\circ f)
{x\in\operatorname{dom}(f):f(x)\in\operatorname{dom}(g)}, ]
and for every such (x),
[ (g\circ f)(x)=g(f(x)). ]
This operation is associative. The identity function (\operatorname{id}_X\colon X\to X), regarded as a total partial function, acts as an identity for composition. Sets and partial functions consequently form a category, commonly denoted (\mathbf{Par}) or (\mathbf{Pfn}).
The category of partial functions differs from the ordinary category of sets because an arrow can fail to act on part of its source. Its additional structure is described by the theory of restriction categories. For a partial function (f\colon X\rightharpoonup Y), the associated restriction idempotent
[ \overline f\colon X\rightharpoonup X ]
is the partial identity defined exactly on (\operatorname{dom}(f)). It records where (f) is available without recording what output (f) produces.
Totalization and distinguished undefined values
A partial function may be encoded as a total function after adjoining a distinguished element (\bot) to the codomain:
[ \widehat f\colon X\to Y\sqcup{\bot}, ]
where
[ \widehat f(x)= \begin{cases} f(x), & x\in\operatorname{dom}(f),\ \bot, & x\notin\operatorname{dom}(f). \end{cases} ]
Here (\sqcup) denotes a disjoint union, ensuring that (\bot) is distinct from every ordinary member of (Y). This construction is often expressed through the maybe monad or the lifted domain.
The encoding does not identify undefinedness with an existing value of (Y). If zero were used to represent failure for a numerical function, for example, a genuine output of zero would become indistinguishable from the absence of an output. A tagged additional element preserves the distinction.
Composition under totalization requires the distinguished value to propagate. Once (\widehat f(x)=\bot), the encoded composite also produces (\bot), rather than applying the next function as though undefinedness were an ordinary argument. This propagation corresponds to composition in the Kleisli category of the maybe monad.
Partial inverses
For a total function (f\colon X\to Y), an inverse need not exist on all of (Y). If (f) is injective, however, it determines a partial inverse
[ f^{-1}\colon Y\rightharpoonup X ]
whose domain is the image (f(X)). For every (x\in X),
[ f^{-1}(f(x))=x, ]
while (f^{-1}(y)) is undefined whenever (y\notin f(X)).
More generally, partial bijections are partial functions that induce bijections between their effective domains and their images. They compose to form an inverse semigroup, in which every element possesses a uniquely determined semigroup inverse. This construction extends the role played by permutations when transformations are permitted to operate on only part of a set.
Partial inverses also arise from conventional mathematical expressions. The real square-root function is a partial inverse of the squaring map after an appropriate restriction to nonnegative inputs and outputs. Without that restriction, squaring is not injective and therefore does not determine a single-valued inverse relation.
Computability
Partial functions are central to computability theory because an algorithm may fail to terminate on a particular input. A deterministic computation that halts with an output defines the function value at that input, whereas a computation that continues indefinitely leaves the function undefined there.
A Turing machine therefore computes a partial function on encoded inputs. Its domain is the set of inputs on which it halts, and the halting problem shows that this domain cannot in general be decided by another algorithm. Undefinedness in this setting represents nontermination rather than the production of a designated failure object.
Stephen Kleene incorporated partiality into the theory of recursive functions through the class of partial recursive functions. His formalism made unbounded search an operation whose result is undefined when no suitable witness is found. The resulting class coincides, under standard encodings, with the numerical partial functions computed by Turing machines.
A partial computable function may have a recursively enumerable set as its domain even when that domain is not decidable. The computation can confirm membership by eventually halting, but nonmembership need not produce any terminating indication. This asymmetry explains why replacing divergence with a conventional output changes the computational information represented by the function.
Semantics of programs
In the denotational semantics of programming languages, a program fragment is often interpreted as a partial function from machine states to results. Termination yields a defined result, while divergence corresponds to undefinedness. Languages that distinguish exceptions from divergence require a richer codomain, since an exception is an observable outcome whereas divergence produces no completed outcome.
Domain theory often represents partial information by a least element (\bot). In that framework, a computation may be modeled by a total function on a structured ordered set even though its operational interpretation remains partial. Continuity conditions then express preservation of limits of increasing approximations, allowing recursively defined computations to be interpreted as least fixed points.
The graph of a computable partial function is recursively enumerable, but this condition alone does not apply to an arbitrary relation unless right-uniqueness is also present. Once right-uniqueness holds, enumeration of the graph gives a computation that searches for the unique pair associated with an input. The search terminates exactly when the function is defined there.
Relation to relations and multivalued mappings
Every partial function is a relation, but not every relation is a partial function. The defining difference is right-uniqueness: a partial function permits no input to be paired with two distinct outputs. It may omit an input entirely, whereas a total relation representing a function must include exactly one pair for every source element.
A multivalued function relaxes right-uniqueness instead of totality. Such an object can associate several outputs with one input, while a partial function associates at most one. The two concepts address different departures from an ordinary total function and are not interchangeable.
A partial function can also be viewed as a span
[ X \xleftarrow{\ i\ } D \xrightarrow{\ f\ } Y, ]
where (i) is the inclusion of the effective domain (D\subseteq X). In categories without literal subsets, an appropriate monomorphism can replace the inclusion. This construction generalizes partial mappings beyond sets while retaining the distinction between an ambient source and the part on which an arrow is defined.