nLab
partial function

Partial functions

Idea

A partial function f:ABf: A \to B is like a function from AA to BB except that f(x)f(x) may not be defined for every element xx of AA. (Compare a multi-valued function, where f(x)f(x) may have several possible values.)

In some fields (including secondary-school mathematics even today), functions are often considered to be partial by default, requiring one to specify a total function otherwise. As category-theoretic and type-theoretic formalisation spreads, this is difficult to treat as the basic concept, and the most modern idea is that a function must be total. If you want partial functions, then you can get them in terms of total functions as below.

Definitions

In sets

Given sets AA and BB, a partial function ff from AA to BB consists a subset DD of AA and a (total) function from DD to BB. In more detail, this is a span

D ι f A B \array { & & D \\ & \swarrow_\iota & & \searrow^f \\ A & & & & B \\ }

of total functions, where ι:DA\iota: D \to A is an injection. (This condition can be dropped to define a partial multi-valued function, which is simply a span.)

AA and BB are called the source and target of ff as usual; then DD is the domain of ff and ι:DA\iota: D \to A is the inclusion of the domain into the source. By abuse of notation, the partial function ff is conflated with the (total) function f:DBf: D \to B.

Notice that the induced function DA×BD \to A \times B is an injection, so a partial function is the same as a functional relation seen from a different point of view.

We consider two partial functions (with the same given source and target) to be equal if there is a bijection between their domains that makes the obvious diagrams commute. You can get this automatically in a traditional set theory by requiring DD to be literally a subset of AA (with ι\iota the inclusion map).

General abstract

In terms of spans

If CC is a category with pullbacks, then a partial map from aa to bb may be defined to be a span

D i f A B\array{ & & D & & \\ & ^\mathllap{i} \swarrow & & \searrow^\mathrlap{f} & \\ A & & & & B }

where ii is monic. Such spans are closed under span composition, and as a locally full subbicategory of Span(C)Span(C), the bicategory of partial maps in CC is locally preordered. In more down-to-earth terms, if (i,f)(i, f) and (i,f)(i', f') are partial maps from aa to bb, we have (i,f)(i,f)(i, f) \leq (i', f') if there exists (necessarily monic) jj such that i=iji = i' \circ j and f=fjf = f' \circ j.

Abstract bicategories of partial maps, parallel to bicategories of relations, were introduced by (Carboni 87).

In terms of the maybe monad

Notice that a partial function from AA to BB as above is equivalently a genuine function from AA to the disjoint union (coproduct) of BB with the point (the singleton)

ϕ:AB*. \phi \;\colon\; A \longrightarrow B \coprod \ast \,.

(The subset DAD \hookrightarrow A in the above is identified with the set of all elements that are sent to the point by ϕ\phi.)

This in turn is equivalently a morphism in the Kleisli category of the maybe monad. Phrased this way, the concept of partial function makes sense in any category with coproducts and with a terminal object. It comes out as intended when the category is an extensive category (partial functions with complemented domain).

Examples

In secondary-school mathematics, one often makes functions partial by fiat, just to see if students can calculate the domains of composite functions and the like. This is not (only) busywork, as in applications one often has a function given by a formula that is really valid only on a certain domain. However, in more sophisticated analyses (such as those that Lawvere and his followers propose for physics and synthetic geometry), these domains and the total functions on them become the primary objects of study, with the partial functions being secondary (as ι\iota is seen as merely a way to place coordinates on DD).

In analysis, one often considers partial functions whose domains are required to be intervals in the real line, regions of the complex plane, or dense subsets of a Banach space.

Ronnie There is an interesting debate possible here!

On the basis of my teaching of first year analysis and calculus since 1959, I found the most convenient idea is that of a function f:RRf: R \to R being a partial function with a domain which can be calculated from a formula for the function, and may be empty. Then one finds that the inverse of an injective function RRR \to R is also a function RRR \to R. A first order differential equation has a solution which is a partial function. What seems to be lacking is the functional analysis of such solutions. For example dy/dx=1/(λ+x)dy/dx=1/ (\lambda +x) has a solution whose domain varies with λ\lambda and ought to (and can be made to) vary continuously, including its open domain!

The work of Charles Ehresmann is full of partial functions, derived from his strong interest in analysis and differential geometry, and local-to-global problems. So he developed for example the theory of pseudogroups, and contributed to inverse semigroups.

