Universal properties and Galois connections

One recurring theme throughout this series will be that of a universal property—an identity that captures an indirect means of solving a problem, by transforming that problem into a different (and hopefully simpler) domain, while still preserving all its essential properties. In particular, the original problem has a solution if and only if the transformed problem does, and moreover, the solution to the transformed problem can easily be translated back into a solution to the original problem. One can see universal properties as a generalization of the notion of a Galois connection between two orderings, which are a similarly powerful technique of relating problems in two different settings. (In fact, the proper generalization of Galois connections is to adjunctions, but that’s a story for next time.)

Universal properties

The universal property of the ${\mathit{fork}}$ operation for products is a representative example. Recall that ${\mathit{fork}\,(f,g) :: a \rightarrow (b,c)}$ when ${f :: a \rightarrow b}$ and ${g :: a \rightarrow c}$ ; and that ${\mathit{fst} :: (b,c) \rightarrow b}$ and ${\mathit{snd} :: (b,c) \rightarrow c}$ . Then ${\mathit{fork}}$ is completely defined by its universal property:

$\displaystyle h = \mathit{fork}\,(f,g) \quad\Leftrightarrow\quad \mathit{fst} \cdot h = f \land \mathit{snd} \cdot h = g$

This identity repays careful study.

It translates a problem in the more complex domain of products (namely, the problem of showing how some complicated expression ${h}$ can be written in terms of ${\mathit{fork}}$ ) into simpler problems (here, equations about the two projections of ${h}$ ).
It’s an equivalence. So not only do you have an implication from left to right (any ${h}$ expressible as a ${\mathit{fork}}$ satisfies the two properties on the right), you also have one from right to left (any pair of functions ${f,g}$ satisfying the two properties on the right induces a ${\mathit{fork}}$ ). In other words, ${h}$ is a solution to the equation on the left iff it is a solution on the right; not only does a solution on the right yield a construction on the left, but also the absence of solutions on the right implies the absence on the left. Or again: the equations on the right have a unique solution in ${h}$ —since any two solutions ${h,h'}$ must both be equal to the same expression on the left.
It has many useful simple consequences. You can make the left-hand side trivially true by letting ${h = \mathit{fork}\,(f,g)}$ ; then the right-hand side must also be true:

$\displaystyle \begin{array}{lcl} \mathit{fst} \cdot \mathit{fork}\,(f,g) &=& f \\ \mathit{snd} \cdot \mathit{fork}\,(f,g) &=& g \end{array}$

Symmetrically, you can make the right-hand side trivially true by letting ${f = \mathit{fst} \cdot h}$ and ${g = \mathit{snd} \cdot h}$ ; then the left-hand side must also be true:

$\displaystyle h = \mathit{fork}\,(\mathit{fst} \cdot h, \mathit{snd} \cdot h)$

If you further let ${h = \mathit{id}}$ , you conclude that every pair consists solely of its two projections, nothing more:

$\displaystyle \mathit{id} = \mathit{fork}\,(\mathit{fst}, \mathit{snd})$

In fact, the universal property of ${\mathit{fork}}$ tells you everything you need to know about ${\mathit{fork}}$ ; you might take that as one justification for the term “universal”.
It also has many useful less obvious consequences. For example, if you’re searching for an ${h}$ that acts independently on the two components of a pair— ${\mathit{fst} \cdot h = h_1 \cdot \mathit{fst}}$ and ${\mathit{snd} \cdot h = h_2 \cdot \mathit{snd}}$ —just let ${f = h_1 \cdot \mathit{fst}}$ and ${g = h_2 \cdot \mathit{snd}}$ in the universal property, and conclude

$\displaystyle h = \mathit{fork}\,(h_1\cdot\mathit{fst}, h_2\cdot\mathit{snd})$

(which we’ve written “ ${\mathit{prod}\,(h_1,h_2)}$ ” elsewhere). For another example, we can deduce a fusion law for ${\mathit{fork}}$ : for what ${f',g'}$ does the equation

$\displaystyle \mathit{fork}\,(f,g) \cdot k = \mathit{fork}\,(f',g')$

hold? This matches the left-hand side of the universal property; expanding the right-hand side yields

$\displaystyle \begin{array}{lclcl} f' &=& \mathit{fst}\cdot\mathit{fork}\,(f,g)\cdot k &=& f \cdot k \\ g' &=& \mathit{snd}\cdot\mathit{fork}\,(f,g)\cdot k &=& g \cdot k \end{array}$

Such a rich harvest from so small a seed! (In fact, we will see later that an even smaller seed suffices.)

Galois connections

We can see the same structures that occur in universal properties like that of ${\mathit{fork}}$ above also in relationships between orderings. As a very simple example, consider the problem of dividing a natural number ${n}$ by two, exactly; the universal property of a solution ${m}$ to this problem is the equivalence

$\displaystyle n / 2 = m \Leftrightarrow n = m \times 2$

That is, ${m}$ is a solution to the problem “compute ${n / 2}$ ” precisely when ${n = m \times 2}$ ; both the existence and the identification of a solution to a problem expressed in terms of division has been translated to one in terms of multiplication—which is arguably a simpler setting. Note that the universal property amounts to an equivalence

$\displaystyle f(n) = m \Leftrightarrow n = g(m)$

involving the two functions ${f = (/2)}$ and ${g = (\times 2)}$ , which are in some sense inverses. This pattern will crop up over and over again.

The division example involved an equivalence between the two identities ${f(n)=m}$ and ${n=g(m)}$ . More generally, another relation than “ ${=}$ ” might be involved. Extending the previous example to integer division, rounding down, we have for ${k>0}$ :

$\displaystyle n \div k \ge m \Leftrightarrow n \ge m \times k$

Again, this relates the two (in some sense inverse) functions ${(\div k)}$ and ${(\times k)}$ ; but this time equality is inadequate for stating the problem, and it perhaps more convincing to claim that a more complicated problem ${(\div k)}$ has been translated into a simpler one ${(\times k)}$ . What is more, translating the problem via this universal property pays dividends when it comes to reasoning about the problem, because the simpler problem space is much more amenable to calculation. For example, properties of repeated division ${(n \div k) \div l}$ (for ${k,l>0}$ ) do not trip off the tongue; but we can reason straightforwardly as follows:

$\displaystyle \begin{array}{ll} & (n \div k) \div l \ge m \\ \Leftrightarrow & \qquad \{ \mbox{universal property} \} \\ & n \div k \ge m \times l \\ \Leftrightarrow & \qquad \{ \mbox{universal property} \} \\ & n \ge (m \times l) \times k \\ \Leftrightarrow & \qquad \{ \mbox{multiplication is associative} \} \\ & n \ge m \times (l \times k) \\ \Leftrightarrow & \qquad \{ \mbox{universal property} \} \\ & n \div (l \times k) \ge m \end{array}$

Thus, ${(n \div k) \div l \ge m}$ precisely when ${n \div (l \times k) \ge m}$ , or in other words, ${(n \div k) \div l = n \div (l \times k)}$ .

In this case, the two problem spaces have both involved the same relation ${\ge}$ on the same domain, namely the natural numbers; that is not essential. For example, the universal property of the floor function ${\lfloor\cdot\rfloor}$ from reals to integers is given by:

$\displaystyle \mathit{inj}(n) \le_R x \Leftrightarrow n \le_I \lfloor x \rfloor$

where, to be completely explicit, we have written ${\le_R}$ for the usual ordering on reals and ${\le_I}$ for the corresponding ordering on integers, and ${\mathit{inj}}$ for the injection from the integers into the reals. This time the two problem spaces involve two different orderings on different domains; we say that the pair of functions ${\mathit{inj}}$ and ${\lfloor\cdot\rfloor}$ form a Galois connection between the orderings ${\le_R}$ and ${\le_I}$ . (We also see that the relationship between the two functions ${\mathit{inj}}$ and ${\lfloor\cdot\rfloor}$ is becoming less like a pure inverse relationship, and more of an embedding–projection pair.)

As a simple non-arithmetical example of a Galois connection on a single domain, consider some set ${U}$ and a fixed subset ${X \subseteq U}$ ; then

$\displaystyle A \cap X \subseteq B \Leftrightarrow A \subseteq B \cup \overline{X}$

That is, ${(\cap X)}$ and ${(\cup \overline{X})}$ form a Galois connection between ${\subseteq}$ and itself.

A non-arithmetical example between two different domains is afforded by the field of formal concept analysis, which relates “objects” and their “properties”. Given are sets ${O}$ of objects and ${P}$ of properties, and a relation ${(\vdash) \subseteq O \times P}$ ; we write ${o \mathrel{\vdash} p}$ to denote that object ${o}$ has property ${p}$ . This induces “concept-forming operators” ${\mathit{intent} : 2^O \rightarrow 2^P}$ and ${\mathit{extent} : 2^P \rightarrow 2^O}$ defined by:

$\displaystyle \begin{array}{lcl} \mathit{intent}(E) &=& \{ p \in P \mid \forall o \in E .\; o \mathrel{\vdash} p \} \\ \mathit{extent}(I) &=& \{ o \in O \mid \forall p \in I .\; o \mathrel{\vdash} p \} \end{array}$

That is, ${\mathit{intent}(E)}$ is the set of properties enjoyed by all objects in ${E}$ , and ${\mathit{extent}(I)}$ is the set of objects enjoying all the properties in ${I}$ ; a concept is a pair ${(E,I)}$ with ${\mathit{intent}(E) = I}$ and ${\mathit{extent}(I) = E}$ . The concept-forming operators form a Galois connection between ${\subseteq}$ and ${\supseteq}$ :

$\displaystyle \begin{array}{ll} & \mathit{extent}(I) \supseteq E \\ \Leftrightarrow& \qquad \{ \mbox{characteristic of~} \mathit{extent} \} \\ & \forall o \in E .\; (\forall p \in I .\; o \mathrel{\vdash} p) \\ \Leftrightarrow& \qquad \{ \mbox{commuting quantifiers} \} \\ & \forall p \in I .\; (\forall o \in E .\; o \mathrel{\vdash} p) \\ \Leftrightarrow& \qquad \{ \mbox{characteristic of~} \mathit{intent} \} \\ & I \subseteq \mathit{intent}(E) \end{array}$

This construction can be used to translate a problem about the extension of a concept (that is, an enumeration of its instances) into one about the intension (that is, the characteristic properties of its instances). It is related to the observation that “syntax and semantics are adjoint“—under the analogy that “objects” are sets of mathematical structures, “properties” are axioms, and the relation is “satisfaction”, the models of an axiomatic theory ${T}$ are included in a set of structures ${S}$ if and only if the theory ${T}$ logically entails the minimal axiomatization of ${S}$ .

3 Responses to Universal properties and Galois connections

Andrea Vezzosi says:

Friday, April 1st, 2011 at 11:48 pm

in the second to last example you should have used ⊆ rather than ⊇, i think.

- jeremygibbons says:
  
  Saturday, April 2nd, 2011 at 1:44 pm
  
  Thanks – fixed.
  
jeremygibbons says:

Friday, October 3rd, 2014 at 4:13 pm

Fixed a WordPress formatting problem.