• Nebyly nalezeny žádné výsledky

Categories

A category is a graph with a rule for composing arrows head to tail to give another arrow. This rule is subject to certain conditions, which we will give precisely in Section 2.1. The connection between functional programming languages and categories is described in Section 2.2. Some special types of categories are given in Section 2.3. Sections 2.4 and 2.5 are devoted to a class of examples of the kind that originally motivated category theory. The reader may wish to read through these examples rapidly rather than trying to understand every detail.

Constructions that can be made with categories are described in Sec-tion 2.6. SecSec-tions 2.7, 2.8 and 2.9 describe certain properties that an arrow of a category may have. Section 2.10 describes factorization systems, which are useful structures in many categories. This section is used only in Chap-ters 9 and 16.

2.1 Basic definitions

Before we define categories, we need a preliminary definition.

2.1.1 Definition Let k >0. In a graph G, a path from a node x to a nodey of lengthkis a sequence (f1, f2, . . . , fk) of (not necessarily distinct) arrows for which

(i) source(fk) =x,

(ii) target(fi) = source(fi−1) fori= 2, . . . , k, and (iii) target(f1) =y.

By convention, for each nodexthere is a unique path of length 0 fromxto xthat is denoted (). It is called theempty pathatx.

Observe that if you draw a path as follows:

· fk

−−→ · fk1

−−−−→ · · · f2

−−→ · f1

−−→ ·

with the arrows going from left to right, fk will be on the left and the subscripts will go down from left to right. We do it this way for consistency with composition (compare 2.1.3, C–1).

15

For any arrowf, (f) is a path of length 1. As an example, in Diagram (1.3) on page 10, there is just one path of each lengthk fromnto n, namely (), (succ), (succ,succ), and so on.

2.1.2 Definition The set of paths of lengthkin a graphG is denotedGk. In particular,G2, which will be used in the definition of category, is the set of pairs of arrows (g, f) for which the target off is the source ofg. These are calledcomposable pairsof arrows.

We have now assigned two meanings toG0andG1. This will cause no conflict as G1 refers indifferently either to the collection of arrows of G or to the collection of paths of length 1, which is essentially the same thing. Similarly, we useG0 to represent either the collection of nodes ofG or the collection of empty paths, of which there is one for each node. In each case we are using the same name for two collections that are not the same but are in a natural one to one correspondence. Compare the use of ‘2’ to denote either the integer or the real number. As this last remark suggests, one might want to keep the two meanings ofG1 separate for purposes of implementing a graph as a data structure.

The one to one correspondences mentioned in the preceding paragraph were called ‘natural’. The word is used informally here, but in fact these correspon-dences are natural in the technical sense (Exercise 10 of Section 4.3).

2.1.3 Categories A categoryis a graphC together with two functions c :C2 −→C1 and u: C0 −→ C1 with properties C–1 through C–4 below.

(Recall that C2 is the set of paths of length 2.) The elements of C0 are calledobjects and those ofC1are calledarrows. The function cis called composition, and if (g, f) is a composable pair,c(g, f) is writtengf and is called thecompositeofg andf. IfA is an object ofC,u(A) is denoted idA, which is called theidentityof the objectA.

C–1 The source of g f is the source of f and the target of g f is the target ofg.

C–2 (hg)f =h(gf) whenever either side is defined.

C–3 The source and target of idAare bothA.

C–4 Iff :A−→B, thenf idA= idBf =f.

The significance of the fact that the compositecis defined onG2is that gfis defined if and only if the source ofgis the target off. This means that composition is a function whose domain is an equationally defined subset of G1×G1: the equation requires that the source ofg equal the target off. It follows from this and C–1 that in C–2, one side of the equation is defined if and only if the other side is defined.

In the category theory literature, idAis often written just A.

2.1 Basic definitions 17 2.1.4 Terminology In much of the categorical literature, ‘morphism’, ‘do-main’ and ‘codo‘do-main’ are more common than ‘arrow’, ‘source’ and ‘target’.

In this book we usually use the language we have just introduced of ‘arrow’,

‘source’ and ‘target’. We will normally denote objects of categories by capital letters but nodes of graphs (except when we think of a category as a graph) by lower case letters. Arrows are always lower case.

In the computing science literature, the composite g f is sometimes written f;g, a notation suggested by the perception of a typed functional programming language as a category (see 2.2.1).

We have presented the concept of category as a two-sorted data structure;

the sorts are the objects and the arrows. Categories are sometimes presented as one-sorted – arrows only. The objects can be recovered from the fact that C–3 and C–4 together characterize idA (Exercise 4), so that there is a one to one correspondence between the objects and the identity arrows idA. 2.1.5 Definition A category issmallif its objects and arrows constitute sets; otherwise it islarge(see the discussion of Russell’s paradox, 1.1.3).

The category of sets and functions defined in 2.1.11 below is an example of a large category. Although one must in principle be wary in dealing with large classes, it is not in practice a problem; category theorists have rarely, if ever, run into set-theoretic difficulties.

2.1.6 Definition IfAandBare two objects of a categoryC, then the set of all arrows ofC that have sourceAand targetB is denoted HomC(A, B), or just Hom(A, B) if the category is clear from context. This generalizes the notation of Definition 1.2.13.

