DEFINITION 4.4.1
A *functor**F*:*C*® *D* between categories
is

**(a)**- a (class) function
\funcF
_{o}:*ob**C*®*ob**D*, together with **(b)**- a function
\funcF
_{X,Y}:*C*(*X*,*Y*)®*D*(\funcF_{ o}*X*,\funcF_{o}*Y*) for each pair of objects*X*,*Y*Î*ob**C*

which preserves the structure (identity and composition), *ie*

\funcF

_{X,X}(id^{\C}_{X}) =id^{\D}_{\funcF o(X)}\funcF_{X,Z}(f;^{C}g) = \funcF_{X,Y}(f);^{D}\funcF_{Y,Z}(g).

A functor *F*:*C*® *D*^{op} or
*F*:*C*^{op}® *D* may be called a ** contravariant** functor
from

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*X*^{op}® 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
*C*^{op}to**Set**is a contravariant action of*C*on sets; it is also called aon*presheaf**C*,*cf*Definitions 3.1.7 and 3.9.6. []

EXAMPLES 4.4.3
The following are often known as ** forgetful functors** or

**(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*Î*Lift**X*)® {*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**º**Frm**^{op}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 \Clone_{L} the category it
presents by Theorem 4.2.12. Then *
interpretations of L correspond to functors
\Clone_{L}® Set*.

omitted diagram environment

PROOF: Let the interpretation be \typeA_{X} on sorts and
\typeA_{r}:\typeA_{X}® \typeA_{Y} on operations. These are already part of the
required data for a functor
\typeA_{(-)}:\Clone_{L}® **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
\Clone_{L}® **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*:\Clone_{L} = (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
\Clone_{L} = *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 e^{2}= 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*®*X*^{X}is also not defined on morphisms, because it is the ``restriction to the diagonal'' of a functor of*mixed variance***Set**^{op}*x***Set**®**Set**. **(d)**- Operations satisfying the definition of a functor apart from
the preservation of identities are called
; they were first studied by Susumi Hayashi. For an example*semifunctors***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 *n*th reduced
homology group is non-trivial for the sphere *S*^{n} 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 \typeX_{1} º \typeX_{2} in *C*, *ie* there is
a pair of morphisms **u**:\typeX_{1}® \typeX_{2} and
|:\typeX_{2}®\typeX_{1} with
**u**;| = \id_{\typeX1} and
|;**u** = \id_{\typeX2}; we say that the two objects are ** isomorphic** (

**(a)**- Any structure carried by \typeX
_{1}may be transferred to \typeX_{2}, because any morphism G® \typeX_{1}or \typeX_{1}® Q may be turned into a morphism G® \typeX_{2}or \typeX_{2}® 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*\typeX_{1}º*F*\typeX_{2}.

Hence if \typeX_{1},\typeX_{2} Î *C* are two objects and
*F*:*C*® *D* is a functor (such as homology) for which *F* \typeX_{1}
and *F* \typeX_{2} are *not* isomorphic in *D*, then \typeX_{1}
and \typeX_{2} 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*isif the functions \funcF*faithful*_{X,Y}:*C*(*X*,*Y*)®*D*(*FX*,*FY*) are injective,*ie*given**f**,**g**:*X*\rightrightarrows*Y*in*C*, if*F***f**=*F***g**then**f**=**g**. **(b)**-
*F*isif each function \funcF*full*_{X,Y}is surjective ,*ie*given*X*,*Y*Î*ob**C*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*isor has*essentially surjective (on objects)*if for every object*representative image**A*Î*ob**D*there are some object*X*Î*ob**C*and an isomorphism*F**X*º*A*in*D*. **(d)**-
*F*isif for every*replete**X*Î*ob**C*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*if every morphism*reflects invertibility***u**:*X*®*Y*in*C*for which*F***u**:*FX*º*FY*in*D*is already itself invertible in*C*. **(f)**-
*F*the existence of*reflects*if every*isomorphisms**X*,*Y*Î*ob**C*such that*FX*º*FY*in*D*are already themselves isomorphic in*C*. **(g)**-
*F*is anif it is full, faithful and also essentially surjective (see also Definition 4.8.9(c)).*equivalence functor*

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

**(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*T*_{0}-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 \Clone_{L}® \Clone_{L ¢}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).