# Practical Foundations of Mathematics

## 4.4  Functors

Since an action takes composition in the syntax to composition in the semantics, it is an example of a homomorphism of categories.

DEFINITION 4.4.1 A functor F:CÛ D between categories is

(a)
a (class) function \funcFo:obC Û obD, together with

(b)
a function \funcFX,Y:C(X,Y)Û D(\funcF oX,\funcFoY) for each pair of objects X,Y ö obC

which preserves the structure (identity and composition), ie

\funcFX,X(id\CX) = id\D\funcF o(X)        \funcFX,Z(f;C g) = \funcFX,Y(f);D \funcFY,Z(g).

A functor F:CÛ Dop or F:CopÛ D may be called a contravariant functor from C to D, the usual case being styled covariant if emphasis is needed. To avoid the confusion caused by discussing morphisms of an opposite category explicitly when describing contravariant functors, it is usual simply to define \funcFX,Y:C(X,Y)Û D(\funcFoY,\funcFoX).

Since the essence of a functor is that it is defined in a ``coherent'' fashion for all objects and morphisms together, the subscripts and superscripts are omitted: we write F X and F f for the application of the functor to an object or morphism. If it is defined on objects by built-in notation such as C(X,-) or Y(-) this can look a bit strange when applied to maps.

Of course given another functor G:DÛ E we can apply this too, writing the result as G(F X) or G(F f), with the brackets. The abstract theory of functors is a good example of a unary language (Definition 4.2.5), and would be clearer in the left-to-right notation without operators or brackets. For the sake of conformity with other notations and concepts, we shall, however, always write composition of functors from right to left as G·F, and not using juxtaposition.

EXAMPLES 4.4.2 Following 4.1.5 and 4.1.6 , a functor

(a)
between preorders considered as categories is exactly a monotone function (Definition 3.1.5), and a contravariant functor is antitone;

(b)
between monoids, groups or groupoids is exactly a homomorphism;

(c)
between equivalence relations is a function between their quotients (Remark 1.3.2, Examples  2.1.5 and 3.1.6(d));

(d)
from a group to the category of vector spaces is a linear or matrix representation of the group;

(e)
from a poset X to W is an upper subset of X (Example 3.1.6(f)), and XopÛ W is a lower subset (Definition 3.1.7);

(f)
from C to Set is a covariant action of C (Definition 4.2.7);

(g)
from Cop to Set is a contravariant action of C on sets; it is also called a presheaf on C, cf Definitions 3.1.7 and 3.9.6. []

Constructions as functors

EXAMPLES 4.4.3 The following are often known as forgetful functors or underlying set functors. This terminology should only ever be used when the meaning, ie just what is being forgotten, is completely clear from the presentation of the category. Notice that we may forget (a) properties of objects, (b) properties of morphisms or (c) structure on an object together with the property of morphisms that they preserve the structure. The last is the commonest situation. In all cases composition is preserved because it is defined in the same way on both sides.

(a)
PosÛ Preord , DLatÛ Lat, IPO Û Dcpo, AbGpÛ Gp, CMonÛ Mon etc . which forget the significance of laws and the descriptions of special elements such as ^;

(b)
Pos\dashvÛ Pos, SetÛ Pfn and Pfn Û Rel which forget that all joins exist, and totality and functionality of relations;

(c)

HeytÛ LatÛ SLatÛ PosÛ Set , DcpoÛ Pos, Mon Û Set and RngÛ AbGp which forget operations and their preservation.

Besides forgetting things, functors also arise from constructions, where now one may need to check preservation of (identities and) composites.

EXAMPLES 4.4.4 The following are functors:

(a)
PfnÛ Pos, which takes a set X to its lift, Lift X, with the information order (Definition 3.3.7), and a partial function f:X\rightharpoonup Y to the monotone function (U ö LiftX)Û {y|\$x ö U.xfÛ y};

(b)
RelÛ CSLat by XÛ P(X) and RÛ (UÛ {y|\$x ö U. x Ry});

(c)
CSLatÛ Pos\dashv, which equips a function that preserves all joins with its unique right adjoint (Theorem 3.6.9);

(d)
DcpoÛ Sp by the Scott topology (Proposition 3.4.9);

(e)
SpÛ Loc ¤ Frmop by the frame of open sets;

(f)
SpÛ Preord by the specialisation order (Example 3.1.2(i)).

PROOF:

(a)
[[a]] First check that the result of the functor applied to a map is a map of the right kind, in this case {y|\$x.x ö U ìx,y ö f} ö Lift Y. This and preservation of composition are technically the same as the fact that relational composition preserves functionality (Lemma 1.6.6).

(b)
[[b]] Powersets have arbitrary joins, given by unions. These are preserved by the formula shown for morphisms, and in fact any join- preserving function P(X)Û P(Y) arises uniquely in this way.

The other examples rely on composition of adjunctions (Lemma  3.6.6) and of continuous functions. []

