Editing User:Michiexile/MATH198/Lecture 1 (section)

===New Categories from old===

As with most other algebraic objects, one essential part of our tool box is to take known objects and form new examples from them. This allows us generate a wealth of examples from the ones that shape our intuition.

Typical things to do here would be to talk about ''subobjects'', ''products'' and ''coproducts'', sometimes obvious ''variations on the structure'', and what a ''typical object'' looks like. Remember from linear algebra how ''subspaces'', ''cartesian products'' (which for finite-dimensional vectorspaces covers both products and coproducts) and ''dual spaces'' show up early, as well as the theorems giving ''dimension'' as a complete descriptor of a vectorspace.

We'll go through the same sequence here; with some significant small variations.

A category <math>D</math> is a ''subcategory'' of the category <math>C</math> if:
* <math>D_0\subseteq C_0</math>
* <math>D_1\subseteq C_1</math>
* <math>D_1</math> contains <math>1_X</math> for all <math>X\in D_0</math>
* sources and targets of all the arrows in <math>D_1</math> are all in <math>D_0</math>
* the composition in <math>D</math> is the restriction of the composition in <math>C</math>.

Written this way, it does look somewhat obnoxious. It does become easier though, with the realization - studied closer in homework exercise 2 - that the really important part of a category is the collection of arrows. Thus, a subcategory is a subcollection of the collection of arrows - with identities for all objects present, and with at least all objects that the existing arrows imply.

A subcategory <math>D\subseteq C</math> is ''full'' if <math>D(A,B)=C(A,B)</math> for all objects <math>A,B</math> of <math>D</math>. In other words, a full subcategory is completely determined by the selection of objects in the subcategory.

A subcategory <math>D\subseteq C</math> is ''wide'' if the collection of objects is the same in both categories. Hence, a wide subcategory picks out a subcollection of the morphisms.

The ''dual'' of a category is to a large extent inspired by vector space duals. In the dual <math>C^*</math> of a category <math>C</math>, we have the same objects, and the morphisms are given by the equality <math>C^*(A,B)=C(B,A)</math> - every morphism from <math>C</math> is present, but it goes in the ''wrong'' direction. Dualizing has a tendency to add the prefix ''co-'' when it happens, so for instance coproducts are the dual notion to products. We'll return to this construction many times in the course. 

Given two categories <math>C,D</math>, we can combine them in several ways:
# We can form the category that has as objects the disjoint union of all the objects of <math>C</math> and <math>D</math>, and that sets <math>Hom(A,B)=\emptyset</math> whenever <math>A,B</math> come from different original categories. If <math>A,B</math> come from the same original category, we simply take over the homset from that category. This yields a categorical ''coproduct'', and we denote the result by <math>C+D</math>. Composition is inherited from the original categories.
# We can also form the category with objects <math>\langle A,B\rangle</math> for every pair of objects <math>A\in C, B\in D</math>. A morphism in <math>Hom(\langle A,B\rangle,\langle A',B'\rangle)</math> is simply a pair <math>\langle f:A\to A',g:B\to B'\rangle</math>. Composition is defined componentwise. This category is the categorical correspondent to the cartesian ''product'', and we denot it by <math>C\times D</math>.

In these three constructions - the dual, the product and the coproduct - the arrows in the categories are formal constructions, not functions; even if the original category was given by functions, the result is no longer given by a function.

Given a category <math>C</math> and an object <math>A</math> of that category, we can form the ''slice category'' <math>C/A</math>. Objects in the slice category are arrows <math>B\to A</math> for some object <math>B</math> in <math>C</math>, and an arrow <math>\phi:f\to g</math> is an arrow <math>s(f)\to s(g)</math> such that <math>f=g\circ\phi</math>. Composites of arrows are just the composites in the base category. 

Notice that the same arrow <math>\phi</math> in the base category <math>C</math> represents potentially many different arrows in <math>C/A</math>: it represents one arrow for each choice of source and target compatible with it.

There is a dual notion: the ''coslice category'' <math>A\backslash C</math>, where the objects are paired with maps <math>A\to B</math>.

Slice categories can be used, among other things, to specify the idea of parametrization. The slice category <math>C/A</math> gives a sense to the idea of ''objects from <math>C</math> labeled by elements of <math>A</math>''.

We get this characterization by interpreting the arrow representing an object as representing its source and a ''type function''. Hence, in a way, the <hask>Typeable</hask> type class in Haskell builds a slice category on an appropriate subcategory of the category of datatypes.

Alternatively, we can phrase the importance of the arrow in a slice categories of, say, Set, by looking at preimages of the slice functions. That way, an object <math>f:B\to A</math> gives us a family of (disjoint) subsets of <math>B</math> ''indexed'' by the elements of <math>A</math>.

Finally, any graph yields a category by just filling in the arrows that are missing. The result is called the ''free category generated by the graph'', and is a concept we will return to in some depth. Free objects have a strict categorical definition, and they serve to give a model of thought for the things they are free objects for. Thus, categories are essentially graphs, possibly with restrictions or relations imposed; and monoids are essentially strings in some alphabet, with restrictions or relations.