Category Theory/Categories

This is the Categories chapter of Category Theory.

DefinitionEdit

A category \mathcal C consists of four kinds of data subject to three axioms, as listed below:

DataEdit

Objects
\mathcal C has objects A, B, C,…
Morphisms
For each ordered pair of objects A, B in \mathcal C, there is a class of morphisms or arrows from A to B. The notation f: A \to B means that f is a morphism from A to B. The class of all morphisms from A to B is denoted by \text{Hom}_\mathcal{C}(A,B).
Composition
For each ordered triple of objects A, B, C in \mathcal C, there is a law of composition: If f:A\to B and g:B\to C, then the composite of f and g is a morphism gf:A\to C
Identity
For each object A there is a designated identity morphism on A, notated as 1_A, from A to A.

AxiomsEdit

These data satisfy the following three axioms, of which the first is in the nature of a convention, while the remaining two are more substantial:

Unique typing
\text{Hom}(A_1,B_1) and \text{Hom}(A_2,B_2) are disjoint unless A_1 = A_2, B_1 = B_2.
Associative Law
h(gf) = (hg)f if the composites are defined. Note that if one composite is defined, the other is necessarily defined.
Identity is a “neutral element”
For the identity morphism 1_B: B \to B associated to each object B, two equations must hold for each pair of objects A and C and each pair of arrows f: A \to B, g: B \to C:
  • 1_B \, f = f
  • g\, 1_B = g