A classifying category   We saw that a category is what is required to express a unary algebraic theory. An interpretation of such a theory is similarly given by a functor. Any category may play the role of Set: we restrict to the special case simply because we did in Section 4.2.

THEOREM 4.4.5 Let L be a unary language and \CloneL the category it presents by Theorem 4.2.12. Then interpretations of L correspond to functors \CloneLÛ Set.

omitted diagram environment

PROOF: Let the interpretation be \typeAX on sorts and \typeAr:\typeAXÛ \typeAY on operations. These are already part of the required data for a functor \typeA(-):\CloneLÛ Set, but it remains to define its effect on strings. This is uniquely determined by preservation of (the identity and) composition. Using list recursion, the identity is the base case and composition ( cons) the recursion step. Proposition 2.7.5, which showed that append is associative, guarantees that this too is preserved.

Where a law is given to hold in the interpretation of L, this means exactly that the functor takes equal values on the corresponding strings of operation-symbols. Conversely any functor \CloneLÛ Set restricts to the sorts and generating arrows in a way which satisfies the laws. []

How interpretations and functors correspond is what matters here, not just the fact that they do. (Category theory is in a real sense constructive logic, since the proofs are usually needed to give an accurate statement of the theorems.) Theorem 4.6.7 extends the result to Cn×L and, since it discusses algebra, has a more type-theoretic flavour; later we shall do the same for larger fragments of logic. Example 4.8.2(d) shows how the correspondence deals with homomorphisms.

The propositional analogue at the unary level is simply that a function f:(S, < )Û (Q, È Q ) obeys x < yß f(x) È Q f(y) iff the same function p:\CloneL = (S, È )ÛQ is monotone when the source is considered to carry the reflexive- transitive closure (Section 3.8). A model of a unary Horn theory is a < -upper subset. Similarly any function f:SÛQ from a set to a monoid extends uniquely to a monoid homomorphism \CloneL = List(S)Û Q (Section  2.7).

Theorem 4.2.12 generated a category freely from a sketch in the sense (of universal algebra) that it satisfies only those laws which are forced. By Theorem 4.4.5, it is the free category in the categorical sense of satisfying a universal property (next section). Classifying categories for algebra and the l- calculus will be given in Theorem 4.6.7 and Remark 4.7.4.

The force of functoriality   It is easy to get into the (bad) habit of only defining the effect of a functor on objects, since we usually write them in this way. The force of functoriality, however, lies in the definition on morphisms and the preservation of composition.

EXAMPLES 4.4.6 The following are not functors.

(a)
The map C-/Û M from any category which takes isomorphisms to id and everything else to  e, where M is the monoid {id,e} with e2 = e.

