Processing math: 100%

Sunday, April 6, 2014

Basic examples of Kan extension in logic and set theory

We give (some basic examples) of (simple Kan extensions) which are used in (both logic and all branches of mathematics).
We show how (several seemingly different examples) in fact are (manifestations of the same general pattern), interpreted in (different target cartesian closed categories).


These examples (are simple) because we extend, not over (a general functor between categories), but merely over (a function between (small) sets).
Thus we start with (a function f:XY between sets).
This fits into (the categorical framework) by considering (the embeddings of Set into 2-Cat and Set-Cat), which take (sets to discrete enriched categories).

We give two examples of target categories: 2={<}, and Set itself, basic respectively to Boolean logic and mathematics.
Each is a ccccc (complete and cocomplete cartesian closed category) thus supports the following operations (among others):

2 and Set as cccccs (complete and cocomplete cartesian closed categories)
completeness cocompleteness internal hom
arity: nullary binary arbitrary nullary binary arbitrary binary
2 or or
Set 1 × + or [,]
We denote the internal hom in Set (the set of functions from, say, set X to set Y), often denoted by exponentiation YX, by [X,Y].

Given the above, we are interested in situations as shown in (the box at left below).
((The box at right below) will be discussed later.) the extension situation(enriched categorical) formulas for pointwise Kan extensionXAVfYARanf=xXYxfAx(4.24)end (x) and (cotensor or power) ()ALanf=xXxfYAx(4.25)coend (x) and (tensor or copower) () Here, as above, (f:XY) is merely (an arbitrary function in the category Set).
(A:XV) is (a function/functor) into (either of the cccccs 2 or Set);
(an A:X2) is called (a predicate on X),
(an A:XSet) is called (an X-indexed family of sets).
(By analogy, (a predicate A:X2) could be called (an X-indexed family of Boolean truth values”).)
We are interested in ways of extending A over f.

To illustrate, let us take a simple case, where (the V=2) and (f is an inclusion of a subset, f:XY).
There are 2|Y||X| possible extensions, where |X| denotes the number of elements in X, etc.
In the partially ordered set of the 2|Y||X| possible extensions:
one extension is least, taking all of YX to ; it will turn out to be (the left Kan extension ALanXY);
one extension is greatest, taking all of YX to ; it will turn out to be (the right Kan extension ARanXY).

We wish to generalize this to (arbitrary functions f in Set),
and to include the case when (the target V is Set instead of 2).
To do this we use formulas which give (pointwise Kan extensions) into (arbitrary suitably complete and cocomplete enriched categories)
(see, e.g., Max Kelly’s Basic Concepts of Enriched Category Theory or nLab),
specialized to (the situation in the left box above).
(The formulas thus specialized) are shown in (the right box above).
((The numbers in parentheses) refer to (the formulas in Kelly’s BCECT);
following (the reference numbers) are (the names of the operators in the formulas).)

The only (slight) challenge is interpreting (the general operations of enriched category theory) in (the specific target cccccs 2 and Set),
then performing (the calculations appropriate in (that particular category))
to transform (the general formula) into (a more familiar form).
We do this in the following display,
first for (the right Kan extensions) for (the targets 2 and Set), then for (the left Kan extensions), again for (both targets):


2-Catformulae common to bothSet-CAT2-CatXA2fARanf=xXYxfAx=fAYXASetfARanf=xXYxfAx=fA=AfY(ARanf)yxXyYxfAx(xX)[yYxfAx]xX[yYxf,Ax]xX[yYxfAx](xX)[(y=xf)(xA)](xf1y[,Ax])×(xf1y[1,Ax])(xf1y[Ax])(xf1y[Ax])(xX)[(xf1y)(xA)]1×(xf1yAx)(xf1yAx)f1yAxf1yAxxf1yAx(fA)y(fA)y(fA)yXA2fALanf=xXxfYAx=fAYXASetfALanf=xXxfYAx=fA=Af!Y(ALanf)yxXxfYyAx(xX)(xfYyAx)xX(xfYy×Ax)xX(xfYyAx)(xX)(xf=yxA)(xf1y×Ax)+(xf1y1×Ax)(xf1yAx)(xf1yAx)(xA)(xf=y)+(xf1yAx)(xf1yAx)yAfxf1yAxxf1yAx(fA)y(fA)y(fA)y