A possible reason for the difficulties some have of accepting groupoids rather than groups is that groupoids have a partial composition, which is of course very intuitive when one thinks of composing journeys.

In higher dimensional algebra one is dealing with algebraic structures whose domains are defined by geometric conditions.

Of course category theory initially derived from algebra and algebraic topology, where partial functions are unusual. However they are necessary in dealing with fibred exponential laws, i.e. exponential laws in a slice category of TopTop, and their applications. See papers of Peter Booth.

Toby: For first-year calculus, I agree with you, except that you ought to be able to restrict the definition to an interval (or a union of intervals) by fiat. (Actually, you can get this from formulas by adding appropriate terms of the form xaxa\sqrt {x-a} - \sqrt{x-a}, log(ax)log(ax)\log(a-x) - \log(a-x), etc, but that's silly.) So calculus is about (certain) functions to R\mathbf{R} from unions of intervals on R\mathbf{R}. Of course, this doesn't include all partial functions on R\mathbf{R}, but then it doesn't even include all such total functions, so maybe the restriction on allowed domains doesn't matter.

But if you disagree that ‘in more sophisticated analyses [], these domains and the total functions on them become the primary objects of study’, then feel free to change the text (say to ‘in other analyses []’; I don't intend to defend the claim that this is really the right way to do things.

In a field, the multiplicative inverse is a partial function whose domain is the set of non-zero elements of the field.

The category of sets and partial functions

The category Set partSet_part of sets and partial functions between them is important for understanding computation. However, one often replaces this with an equivalent category of sets and total functions.

Specifically, replace each set SS with the set S S_\bot of all subsets of SS with at most one element, otherwise known as the partial map classifier of Set. In this context, we identify an element xx of SS with the subset {x}\{x\} and write the empty subset as \bot. Then a partial function STS \to T becomes a total function S T S_\bot \to T_\bot such that inhabited subsets of TT are assigned only to inhabited subsets of SS. Then Set partSet_part is equivalent to the category Set Set_\bot of such sets and functions.

In classical mathematics S S⨿{}S_\bot \cong S \amalg \{\bot\}, although this is not true constructively. In this case, SS⨿{}S\mapsto S \amalg \{\bot\} is the maybe monad and Set Set_\bot is its Kleisli category. Moreover, since every algebra for this monad is free? this category is also equivalent to its Eilenberg-Moore category, which is the category Set *Set_* of pointed sets and total point-preserving functions. Traditionally, one uses the notation of Set Set_\bot but (unless one is a constructivist) thinks of this as simply different notation for Set *Set_*. It is still true constructively that SS S\mapsto S_\bot is a monad (the partial map classifier) and Set Set_\bot is its Kleisli category, but it is (probably) no longer true that every algebra is free.

Emily Riehl I don’t understand how I am supposed to think about Set Set_\bot. In particular, Set Set_\bot is isomorphic to get category of based sets and basepoint preserving functions, which seems both easier to describe and easier to think about.

Also what is non-constructive about the bijection S S⨿{}S_\bot \cong S \amalg \{\bot\}?

Toby writes: We have the map S⨿{}S S \amalg \{\bot\} \to S_\bot; map xx to {x}\{x\} and \bot to \emptyset. Suppose that this map is surjective. That's fine for some SS, but suppose that SS is inhabited, with an element aa. Let PP be any proposition, and form the subset {x|P}\{x | P\} of SS, defined so that a{x|P}a \in \{x | P\} iff a=xa = x and PP is true. This subset has at most one element, so it is (by hypothesis) in the image of the map S⨿{}S S \amalg \{\bot\} \to S_\bot. If its preimage is in SS, then PP is true; if its preimage is in {}\{\bot\}, then PP is false. Since PP could be any proposition, excluded middle follows; this is nonconstructive.

This is all yet different from the category of pointed sets.

For a more sophisticated analysis of computation, Set Set_\bot can be replaced with a suitable category of domains, such as directed complete partially ordered sets (DCPOs). The requirement that \bot be preserved can then be removed to model lazy computation, but now we are hardly talking about partial functions anymore.

References

Revised on February 24, 2014 10:40:41 by Mike Shulman (192.195.154.58)