Thus for each tripleA, B, Cof objects, composition induces a function Hom(B, C)×Hom(A, B)−→Hom(A, C)

A set of the form Hom(A, B) is called ahom set. Other common notations for Hom(A, B) areC(A, B) andC(AB).

2.1.7 The reference to the set of all arrows from A to B constitutes an assumption that they do indeed form a set. A category with the property that Hom(A, B) is a set for all objectsAandBis calledlocally small. All categories in this book are locally small.

2.1.8 Definition For any path (f1, f2, . . . , fn) in a categoryC, definef1

f2· · ·fnrecursively by

f1f2· · ·fn= (f1f2· · ·fn1)fn, n >2

2.1.9 Proposition The general associative law. For any path (f1, f2, . . . , fn)

in a categoryC and any integerk with1< k < n,

(f1· · ·fk)(fk+1· · ·fn) =f1· · ·fn In other words, you can unambiguously drop the parentheses.

In this proposition, the notation fk+1 · · · fn when k=n−1 means simplyfn.

This is a standard fact for associative binary operations (see [Jacobson, 1974], Section 1.4) and can be proved in exactly the same way for categories.

2.1.10 Little categories The smallest category has no objects and (of course) no arrows. The next smallest category has one object and one arrow, which must be the identity arrow. This category may be denoted1. Other categories that will be occasionally referred to are the categories1+1and 2illustrated below (the loops are identities). In both cases the choice of the composites is forced.

A B

R R

C -D

R R

1+1 2

(2.1)

2.1.11 Categories of sets Thecategory of setsis the category whose objects are sets and whose arrows are functions (see 1.2.1) with composi-tion of funccomposi-tions forc and the identity function fromS to S for idS. The statement that this is a category amounts to the statements that composi-tion of funccomposi-tions is associative and that each identity funccomposi-tion idS:S−→S satisfiesf idS =f and idS g=g for all f with source S and all g with target S. The fact that composition of functions is associative follows by using Definition 1.2.10 repeatedly:

((hg)f)(x) = (hg)(f(x)) =h(g(f(x))) =h((gf)(x)) = (h(gf))(x) The properties of the identity function follow from the definition of the identity function (1.2.2).

In this text, the category of sets is denotedSet. There are other categories whose objects are sets, as follows.

2.1 Basic definitions 19 2.1.12 Definition Thecategory of finite sets, denotedFin, is the cat-egory whose objects are finite sets and whose arrows are all the functions between finite sets.

2.1.13 Definition Apartial functionfrom a setS to a setT is a func-tion with domainS0 and codomain T, where S0 is some subset of S. The category Pfn of sets and partial functionshas all sets as objects and all partial functions as arrows. If f : S −→ T and g : T −→V are partial functions withf defined onS0⊆S andgdefined onT0⊆T, the composite g f :S −→V is the partial function from S to V defined on the subset {x∈S0|f(x)∈T0}ofS by the requirement (gf)(x) =g(f(x)).

It is worth checking that composition so defined is associative. Letf :S

−→T, g :T −→V and h:V −→W be partial functions with domains of definitionS0⊆S,T0⊆T andV0⊆V respectively. We must show

(i) (hg)f has the same domain of definition ash(gf), and (ii) Forxin that common domain of definition,

((hg)f)(x) = (h(gf))(x)

For (i), the domain of definition of (h g) f is the set of x∈ S such that f(x) is in the domain of definition of h g. The latter is the set of t∈T such that g(t) is inV0. Thus, the domain of definition of (hg)f is{x∈S0 |g(f(x))∈V0}. Since g(f(x)) = (g f)(x), that is precisely the domain of definition ofh(gf). As for (ii), the proof is the same as for ordinary functions (Section 2.1.11).

2.1.14 Definition Let α be a relation from a set S to a set T and β a relation fromT toU (see 1.1.5). Thecompositeβ αis the relation from S to U defined as follows: If x∈S and z∈U, (x, z)∈β α if and only if there is an elementy ∈T for which (x, y)∈αand (y, z)∈β. With this definition of composition, thecategory Rel of sets and relationshas sets as objects and relations as arrows. The identity for a setS is the diagonal relation ∆S={(x, x)|x∈A}.

Other examples of categories whose objects are sets are the category of sets and injective functions and the category of sets and surjective functions (Exercises 1 and 2).

Categories also arise in computing science in an intrinsic way. Three ex-amples of this concern functional programming languages (2.2.1), automata with typed states (3.2.6) and deductive systems (Section 5.6). In Sections 2.3, 2.4 and 2.5, we discuss some of the ways in which categories arise in mathe-matics.

2.1.15 Exercises

1. Prove that sets (as objects) and injective functions (as arrows) form a category with functional composition as the composition operationc.

2. Do the same as Exercise 1 for sets and surjective functions.

3. Show that composition of relations (2.1.14) is associative.

4. Prove the following for any arrowu:A−→A of a categoryC. It follows from these facts that C–3 and C–4 of 2.1.3 characterize the identity arrows of a category.

a.Ifgu=gfor every objectBofC and arrowg:A−→B, thenu= idA. b. If u h=h for every object C of C and arrow h: C −→ A, then u= idA.

2.2 Functional programming languages