The special cases

2-CatSet-CATXA2!X!XA=(xX)Ax1XASet!X!XA=xXAx1XA2!X!XA=(xX)Ax1XASet!X!XA=xXAx1221=!12=(x)=1SetSet1=!1Set=x=11221=!12=(x)=1SetSet1=!1Set=x=122YY2=(x)=!YYSetSetYYSet=x=!Y1Y22YY2=(x)=!YYSetSetYYSet=x=!YY

Kan extension adjunctions

A little notation: We use V as a variable standing for (either of the cccccs 2 or Set).
As cccccs, either can be used as a base for enrichment, as in the theory of enriched categories,
and (using V for an arbitrary base for enrichment) is fairly standard (at least it is what is used in Kelly’s book BCECT).
[X,V] denotes the (ordinary, mere) category of functors and natural transformations from the discrete category X to V, and likewise for the discrete category Y.
With these notations, we have, for each function f:XY in Set, an adjoint triple (adjoint string of length 3).
The adjoint triple is shown (in CAT) twice, once oriented vertically and once horizontally; each has its advantages. XAf⇓⇑VBY[X,V](Lanf=f!)f(Ranf=f)[Y,V]CAT[X,V]Lanf=f!fRanf=f[Y,V]CATXfYAαγBVCATX=X=XfAαYγABV=V=VCAT|||X=X=XfAAηY=Y=YAϵAAf!βBδAfV=V=V=V=VCAT(Lanf=f!)ff(f=Ranf)the two adjunctionsAAη(Af!f=f(Af!)=(Af!)f)(Aff=f(Af)=(Af)f)AϵA(unit Aη for f!f) and (counit Aϵ for ff), both transformations in [X,V]Aα(Bf=fB=Bf)(Bf=fB=Bf)γAx0-component of transformations in [X,V]Ax0αx0Bx0fBx0fγx0Ax0“name of” bijection (v) (ECT (1.25))Iαx0[Ax0,Bx0f]Iγx0[Bx0f,Ax0]Yoneda (identities-are-free) bijection (ECT (1.46) and ff.)x0fYy[Ax0,By]yYx0f[By,Ax0]definition of copower ()xx0fYyAx0ByyYx0fByAx0in the Ran case, extra step added to show the symmetrydefinition of power ()xx0fYyAx0xyYx0fAx0yιx0univ. coconecocone to the vertex (sink) Bycone from the vertex (source) Byuniv. coneyπx0universal properties of coend (x,ι) and end (x,π)xxfYyAxβyByByδyxyYxfAxy-component of transformations in [Y,V](Af!=ALanf)βBBδ(Af=ARanf)(Bff!=BfLanf)BϵBBBη(Bff=BfRanf)(counit Bϵ for f!f) and (unit Bη for ff), both transformations in [Y,V]

Units and counits of the Kan adjunctions