Terminology and fine pointsEdit

  • If f: A \to B in a category, A is called the domain or source of f, and B is called the codomain or target of f.
  • \text{Hom}(A,B) is called a hom class' or a hom set if it is indeed a set. In general a hom set may be empty, but for any object A, \text{Hom}(A,A) is not empty because it contains the identity morphism.
  • The hom set \text{Hom}(A,B) may be denoted by \text{Hom}_\mathcal{C}(A,B) or \mathcal{C}(A,B) if it is necessary to specify which category is referred to.
  • Morphisms may also be called maps. This does not mean that every morphism in any category is a set function (see #Baby examples and #Preorders). Arrow is a less misleading name.
  • The composite gf may be written g\circ f.
  • It might be more natural to write the composite of f:A\to B and g:B\to C as f g instead of g f but the usage given here is by far the most common. This stems from the fact that if the arrows are set functions and x\in A, then (gf)(x)=g(f(x)). Thus g f is best read as "do g after f".

Large and smallEdit

The definition says that a category 'has' objects and 'has' morphisms. This means that for any category \mathcal{C} and X is any mathematical object, the statement ' X is an object of \mathcal{C}' is either true or false, and similarly for the statement ' X is a morphism of \mathcal{C}'. The objects (or arrows) of a category need not constitute a set. If they do, the category is said to be small. If they don't, the category is large.

The requirement that the collection of morphisms from A to B be a set makes a category locally small. In this book, all categories are locally small.

DiscreteEdit

A category is discrete if every morphism is an identity.

Examples of categoriesEdit

Baby examplesEdit

These examples are trivial and maybe uninteresting. But do not underestimate the power of baby examples. For one thing, they are sometimes counterexamples to possible theorems.

0 (the empty category)
This category has no objects and no morphisms.
1
Baby Category 1.svg
The category 1 has one object and one morphism, which must necessarily be the object's identity arrow.
1+1
Baby Category 1 plus 1.svg
This category has two objects and two morphisms: the identities on each object.
2
Baby Category 2.svg
This category has two objects and three morphisms. The third morphism goes from one object to the other.
Remarks
  • The objects of these baby categories are nodes in a graph (not sets) and the morphisms are arrows in the graph (not functions).
  • For these baby categories we don't have to say what the composition operation does: it is always forced.
  • It is impolite to say that categorists think that 1 + 1 is not equal to 2.

The category of setsEdit

The category of sets, denoted by Set, is this category:

  • The objects are all sets
  • A morphism from a set A to a set B is a function with domain A and codomain B.
  • The composition is the usual composition: If f:A\to B and g:B\to C then gf:A\to C is defined by gf(x)=g(f(x)) for all x\in A.
  • The identity morphism 1_A on a set A is the identity function defined by 1_A(x)=x for x\in A.
Terminology and fine points
  • In order to preserve the unique typing in a function definition, it is necessary to include its codomain. For example, 1_A:A\to A is a different function from the inclusion function i:A\to B to some set B properly including A.
  • In most approaches to the foundations of math, the collection of all sets is not a set. This makes Set a large category.

Mathematical structures as categoriesEdit

PreordersEdit

A preorder α on a set A is a reflexive and transitive relation on A, which means that for all a\in A, a α a and for all a, b, c in A, if a α b and b α c, then a α c.

A preorder "is" a category in the following sense: Given a preorder (A, α) the category structure is this:

  • The objects of the category are the elements of A.
  • There is exactly one morphism from a to b if and only if a α b.

The existence of identities is forced by reflexivity and the composition law is forced by transitivity. It follows that the category structure has the property that there is at most one morphism from any object a to any object b.

Conversely, suppose you have a category with set A of objects, with the property that there is at most one morphism between any two objects. Define a relation α on A by requiring that a α b if and only if there is a morphism from a to b. Then (A, α) a preorder.

The statements in the two preceding paragraphs describe an equivalence of categories between the category of small categories and functors and the category of preorders and order-preserving maps.

Remark: Given a preorder, the morphisms of the corresponding category exist by definition. There is exactly one morphism from a to b if and only if a α b. This is an axiomatic definition; in a model a morphism from a to b could be anything, for example the pair (a,b). In no sense is the morphism required to be a function.

GroupsEdit

Every group G can be viewed as a category \mathcal{G} as follows: \mathcal{G} has one single object; call it e. Therefore it has only one homset \text{Hom}_\mathcal{G}(e,e), which is defined to be the underlying set of the group G (in other words, the arrows are the group elements.) We take as composition the group multiplication. It follows that the identity element of G is 1_e. Notice that in the category \mathcal{G}, every morphism is an isomorphism (invertible under composition). Conversely, any one-object category in which all arrows are isomorphisms can be viewed as a group; the elements of the group are the arrows and the multiplication is the composition of the category. This describes an equivalence between the category of groups and homomorphisms and the category of small categories with a single object in which every morphism is an isomorphism.

This can be generalized in two ways.

A category \mathcal{G} is called a groupoid if every morphism is an isomorphism. Thus a groupoid can be called "a group with many objects."

A monoid is a set with an associative binary operation that has an identity element. By the same technique as for groups, any monoid "is" a category with exactly one object and any category with exactly one object "is" a monoid.

Categories of sets with structureEdit

finite sets and functions; denoted FinSet.
monoids and morphisms; denoted Mon.
groups and homomorphisms; denoted Grp.
abelian groups and homomorphisms; denoted Ab.
rings and unit-preserving homomorphisms; denoted Rng.
commutative rings and unit-preserving homomorphisms; denoted CRng.
left modules over a ring R and linear maps; denoted R-Mod.
right modules over a ring R and linear maps; denoted Mod-R.
modules over a commutative ring K and linear maps; denoted K-Mod.
subsets of Euclidean space of 3 dimensions and Euclidean movements
subsets of Euclidean space of n dimensions and continuous functions
topological spaces and continuous functions; denoted Top.
topological spaces and homotopy classes of functions; denoted Toph.
Remarks

The law of composition is not specified explicitly in describing these categories. This is the custom when the objects have underlying set-structure, the morphisms are functions of the underlying sets (transporting the additional structure), and the law of composition is merely ordinary function-composition. Indeed, sometimes even the specification of the morphisms is suppressed if no confusion would arise—thus one speaks of the category of groups.

The examples of sets with structure suggest a conceptual framework. For example, the concept of group may be regarded as constituting a first-order abstraction or generalization from various concrete, familiar realizations such as the additive group of integers, the multiplicative group of nonzero rationals, groups of permutations, symmetry groups, groups of Euclidean motions, and so on. Then, again, the notion of a category constitutes a second-order abstraction, the concrete realizations of which consist of such first-order abstractions as the category of groups, the category of rings, the category of topological spaces, and so on.

Properties of objects and morphismsEdit

IsomorphismsEdit

A morphism f: AB in a category is said to be an isomorphism if there is a morphism g: BA in the category with gf = 1A, fg = 1B. It is easy to prove that g is then uniquely determined by f. The morphism g is called the inverse of f, written g = f -1. It follows that f = g-1. If there is an isomorphism from A to B, we say A is isomorphic to B, and it is easy to prove that "isomorphism" is an equivalence relation on the objects of the category.

ExamplesEdit

  • A function from A to B in the category of sets is an isomorphism if and only if it is bijective.
  • A homomorphism of groups is an isomorphism if and only if it is bijective.
  • The isomorphisms of the category of topological spaces and continuous maps are the homeomorphisms. In contrast to the preceding example, a bijective continuous map from one topological space to another need not be a homeomorphism because its inverse (as a set function) may not be continuous. An example is the identity map on the set of real numbers, with the domain having the discrete topology and the codomain having the usual topology.

Monomorphisms and EpimorphismsEdit

A morphism f in a category C is a monomorphism if, for any morphisms g and h, if fh and fg are defined and fg=fh then g=h.


A morphism f in a category C is an epimorphism if, for any morphisms g and h, if gf and hf are defined and gf=hf then g=h.

Initial and terminal objectsEdit

 T is said to be a terminal (or final) object when  X \to T is a unique morphism for any X in  \mathcal{C} . The law of composition ensures that if  T and T' are terminal objects in  \mathcal{C} , they are isomorphic, i.e., T(') is unique up to isomorphism. In the categories of sets, groups, and topological spaces, the terminal objects are singletons, trivial groups, and one-point spaces, respectively. "b" is the terminal object in 2 as depicted above.