(b)
The centre of a group, Z(G) = {x: G|" g.x g = gx}. The result of applying a homomorphism f:GÛ H to a central element of G need not be central in H, so Z(-) is not defined on maps. In my experience this is the commonest fallacy: not checking that the ``expected'' action on morphisms is well defined.

(c)
Set-/Û Set by XÛ XX is also not defined on morphisms, because it is the ``restriction to the diagonal'' of a functor of mixed variance SetopxSetÛ Set.

(d)
Operations satisfying the definition of a functor apart from the preservation of identities are called semifunctors; they were first studied by Susumi Hayashi. For an example Rel Û Rel, take the powerset on sets and the lower order, (-)\flat, on relations (Exercises 3.55 and 3.57). Any semifunctor gives rise to a functor by splitting idempotents in the categories (Definition 1.3.12, Exercise  4.16).

Category theory was first used in algebraic topology, which aims to assign an (easily calculable) algebraic structure to each topological space in order to distinguish between spaces. For example (only) the nth reduced homology group is non-trivial for the sphere Sn which embeds in (n+1)- dimensional space. The homeomorphisms ( ie topological isomorphisms, and even the continuous functions) between the spaces also give rise to isomorphisms (respectively homomorphisms) between the corresponding groups. It is this property which enables algebraic structures to distinguish the spaces.

REMARK 4.4.7 Suppose \typeX1 ¤ \typeX2 in C, ie there is a pair of morphisms u:\typeX1Û \typeX2 and |:\typeX2Û\typeX1 with u;| = \id\typeX1 and |;u = \id\typeX2; we say that the two objects are isomorphic ( cf Lemma 1.3.11).

(a)
Any structure carried by \typeX1 may be transferred to \typeX2 , because any morphism GÛ \typeX1 or \typeX1Û Q may be turned into a morphism GÛ \typeX2 or \typeX2Û Q by composition with either u or |, and the process is reversible. Hence ¤ is a congruence (Definition  1.2.12) with respect to categorically definable properties.

(b)
Any functor F:CÛ D preserves this property: F \typeX1 ¤ F \typeX2.

Hence if \typeX1,\typeX2 ö C are two objects and F:CÛ D is a functor (such as homology) for which F \typeX1 and F \typeX2 are not isomorphic in D, then \typeX1 and \typeX2 are not isomorphic in C. []

Full and faithful   Since objects are only defined up to isomorphism, it is harmless (and often useful) to make isomorphic duplicates of them (for example in our use of variables, Remark 4.3.14). For this reason injectivity and surjectivity on objects are not particularly important for functors. The force of functoriality is, as we have said, on morphisms.

DEFINITION 4.4.8 Let F:CÛ D be a functor.

(a)
F is faithful if the functions \funcFX,Y:C (X,Y)Û D(FX,FY) are injective, ie given f,g :X\rightrightarrows Y in C, if Ff = F g then f = g.

(b)
F is full if each function \funcFX,Y is surjective , ie given X,Y ö obC and h:FXÛ FY in D there is some f:XÛ Y with F f = h. Notice that (unlike surjectivity of functions) C gives as well as takes in this definition; that is, the objects of C must be specified, not just the morphism of D. In particular óÛ C is full. Fullness is often accompanied by faithfulness, just as uniqueness is more important than existence (see the remarks after the proof of Lemma 1.2.11) .

(c)
F is essentially surjective (on objects) or has representative image if for every object A ö ob D there are some object X ö obC and an isomorphism F X ¤ A in D.

(d)
F is replete if for every X ö obC and isomorphism |:A ¤ F X in D there is a (not necessarily unique) isomorphism u:Y ¤ X in C such that F Y = A and F u = |. A forgetful functor which is replete reflects the means of exchange in the sense that the underlying object may be exchanged for an isomorphic copy and the structure will follow. This is a feature of the presentation, but in their usual form most of the functors we describe are replete.

(e)
F reflects invertibility if every morphism u:X Û Y in C for which Fu:FX ¤ FY in D is already itself invertible in C.

(f)
F reflects the existence of isomorphisms if every X,Y ö obC such that FX ¤ FY in D are already themselves isomorphic in C.

(g)
F is an equivalence functor if it is full, faithful and also essentially surjective (see also Definition  4.8.9(c)).

Similarly, a full subcategory is one whose inclusion functor is full, so it shares the same hom-sets and is determined by its objects. Conversely, a wide or lluf subcategory is one with the same objects, but perhaps fewer morphisms. A  replete subcategory U ä C is one which is full with respect to isomorphisms and is such that if X ö obU and X ¤ Y in C then Y ö obU; this happens, for example, when U is defined by a universal property.

EXAMPLES 4.4.9

(a)
Every monotone function between posets is faithful. It is injective iff it reflects the existence of isomorphisms, and surjective iff it is essentially surjective. The notions of fullness and reflecting invertibility are relevant to posets, and repleteness to preorders.

(b)
Monoid and group homomorphisms are faithful and full iff they are respectively injective and surjective. The monoid inclusions N \hookrightarrow Z (under addition) and Z\{0} \hookrightarrow Q\{0} (under multiplication) do not reflect invertibility. A group homomorphism is replete iff it is surjective.

(c)
The functor SpÛ Loc (giving the open-set lattice) is not faithful, but becomes so exactly when restricted to T0-spaces.

(d)
An action of a category is faithful qua functor iff the action is faithful, ie maps which have identical effect are equal (Definition 4.2.7).

(e)
Examples 4.4.3(a) are full and faithful, as are the Scott topology DcpoÛ Sp, the powerset functor RelÛ CSLat and the forgetful functor CSLatÛ Pos\dashv. The topology functor SpÛ Loc is full and faithful exactly when restricted to sober spaces.

(f)
Forgetful functors from categories of algebras, such as GpÛ Set and LatÛ Set, also reflect invertibility: any bijective homomorphism is an isomorphism.

(g)
The forgetful functors PosÛ Set and SpÛ Set are faithful in the sense given, but do not reflect invertibility (Remark  3.1.6(e)).

(h)
For a forgetful functor to reflect the existence of isomorphisms, each carrier set must support at most one algebraic structure.

(i)
Examples 4.4.3(b) are wide subcategories.

(j)
Let L and LÂ be unary languages (elementary sketches) with the same sorts and operation-symbols, but such that LÂ has additional laws. Then \CloneLÛ \CloneL Â is full but not faithful.

There is a moral to this: the full subcategory of CSLat consisting of powerset lattices has forgetful functors successively to CSLat, Pos\dashv, Pos, Set and finally Rel, but is itself equivalent to Rel. This shows that it is misleading to regard forgetful functors as providing a hierarchy of simplicity amongst categories: the notion is entirely dependent upon presentation, and indeed some of the functors in Examples 4.4.4 would be regarded as forgetful by certain authors.

The ``true form'' (in Plato's sense) of a mathematical object is the totality of constructions from it - its presentations are only images (in both the Platonist and functorial senses). This is in the modern spirit of object-oriented programming, in which data-objects are available only via constructions and not as their substance (machine representation).