ora-0018

1.6 Adjunctions and Kan extensions

Definition 1.13 Adjunction

Functors \(L:\mathcal C\rightleftarrows \mathcal D:R\) form an adjunction \(L\dashv R\) when there are natural equivalences

\[ \mathcal D(LX,Y)\cong \mathcal C(X,RY). \]

The left adjoint \(L\) preserves colimits; the right adjoint \(R\) preserves limits.

Kan extensions generalize extension, aggregation, restriction, and quantification. Let \(J:\mathcal A\to \mathcal B\) and \(F:\mathcal A\to \mathcal D\).

Definition 1.14 Kan extensions

A left Kan extension of \(F\) along \(J\) is a functor \(\operatorname {Lan}_JF:\mathcal B\to \mathcal D\) universal among maps from \(F\) to functors restricted along \(J\):

\[ \operatorname {Lan}_J\dashv J^*. \]

A right Kan extension is universal in the opposite direction:

\[ J^*\dashv \operatorname {Ran}_J. \]

The pointwise formulas for Kan extensions are indexed by comma categories.

Definition 1.15 Comma category

Given functors

\[ \mathcal A\xrightarrow {S}\mathcal C \xleftarrow {T}\mathcal B, \]

the comma category \((S\downarrow T)\) has objects \((a,b,\alpha )\), where \(a\in \mathcal A\), \(b\in \mathcal B\), and \(\alpha :S(a)\to T(b)\). A morphism

\[ (f,g):(a,b,\alpha )\longrightarrow (a',b',\alpha ') \]

consists of \(f:a\to a'\) and \(g:b\to b'\) satisfying

\[ T(g)\circ \alpha =\alpha '\circ S(f). \]

Thus a morphism in a comma category is precisely a commuting square in \(\mathcal C\) between the two displayed comparison arrows.

An object \(b\in \mathcal B\) may be regarded as a functor \(b:\mathbf1\to \mathcal B\). Consequently, \((J\downarrow b)\) has objects \((a,\alpha :J(a)\to b)\), while \((b\downarrow J)\) has objects \((a,\beta :b\to J(a))\). Each carries an evident projection \(\pi \) to \(\mathcal A\), selecting the object \(a\).

When the required (co)limits exist, Kan extensions are calculated pointwise:

\[ (\operatorname {Lan}_JF)(b) \cong \operatorname *{colim}_{(a,\alpha )\in (J\downarrow b)}F(a), \qquad (\operatorname {Ran}_JF)(b) \cong \lim _{(a,\beta )\in (b\downarrow J)}F(a). \]

Equivalently, these are the colimit and limit of \(F\circ \pi \). The arrow orientation matters: maps \(J(a)\to b\) contribute to left extension, whereas maps \(b\to J(a)\) contribute to right extension.

Design principle

UODL reads the left Kan stage as universal candidate generation or evidence extension and the right Kan stage as universal consistency. This is a typed factorization, not a claim that every learning algorithm is secretly a Kan extension.

Definition 1.16 Universal Decision Learning

Given

\[ \mathcal A\xrightarrow {J}\mathcal B\xrightarrow {K}\mathcal Q, \qquad F:\mathcal A\to \mathcal D, \]

the UDL semantic object is

\[ \mathsf U(F)=\operatorname {Ran}_K\operatorname {Lan}_JF \]

whenever the displayed extensions exist.

The recurring visual dictionary for UDL. Left Kan extension freely generates or aggregates candidates from available data; right Kan extension retains the candidates compatible with the declared consistency shape. The construction is universal until an observer supplies… — Figure 1.2 The recurring visual dictionary for UDL. Left Kan extension freely generates or aggregates candidates from available data; right Kan extension retains the candidates compatible with the declared consistency shape. The construction is universal until an observer supplies task-specific meaning.