Constructions on categoriesEdit

SubcategoriesEdit

A subcategory  \mathcal{S} of a category  \mathcal{C} is a category in which:

  • The class of objects of  \mathcal{S} is contained in the class of objects of  \mathcal{C} .
  • The class of arrows of  \mathcal{S} is contained in the class of arrows of  \mathcal{C} .
  • For every arrow  f in  \mathcal{S} , the domain and codomain of  f are in  \mathcal{S} .
  • For every object  s in  \mathcal{S} , the identity arrow  1_s is in  \mathcal{S} .
  • For every pair of arrows  f,g in  \mathcal{S} , the arrow  g \circ f is in  \mathcal{S} where it is defined.

Opposite categoryEdit

Given a category \mathcal{C}, the opposite (or dual) category \mathcal{C}^{\text{op}} has the same objects as \mathcal{C} and for every arrow f:a \to b in \mathcal{C}, the arrow f^{\text{op}}:b \to a is in \mathcal{C}^{\text{op}}. In other words, it has the same objects, and arrows are reversed.

The product of two categoriesEdit

Given two categories  \mathcal{B} and  \mathcal{C} , the product category, denoted  \mathcal{B} \times \mathcal{C} , is given by the following data:

  • The objects of  \mathcal{B} \times \mathcal{C} are  (b, c) where  b is an object of  \mathcal{B} and  c is an object of  \mathcal{C} .
  • The arrows of  \mathcal{B} \times \mathcal{C} are  (f, g) where  f is an arrow of  \mathcal{B} and  g is an arrow of  \mathcal{C} .
  • Composition is given by  (f',g') \circ (f,g) = (f' \circ f, g' \circ g)  .

Arrow categoriesEdit

  • A functor category \mathcal{B}^{\mathcal{C}} is a category whose objects are functors T:\mathcal{C} \to \mathcal{B} and arrows are natural transformations.
  • A functor category \mathcal{C}^{\mathbf{2}} is called an arrow category, denoted \mathcal{C}^{\rightarrow}. Its objects are arrows f:a' \to b' in \mathcal{C} and its arrows are pairs of arrows (h,k):f \to f' such that f' \circ h=k \circ f.

Comma categoriesEdit

  • Given categories and functors T:\mathcal{E} \to \mathcal{C} and S:\mathcal{D} \to \mathcal{C}, the comma category (T \downarrow S) has objects (e,d,f) where e is an object in \mathcal{E}, d is an object in \mathcal{D}, and f:Te \to Sd is an arrow in \mathcal{C}. Its arrows are (k,h):(e,d,f) \to (e',d',f') where k:e \to e' is an arrow in \mathcal{E} and h:d \to d' is an arrow in \mathcal{D} such that Sh \circ f = f' \circ Tf. Composition is given by (k,h) \circ (k',h') = (k \circ k', h \circ h'). The identity is 1_{(e,d,f)}=(1_e,1_d).
Last modified on 28 October 2013, at 04:53