Certain common mathematical structures can be perceived as special types of categories.
2.3.1 Preordered and ordered sets IfS is a set, a subset α⊆S×S is called a binary relation on S. It is often convenient to write xαy as shorthand for (x, y)∈α. We say thatαisreflexiveifxαxfor allx∈Sand transitiveifxαy andyαz impliesxαz for allx, y, z∈S.
A setS with a reflexive, transitive relationαon it is a structure (S, α) called apreordered set. This structure determines a categoryC(S, α) de-fined as follows.
CO–1 The objects ofC(S, α) are the elements of S.
CO–2 Ifx, y ∈S and xαy, then C(S, α) has exactly one arrow from x to y, denoted (y, x). (The reader might have expected (x, y) here. This choice of notation fits better with the right-to-left composition that we use. Note that the domain of (y, x) isxand the codomain isy.) CO–3 Ifxis not related byαtoy there is no arrow fromxtoy.
The identity arrows ofC(S, α) are those of the form (x, x); they belong toα because it is reflexive. The transitive property ofαis needed to ensure the existence of the composite described in 2.1.3, so that (z, y)◦(y, x) = (z, x).
2.3.2 Example The categoryC(S, α) forS={C, D} and α={hC, Ci,hC, Di,hD, Di}
is the category2exhibited in (2.1), page 18.
2.3.3 Ordered sets A preordered set (S, α) for whichαis antisymmetric (that isxαy and yαximplyx=y) is called anordered setorposet(for
‘partially ordered set’). Two examples of posets are (R,≤), the real numbers with the usual ordering, and for any setS, the poset (P(S),⊆), the set of subsets ofS with inclusion as ordering.
It is often quite useful and suggestive to think of a category as a general-ized ordered set, and we will refer to this perception to illuminate construc-tions we make later.
2.3.4 Semigroups Asemigroupis a setS together with an associative binary operationm:S×S−→S. The setS is called theunderlying setof the semigroup.
Normally fors andt in S,m(s, t) is written ‘st’ and called ‘multiplica-tion’, but note that it does not have to satisfy the commutative law; that is, we may havest6=ts. A commutative semigroup is a semigroup whose multiplication is commutative.
It is standard practice to talk about ‘the semigroupS’, naming the semi-group by naming its underlying set. This will be done for other mathematical structures such as posets as well. Mathematicians call this practice ‘abuse
2.3 Mathematical structures 25 of notation’. It is occasionally necessary to be more precise; that happens in this text in Section 13.1.
2.3.5 Powers We sets1=s and, for any positive integer k,sk =ssk−1. Such powers of an element obey the lawssksn=sk+n and (sk)n=skn (for positive kandn). On the other hand, the law (st)k =sktkrequires commu-tativity.
2.3.6 Empty semigroup We specifically allow theempty semigroup, which consists of the empty set and the empty function from the empty set to itself. (Note that the cartesian product of the empty set with itselfisthe empty set.) This is not done in most of the non-category theory literature;
it will become evident later (Section 9.5.2) why we should include the empty semigroup.
2.3.7 Definition Anidentity elementefor a semigroupSis an element ofS that satisfies the equation se=es=s for all s∈S. There can be at most one identity element in a semigroup (Exercise 3).
2.3.8 Definition Amonoid is a semigroup with an identity element. It iscommutativeif its binary operation is commutative.
It follows from the definition that a monoid isnot allowed to be empty:
it must contain an identity element. It also follows that we can extend the notation in 2.3.5 to 0 by definingx0to be the identity element of the monoid.
The lawssksn=sk+n and (sk)n=skn then hold for all nonnegativek and n.
2.3.9 Examples One example of a semigroup is the set of positive inte-gers with addition as the operation; this is a semigroup but not a monoid.
If you include 0 you get a monoid.
The Kleene closure A∗ of a set A is the set of strings (or lists) of finite length of elements ofA. We write the lists in parentheses; for example (a, b, d, a) is an element of {a, b, c, d}∗. Some parts of the computer science literature call these strings instead of lists and write them this way: ‘abda’.
A∗includes the empty list () and for each elementa∈Athe list (a) of length one.
The operation of concatenation makes the Kleene closure a monoidF(A), called the free monoid determined by A. The empty list is the identity element. We write concatenation as juxtaposition; thus
(a, b, d, a)(c, a, b) = (a, b, d, a, c, a, b)
Note that the underlying set of the free monoid is A∗, not A. In the literature,A is usually assumed finite, but the Kleene closure is defined for any setA. The elements ofA∗are lists offinite length in any case. WhenA is nonempty,A∗ is an infinite set.
The concept of freeness is a general concept applied to many kinds of structures. It is treated systematically in Chapter 13.
2.3.10 Definition Asubmonoidof a monoidM is a subsetSofM with the properties:
SM–1 The identity element ofM is in S.
SM–2 If m, n ∈S then mn ∈S. (One says that S is closed under the operation.)
2.3.11 Examples The natural numbers with addition form a submonoid of the integers with addition. For another example, consider the integers with multiplication as the operation, so that 1 is the identity element. Again the natural numbers form a submonoid, and so does the set ofpositive natural numbers, since the product of two positive numbers is another one. Finally, the singleton set{0} is a subset of the integers that is closed under multi-plication, and it is a monoid, but it is not a submonoid of the integers on multiplication because it does not contain the identity element 1.
2.3.12 Monoid as category A monoidM determines a categoryC(M).
CM–1 C(M) has one object, which we will denote∗;∗ can be chosen arbi-trarily. A simple uniform choice is to take∗=M.
CM–2 The arrows of C(M) are the elements of M with ∗ as source and target.
CM–3 Composition is the binary operation onM. (This construction is revisited in Section 3.4.)
Thus a category can be regarded as a generalized monoid, or a ‘monoid with many objects’. This point of view has not been as fruitful in mathe-matics as the perception of a category as a generalized poset. However, for computing science, we believe that the monoid metaphor is worth consider-ing. It is explored in this book primarily in Chapter 12.
2.3.13 Remark Many categoristsdefine a monoid to be a category with one object (compare 2.3.12) and a preordered set to be a category in which every hom set is either empty or a singleton (compare 2.3.1). This can be justified by the fact that the category of monoids and the category of one-object categories are ‘equivalent’ as defined in Section 3.4.