CLASSES That x is a real number is a logical proposition, for all x. And in fact we can form the set \R = { x | x is a real number }. If we want to talk about real numbers, it's sometimes helpful to make use of the set \R. Since the discussion is about the members of \R, it's irrelevant that \R could also be a member of some other set. That x is an ordinal number is also a logical proposition, for all x. However, we can't form the set Omega = { x | x is an ordinal number }. If we want to talk about ordinal numbers, we can't make use of the set Omega, since there is no such thing. But the contradictions that arise from the assumption that Omega is a set depend on the fact that Omega could be a member of some other set, and we were never intending to use that fact at all. How do we use Omega like we used \R? We treat it as a class. A proper class is just like a set except for one restriction: A proper class cannot be a member of a set. A class is something which is either a set or a proper class. The axioms of standard set theory can be rewritten in terms of classes, and then we can add the definition: A set is a class which is a member of some other class. You can use classes just as you use sets, without fear of contradiction (assuming ordinary set theory doesn't lead to a contradiction), as long as you don't put classes inside other classes. You can even speak of the class of all sets. That the set of all sets can't belong to itself leads to a contradiction. That the class of all sets can't belong to itself just proves that the class of all sets is a proper class. CATEGORIES Let O be a class. An object is a member of O. If A and B are objects, let Mor (A, B) be a set. A morphism from A to B is a member of Mor (A, B). The notation `f: A -> B' means f is a member of Mor (A, B). If f: A -> B and g: B -> C, let g . f be a member of Mor (A, C). (The period in `g . f' should be a small, vertically centred circle.) g . f is the composition of the morphisms f and g. Picture O as a big space, with the objects being points in that space. Then the morphisms are arrows that lead from one object to another. If f is an arrow from A to B and g takes you from B to C, then g . f is an arrow that takes you from A to C by following first the arrow f and then the arrow g. The class O, together with the sets Mor (A, B) and the composition function ., forms a category if certain conditions are met. First, composition must be associative; (h . g) . f = h . (g . f). Second, every object must have an identity morphism; 1_A: A -> A, such that 1_A . f = f for all f: B -> A and f . 1_A = f for all f: A -> B. An example is the category of sets, functions, and composition of functions. O is the class of all sets, Mor (A, B) is the set of functions from A to B, and composition of morphisms is just the usual composition of functions. Another example is the category of groups, homomorphisms, and composition. O is the class of groups, Mor (A, B) is the set of homomorphisms from A to B, and composition of morphisms is, again, the usual composition of functions. A further example is the category of topologies, continuous functions, and -- guess what? -- composition of functions. O is the class of topological spaces, Mor (A, B) is the set of continuous functions from A to B, and composition of morphisms is the usual. A different kind of example is the class of sets and subsets. O is the class of all sets, as in the first example. But this time there is one morphism from A to B if A is a subset of B; if A is not a subset of B, then there is no morphism from A to B. It doesn't matter exactly what the morphism is, as long as it's unique. For concreteness, let it be the ordered pair (A, B), if A is a subset of B. If f: A -> B and g: B -> C, there is exactly one possibility for g . f, so composition of morphisms is easy to define. If we're being concrete, so (A, B) is the morphism from A to B, then (B, C) . (A, B) = (A, C) with this composition. There are some generic terms for special kinds of morphisms. A morphism f: A -> A is an endomorphism of A. If f: A -> B, g: B -> A, g . f = 1_A, and f . g = 1_B, then f and g are each isomorphisms, and they are inverses of each other. An isomorphism which is also an endomorphism is an automorphism. For example, every identity morphism is an automorphism. For a final example, notice that a group is itself a kind of category. The category has one object, and the morphisms are the elements of the group. Composition of morphisms is just muliplication of the group elements. The identity of the group is the identity morphism. Every morphism in this category is an automorphism. In fact, you can define a group as a category with one object such that every morphism is an automorphism. FUNCTORS Suppose you have two categories, X and Y. Suppose you have a function F from the objects of X to the objects of Y, so that F (A) is an object of Y if A is an object of X. Suppose further that you have a function from Mor (A, B) to Mor (F (A), F (B)); if f: A -> B, then F (f): F (A) -> F (B). If F (g . f) = F (g) . F (f) and F (1_A) = 1_(F (A)) in every applicable case, then F is a covariant functor from X to Y. If you treat a group as a kind of category, then a homomorphism is a covariant functor between groups. A contravariant functor is like a covariant functor except that it reverses the directions of all the arrows. Thus, F (f): F (B) -> F (A) if f: A -> B, and F (g . f) = F (f) . F (g). You can also form multivariable functors, which may be covariant or contravariant in each variable. For example, suppose X, Y, and Z are categories and F (A, B) is an object in Z if A is an object in X and B is an object in Y. If f: A -> B in X and g: C -> D in Y, suppose F (f, g): F (A, D) -> F (B, C). Then, if F (f . h, g . i) = F (f, i) . F (h, g), F is a functor from X and Y to Z which is covariant in the first variable and contravariant in the second. You can also compose functors in the obvious way. The composition of two functors of the same variance is covariant, and the composition of two functors of opposite variance is contravariant. Every category X has an identy functor 1_X; if f: A -> B is a morphism in X, 1_X (A) = A, 1_X (B) = B, and 1_X (f) = f. An example of a functor is the forgetful functor U from groups to sets. If G is a group, let U (G) be the set of elements of G. If f: G -> H is a homomorphism, let U (f) be the function that underlies it. U is called `forgetful' because it makes groups forget that they're groups. G has a nice algebraic structure, but U (G) is just another set. Suppose V is a vector space over some field K. These spaces and the linear transformations between them form a category. Suppose f is a functional of V, so f is a linear transformation from V to K. The set V* of functionals of V can be made into a vector space over K by defining (f + g) (m) to be f (m) + g (m) and (c f) (m) to be c f (m). Then V* is the vector space dual to the space V. If f: V -> W is a linear transformation, f*: W* -> V*, where, if g: W -> K is in W*, f* (g) (m) = g (f (m)). Then * is a contravariant functor from the category of vectors spaces over K to itself. NATURAL TRANSFORMATIONS This is the most complicated thing I'm going to do now. A natural transformation takes functors to functors. Let F and G be covariant functors from the category X to the category Y. If A is an object in X, let H (A): F (A) -> G (A) be a morphism in Y. If G (f) . H (A) = H (B) . F (f) for any morphism f: A -> B in the category X, then H is a natural transformation from F to G. You can have natural transformations between contravariant functors and between multivariable functors with the same variance in each variable. The rules as the same as above, except some of the arrows go the other way or there may be more of them. You can visualize natural transformations with a diagramme with arrows. In the following diagramme, there are two ways to get from F (A) to G (B). The equation G (f) . H (A) = H (B) . F (f) says you get the same result, no matter which of the two ways you choose. This diagramme commutes; a diagramme where it doesn't matter which way you go is called `commutative'. H (A) F (A) ---------> G (A) | | | | | F (f) | G (f) | | | | v v H (B) F (B) ---------> G (B) I will give one example. If V is a vector space, let V* be its dual. Then V** = (V*)* is also a vector space over the same field. Note that ** is covariant, like the identity functor. I claim there is a natural transformation from the identity functor to **. To define this, I just have to give you v** in V** for each v in V, which gives you the linear transformation that is the top row in the diagramme, assuming all the conditions in the definition of natural transformation hold. If f is a functional of V, then v** (f) = f (v). I leave it to you to check that ** is a linear transformation from V to V** and that the appropriate diagramme really does commute. This natural transformation between a vector space and its double dual was called `natural' long before category theory was ever invented. It was originally called this because it didn't depend on choosing a basis. In contrast, one could use a basis to find a linear transformation from a vector space to its dual, but the map would depend on the basis. There are lots of things mathematicians call `natural', and about half of them can be expressed as natural transformations, even though many of these were named long before category theory. Cool, huh?