(The units η and counits ϵ) of the adjunctions ((Lanf=f!)f) and (f(Ranf=f)) may be computed by
setting (the bottom or top arrows in the center part of the above display) to be identities, then following through (the chains of bijections).
(The following) performs (that computation),
first for Aη and Aϵ in [X,V],
then for Bϵ and Bη in [Y,V]:
f!fffX=X=XfAYABV=V=VCAT|||X=X=XfAAηY=Y=YAϵAAf!BAfV=V=V=V=VCATAAη(Af!f=f(Af!)=(Af!)f)(Aff=f(Af)=(Af)f)AϵAIAx01x0fAx0x0fYx0fAx0x0fYx0fAx01x0fAx0IAx0equivalent forms of the components(1.4)||x0fιx0x0fπx0||(1.26)Ax0(Aη)x0((Af!)x0f=xxfYx0fAx)((Af)x0f=xx0fYxfAx)(Aϵ)x0Ax0x0-components of transformations Aη and Aϵ“name of” bijection (ECT (1.25))I1x0fx0fYx0f~x0fιx0[Ax0,xxfYx0fAx]I1x0fx0fYx0f¯x0fπx0[xx0fYxfAx,Ax0]Yoneda (identities-are-free) bijection (ECT (1.46) and ff.)x0fYy~yιx0[Ax0,xxfYyAx]yYx0f¯yπx0[xyYxfAx,Ax0]definitions of copower () and power ()xx0fYyAx0xyYx0fAx0yιx0yιx0yπx0yπx0universal maps of coend (x,ι) and end (x,π)xxfYyAx1(Af!)yxxfYyAxxyYxfAx1(Af)yxyYxfAx(Af!=ALanf)1Af!(Af!=ALanf)(Af=ARanf)1Af(Af=ARanf)identity transformations on Af! and AfBf1Bf=1Bf(Bf=fB=Bf)(Bf=fB=Bf)1Bf=1BfBfidentity transformation on BfBxf1BxfBxfBxf1BxfBxf“name of” bijection (ECT (1.25))I1Bxf[Bxf,Bxf]I1Bxf[Bxf,Bxf]Yoneda (identities-are-free) bijection (ECT (1.46) and ff.)xfYyxfBy[Bxf,By]yYxfyBxf[By,Bxf]definitions of copower () and power ()xxfYyBxfxyYxfBxfyιx~xfBy¯yBxfyπxuniversal properties of coend (x,ι) and end (x,π)xxfYyBxf(Bϵ)yByBy(Bη)yxyYxfBxfy-component of transformations Bϵ and Bη(Bff!=BfLanf)BϵBBBη(Bff=BfRanf)X=X=XfffY1fBY1fBYBBBV=V=VCAT|||X=X=XfffY(fB)ηY=Y=Y(fB)ϵYB(fB)!BϵBBη(fB)BV=V=V=V=VCAT
Duplicate of part of the computation for (the counit Aϵ of f(f=Ranf), evaluated at an element x0X):: (Aff)x0=(ARanf)x0f=xx0fYxfAx(Aϵ)x0Ax0“name of” bijection (ECT (1.25))I1x0fx0fYx0f¯x0fπx0[xx0fYxfAx,Ax0]Yoneda bijectionyYx0f¯yπx0[xyYxfAx,Ax0]transpose under the definition of power ()(Af)y=(ARanf)y=xyYxfAxyπx0yYx0fAx0(x0-component) of (universal map yπ) for (the end for (ARanf)y There are equivalent forms of components (again evaluated at an element x0X) of the resulting transformations: (Aη)x0:Ax0(1.4)IAx01x0fAx0x0fYx0fAx0x0fιx0xXxfYx0fAx=(ALanf)x0f(Aϵ)x0:(ARanf)x0f=xXx0fYxfAxx0fπx0x0fYx0fAx01x0fAx0IAx0(1.26)Ax0 Here are those versions (for a general V) again, followed by their translations for V=2 and V=Set: (Aη)x0:Ax0(1.4)IAx01x0fAx0x0fYx0fAx0x0fιx0xXxfYx0fAx=(ALanf)x0fV(Aη)x0:Ax0(1.4)Ax01x0fAx0x0fYx0fAx0x0fιx0(xX)xfYx0fAx=(ALanf)x0f=(fA)x0f2(Aη)x0:Ax0(1.4)1×Ax01x0f×Ax0x0fYx0f×Ax0x0fιx0xXxfYx0f×Ax=(ALanf)x0f=(fA)x0fSet (Aϵ)x0:(ARanf)x0f=xXx0fYxfAxx0fπx0x0fYx0fAx01x0fAx0IAx0(1.26)Ax0V(Aϵ)x0:(fA)x0f=(ARanf)x0f=(xX)[x0fYxfAx]x0fπx0[x0fYx0fAx0][1x0fAx0][Ax0](1.26)Ax02(Aϵ)x0:(fA)x0f=(ARanf)x0f=xX[x0fYxf,Ax]x0fπx0[x0fYx0f,Ax0][1x0f,Ax0][1,Ax0](1.26)Ax0Set

No comments:

Post a Comment

MathJax 2.7.9