# nLab partial function

Partial functions

# Partial functions

## Idea

A partial function $f: A \to B$ is like a function from $A$ to $B$ except that $f(x)$ may not be defined for every element $x$ of $A$. (Compare a multi-valued function, where $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 $A$ and $B$, a partial function $f$ from $A$ to $B$ consists a subset $D$ of $A$ and a (total) function from $D$ to $B$. In more detail, this is a span

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

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

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

Notice that the induced function $D \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 $D$ to be literally a subset of $A$ (with $\iota$ the inclusion map).

### General abstract

#### In terms of spans

If $C$ is a category with pullbacks, then a partial map from $a$ to $b$ may be defined to be a span

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

where $i$ is monic. Such spans are closed under span composition, and as a locally full sub-2-category of $Span(C)$, the bicategory of partial maps in $C$ is locally preordered. In more down-to-earth terms, if $(i, f)$ and $(i', f')$ are partial maps from $a$ to $b$, we have $(i, f) \leq (i', f')$ if there exists (necessarily monic) $j$ such that $i = i' \circ j$ and $f = 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 $f$ from $A$ to $B$ as above is (in classical mathematics) equivalently a genuine function from $A$ to the disjoint union (coproduct) of $B$ with the point (the singleton)

$\phi \;\colon\; A \longrightarrow B \coprod \ast \,.$

The subset $D \hookrightarrow A$ in the above is the preimage $\phi^*(B)$; for $x$ in this preimage, $f(x) = \phi(x)$. Conversely, an element $x \in A$ is sent to $\ast$ by $\phi$ if and only if $f$ is undefined at $x$.

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 $D$).

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: 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 $R \to R$ is also a function $R \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/ (\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 $Top$, 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 $\sqrt {x-a} - \sqrt{x-a}$, $\log(a-x) - \log(a-x)$, etc, but that's silly.) So calculus is about (certain) functions to $\mathbf{R}$ from unions of intervals on $\mathbf{R}$. Of course, this doesn't include all partial functions on $\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_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 $S$ with the set $S_\bot$ of all subsets of $S$ with at most one element, otherwise known as the partial map classifier of Set. In this context, we identify an element $x$ of $S$ with the subset $\{x\}$ and write the empty subset as $\bot$. Then a partial function $S \to T$ becomes a total function $S_\bot \to T_\bot$ such that inhabited subsets of $T$ are assigned only to inhabited subsets of $S$. Then $Set_part$ is equivalent to the category $Set_\bot$ of such sets and functions.

In classical mathematics $S_\bot \cong S \amalg \{\bot\}$, although this is not true constructively. In this case, $S\mapsto S \amalg \{\bot\}$ is the maybe monad and $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_*$ of pointed sets and total point-preserving functions. Traditionally, one uses the notation of $Set_\bot$ but (unless one is a constructivist) thinks of this as simply different notation for $Set_*$. It is still true constructively that $S\mapsto S_\bot$ is a monad (the partial map classifier) and $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_\bot$. In particular, $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_\bot \cong S \amalg \{\bot\}$?

Toby writes: We have the map $S \amalg \{\bot\} \to S_\bot$; map $x$ to $\{x\}$ and $\bot$ to $\emptyset$. Suppose that this map is surjective. That's fine for some $S$, but suppose that $S$ is inhabited, with an element $a$. Let $P$ be any proposition, and form the subset $\{x | P\}$ of $S$, defined so that $a \in \{x | P\}$ iff $a = x$ and $P$ is true. This subset has at most one element, so it is (by hypothesis) in the image of the map $S \amalg \{\bot\} \to S_\bot$. If its preimage is in $S$, then $P$ is true; if its preimage is in $\{\bot\}$, then $P$ is false. Since $P$ 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_\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.

## Algebras of partial functions

The functions of high-school mathematics, consisting of real (or complex)-valued functions of one (or two or three) real (or complex) variables, are by default partial functions. As they take values in a field, one may consider adding or multiplying them. The usual rule is that $\dom(f + g) = \dom f \cap \dom g$, etc, but this leads to an unusual algebra: a commutative semiring in which addition has an identity element (the always-defined constant zero function) and multiplication has an absorbing element (the never-defined empty function), but it fails to be a rig because these two elements are not the same. It has many other interesting properties, such as simultaneous additive and multiplicative idempotents (the zero functions with arbitrary domains).

An axiomatic treatment of such semirings may be found at the end of Richman 2010, as well as in the article category of partial endofunctions.