Notices
Results 1 to 38 of 38

Thread: Category Theory Primer

  1. #1 Category Theory Primer 
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    What follows scarcely seems like mathematics at all. Real mathematicians frequently recoil at the extreme level of abstraction involved in this subject, but I maintain it is one that can be enjoyed by those will very little math training. In a sense, it is on the interface between math and philosophy. (I say this advisedly, as I hope to make clear).

    So, You have all put up with my long-winded and boring dissertations on things like Groups, Vector Spaces, Topological Spaces, Manifolds etc. Actually, it comes as some surprise to learn that many of these constructions are relatively modern - one might say that the history of 19th and 20th century has been one of increasingly finer dissection of the subject into sub-disciplines.

    Then, in 1945 a guy named Saunders Mac Lane asked the seemingly simple question: Is it possible to come up with a single language that will describe all of of these disciplines with equal accuracy? He decided the answer is "Yes", and that this language should be called category theory.

    So we had better start with some definitions, which I motivate as follows. When we do set theory, we handle "objects" called sets, with "arrows" pointing form one object to another called set functions. When we do group theory, we handle objects called groups, with arrows between them, called group homomorphisms, vector spaces have linear transformations as arrows etc etc..

    So, my definitions:

    A category C consists of a collection of mathematical objects X, Y, Z for which the following is true;

    for any pair of objects X, Y, there is at least one "mapping" f: X → Y called a morphism, or, by me, an arrow;

    for each object X ∈ C there is a privileged arrow called the identity, id<sub>X</sub>: X → X;

    if f: X → Y, and g: Y → Z, then g ⋅ f: X → Z; this composition is associative;

    f ⋅ id<sub>X</sub> = f and f = id<sub>Y</sub> ⋅ f.

    That's it!

    Oh - notice that I compose arrows right-to-left, this is standard.

    So, I will give a couple of examples, make an important comment, then leave you in peace.

    In the category Set, the objects are sets, the arrows are set functions. In the category Grp the objects are groups, the arrows are group homomorphisms. In the category K-Vec the objects are vector spaces over the field K, the arrows are linear transformations. Simple really.

    Now note this well; category theory is not really interested in the objects themselves, rather the arrows are the main interest - I will show you why later, with an example.

    If objects take back seat, the elements in the objects - set elements, group elements, vectors, in our examples above - don't even make it through the door!


    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    Welcome back! This looks like it could be a great thread--it may drum up a lot of interest in the math forum.

    One small nitpick: in my definition of a category, there need not exist a morphism between any pair A, B of objects. This isn't that important, because most applications involve objects which always have some sort of trivial map--a 0 map in an algebraic setting, a point map in a topological one, etc.

    As an example of a category in which not all pairs of objects have morphisms between them, consider a poset (P,≤)*. Define a category where the objects are the points of P and there is a morphism between a and b iff a≤b. Check that this is a category. If we take a poset (P,≤) in which there are incomparable elements (i.e., elements a and b so that neither a≤b or b≤a is true), then not all pairs of objects have morphisms between them. For example (N,|), the natural numbers under divisibility, satisfies this, as any two distinct primes are incomparable.


    *P is a set, ≤ is a reflexive, transitive binary relation on P, and ≤ is antisymmetric--if a≤b and b≤a, then a=b.

    ------------------------------------------------------

    PS: I guess you can always turn any category into one which always has morphisms between any two objects. Let's take a category C and, between any two objects A, B of C, throw in a morphism Z: A -> B. Declare that Z composed on either side with any other morphism gives the Z morphism between the appropriate objects. All of your old info is still there.


    Reply With Quote  
     

  4. #3  
    Forum Freshman
    Join Date
    Oct 2007
    Posts
    57
    Nice!

    I really like the approach of taking a macroscopic view rather than a specialised perspective. Taking a step back and looking for similarities and pattern in all fields of modern mathematics can definitely yield new insights. I'm not a trained mathematician, but I actually can follow your logic (I think). By generalizing some of the common themes between set, vector and group theory, one can benefit from a more universal big picture. It can help remove intellectual thresholds and thereby accellerates learning (I personally struggle to understand details of a subject without being able to relate them to some kind of global mental framework that consist of no more than 6-8 building blocks).

    From a philosophical perspective the following question immediately bubbled up:

    Is there in your model also a Category of all Categories ?
    Reply With Quote  
     

  5. #4  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    Excellent question! I don't want to step on Guitarist's toes, so let me just say that there is indeed a notion of morphism between two categories, and these morphisms are called functors.
    Reply With Quote  
     

  6. #5  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    Quote Originally Posted by serpicojr
    Welcome back!
    Thanks, it's been a while, I know.

    As an example of a category in which not all pairs of objects have morphisms between them, consider a poset (P,≤)
    Yeah, right, this was to be my canonical example of why category theory cares nothing for elements. I'll get to this directly.

    Accountabled: Yes, there is a category of all categories. Unsurprisingly, it's called Cat. In fact that is one of the reasons I called a category a collection of objects. If I called it a set, I would incur the wrath of Russell, precisely for this reason (well, among others)!

    More tomorrow, if you can bear it.......
    Reply With Quote  
     

  7. #6  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    OK, kids, let's press on. serpicojr raised an interesting point, which I now want to explain. I warn you, this had me tugging my beard for a full day (though, as you're all probably smarter than me, maybe you'll breeze through it.). Either way, take it slow and ask questions, as it is rather subtle.

    often there is more that one way to "categorize" a mathematical object, which I will illustrate for the case case of posets, since our friend raised them.

    Recall first the poset ( = partially ordered set) axioms;

    x ≤ x (reflexivity)

    if x ≤ y, then y ≥ x (antisymmetry)

    if x≤ y and y ≤ z, then x ≤ z (transitivity).

    Now we need a certain generosity of spirit to interpret the symbol ≤. It may, of course mean the usual arithmetic "less than or equal to". But we will also take it to include the relation ⊆, and also the relation "x divides y", often written as x|y. Bear this in mind, as I shall return to this shortly.

    Now, I can consider the category of posets, let's call it Pos, whose object are partially ordered set in the above loose sense, and whose arrows (morphisms, if you prefer) are monotone set functions. (recall that a function is called monotone if, roughly speaking, it preserves order in the above sense of the word.

    In this sense, serpico was not quite right.

    BUT.... I can also interpret the relations x ≤ y, x ⊆ y, x|y as an arrow x → y. This implies that I may treat a randomly chosen poset as a category unto itself, whose category theoretic objects are set elements, and whose arrows are the poset binary relations.

    Now since the poset axioms do not permit a total order (2|14 and 7|14, does 2|7?), serpico was right in this context; not all objects in this category have arrows between.

    But note that, I may have as many such posets as I choose, each having different partially ordered set elements. But there is only one such category!!. This is why I say I care eff-all about objects, since in fact, this latter category should perhaps be referred to as the category of ≤'s.

    It so happens the same reasoning is true for preorders, monoids and groups.

    Maybe more later, but I'd better get back to work......
    Reply With Quote  
     

  8. #7  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    Quote Originally Posted by Guitarist
    But note that, I may have as many such posets as I choose, each having different partially ordered set elements. But there is only one such category!!
    I'm not sure what you mean by this.
    Reply With Quote  
     

  9. #8  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    OK, maybe I expressed myself poorly. Let's try again.

    Consider the category Pos of all partially ordered sets, whose morphisms are monotone set functions. The number of such objects in Pos is huge.

    By my earlier assertion, that I am free to interpret the relation ≤ as a category theoretic morphism, then it may appear that, for any and all objects in Pos, there is again a category, whose objects are set elements, and whose morphisms are ≤, and that is there is therefore a correspondingly huge number of such categories.

    But this is simply not the case - there is only one such category. Therefore, I conclude that I had better not worry too much about the objects, rather accept that by the arrow ≤ = →, I may mean less than or equal, set inclusion or divisible mod zero, or whatever else springs to mind, and that is all that counts.

    You may well ask then "what is this category called, if it isn't quite Pos?" Well the answer is disappointing, I'm afraid; it's just called a category, since category theory, at it's deepest level, is simply a generalization of the concepts of preorder and monoid.

    I do confess, this concept caused me no end of grief at first
    Reply With Quote  
     

  10. #9  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    Quote Originally Posted by Guitarist
    Consider the category Pos of all partially ordered sets, whose morphisms are monotone set functions. The number of such objects in Pos is huge.
    Yes.

    By my earlier assertion, that I am free to interpret the relation ≤ as a category theoretic morphism, then it may appear that, for any and all objects in Pos, there is again a category, whose objects are set elements, and whose morphisms are ≤, and that is there is therefore a correspondingly huge number of such categories.
    Yes.

    But this is simply not the case - there is only one such category.
    No. You just constructed a category for each poset. Once you introduce the notions of equivalence of categories, you can show that each category defined by a poset is inequivalent to any other category defined by a nonisomorphic poset.
    Reply With Quote  
     

  11. #10  
    Forum Ph.D.
    Join Date
    Apr 2008
    Posts
    956
    Category theory is great at abstracting a lot that is common between abstract structures that may look different at first glance, but the attempt at looking for similarities shouldn’t be carried too far. A particular category may have certain properties that are unique to itself and not easily generalizable to other categories.

    Take, for instance, the question of isomorphisms – or “iso-arrows” if you like. An iso-arrow from one object X to another object Y is an bijective arrow from X to Y such that the inverse mapping from Y to X is also an arrow. In certain categories, it is sufficient for an arrow to be bijective in order to become an iso-arrow. This is the case for groups and rings, where the arrows are homomorphims and the iso-arrows are isomorphisms: any bijective homomorphism is an isomorphism. It’s also the case for vector spaces, where the arrows are linear transformations and the iso-arrows are isometries (distance-preserving linear transformations). For topological spaces, things are a bit different. Here the arrows are continuous functions and the iso-arrows are homeomorphisms – but bijective continuous functions are not necessarily homeomorphisms.

    This is because a bijection between two topological spaces is not necessarily bicontinuous: it may be continuous in one direction but not in the other. For example, let X be the topological space consisting of the real numbers with the power set of and Y be the topological space consisting of with the topology {Ø, }. If Φ is the identity map of the real numbers (so it is its own inverse), then Φ:XY is continuous but Φ:YX is not continuous. Hence Φ is not a homeomorphism. (Indeed X and Y are clearly nonhomeomorphic since Y is a connected space whereas X isn’t.)

    For groups and rings, if a homomorphism is bijective, the inverse function is automatically a homomorphism as well. Similarly, if a linear transformation between vector spaces is a bijection, its inverse is always a linear transformation. Continuous functions between topological spaces are different.
    Reply With Quote  
     

  12. #11  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    Quote Originally Posted by JaneBennet
    It’s also the case for vector spaces, where the arrows are linear transformations and the iso-arrows are isometries (distance-preserving linear transformations).
    Careful--not all vector spaces come equipped with a metric, and so the notion of isometry doesn't always make sense in a vector space. And an isometry need not always be invertible. For example, consider the vector space of functions from N to C for which the series with terms f(n) is absolutely convergent. Define a norm on this space to be the absolute value of the sum of the series with terms f(n). If you map f to the function g(n) = f(n-1) for n > 1, g(1) = 0, you have that f and g have the same norm, so this is an isometry. However, g sits in the proper subspace of functions with g(1) = 0.

    -----------

    PS: And I should have also stated that not all invertible linear maps are isometries--for example, scalar multiplication is a linear isomorphism, but this is only an isometry when the scalar has absolute value 1. (I guess I'm assuming we're working in a normed space here.)
    Reply With Quote  
     

  13. #12  
    Forum Ph.D.
    Join Date
    Apr 2008
    Posts
    956
    Oops. I was thinking of rotations and reflections in <sup>2</sup> and <sup>2</sup>, forgetting that these are also metric spaces.

    What’s the name for two vector spaces that are “essentially the same” (i.e. for which there exists a bijective linear transformation between them)? Groups/Rings which are essentially the same are isomorphic, and topological spaces which are essentially the same are homeomorphic. What about vector spaces which are essentially the same?
    Reply With Quote  
     

  14. #13  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    Quote Originally Posted by serpicojr

    No. You just constructed a category for each poset. Once you introduce the notions of equivalence of categories, you can show that each category defined by a poset is inequivalent to any other category defined by a nonisomorphic poset.
    Well OK, I guess I was shortcutting somewhat. But it does illustrate an important point;

    militant category theorists look askance at words like "equal" and "the same", rather, under a natural isomorphism, two or more objects or categories are sufficiently alike to be considered as one.

    My purpose had been to try and illustrate the point that the exact nature of the poset elements, in this case regarded as objects in a category, is entirely immaterial, which brings me to

    Jane: The whole point of category theory, to my mind at least, is that, anything I say about one category can usually (not always) be taken to apply any other category.

    So words like "bijection", "norm" etc. are not recognized, though there is a related category theoretic notion for injection, surjection and bijection. We can talk some about that later, but foe now lemme just stamp out a few more definitions.

    Let C and D be arbitrary categories. The mapping F: CD is called a functor. (i was about to say this gadget is unique to category theory, but, historically at least, that's not quite correct; when Poincare introduced us to the Fundamental Group, for example, he did so via a mapping of this sort from a pointed toplogolical space to the homotopy group. In modern lingo we might write Top<sub>*</sub>Grp).

    Anyhoo - functors are very respectful creatures; they respect objects, they respect the identity, they respect arrows, they respect composition of arrows etc.

    So, for example, in the case that, say f: X → Y ∈ C, then F(f): F(X) → F(Y) ∈ D, and so on.

    Now it might immediately occur to you, as it did to me, that there's a problem here; what about the functor F: SetGrp, say. How can a functor magically conjure the group axioms simply by being fed a set? Ah well, boys and girls, that will have to wait. I have something more important to do first.

    Recall I was at pains not to refer to the collection of objects that comprise a category as a set. Well, it turns out that the collection of arrows from one object in a category to another object in the same category is in fact a set.

    This set is called a Hom-set, and is very unattractively written Hom(X,Y) is the set of all arrows X → Y.

    But Hom-sets are sets, and are therefore objects in the category Set. This means that for an arbitrary category C, I will need a functor CSet. This guy is called a Hom-functor. It's sole pleasure in life is to take all the arrows X to Y to the appropriate Hom-set.

    OK, I am about to introduce one of the key concepts in our theory, but I fear that the length of this post will prevent you from seeing it.

    Later.
    Reply With Quote  
     

  15. #14  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    Quote Originally Posted by JaneBennet
    What’s the name for two vector spaces that are “essentially the same” (i.e. for which there exists a bijective linear transformation between them)?
    Isomorphic! It is a fundamental theorem that states that any 2 vector spaces of the same dimension are isomorphic.

    This is just as well, if you think about it. Recall that the dimension of a vector space is given by the number of basis vectors in the spanning set. Recall also that the SAME vector space can be represented on infinitely many different spanning sets, all of the same cardinality, so we require this space to be isomorphic to itself. That's why I called it a fundamental theorem.
    Reply With Quote  
     

  16. #15  
    Forum Ph.D.
    Join Date
    Apr 2008
    Posts
    956
    Quote Originally Posted by Guitarist
    Quote Originally Posted by JaneBennet
    What’s the name for two vector spaces that are “essentially the same” (i.e. for which there exists a bijective linear transformation between them)?
    Isomorphic! It is a fundamental theorem that states that any 2 vector spaces of the same dimension are isomorphic.

    This is just as well, if you think about it. Recall that the dimension of a vector space is given by the number of basis vectors in the spanning set. Recall also that the SAME vector space can be represented on infinitely many different spanning sets, all of the same cardinality, so we require this space to be isomorphic to itself. That's why I called it a fundamental theorem.
    Thanks. :-D


    Quote Originally Posted by Guitarist
    Let C and D be arbitrary categories. The mapping F: CD is called a functor.
    Shouldn’t functors be more than just functions between categories – i.e. they should also preserve the arrows between category objects?
    Reply With Quote  
     

  17. #16  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    Quote Originally Posted by JaneBennet
    Shouldn’t functors be more than just functions between categories – i.e. they should also preserve the arrows between category objects?
    Didn't I say that? I should have!.

    Here. let f: X → Y, and g: Y → Z ∈ C. Let the functor F: CD. Then the following is true;

    F(f): F(X) → F(Y);

    F(g): F(Y) → F(Z);

    if (g ⋅ f): X → Z ∈ C, then F(g ⋅ f) = F(g) ⋅ F(f): F(X) → F(Z) ∈ D.

    Anyone who has studied group theory should find that last identity highly suggestive. It is no accident, and is at the heart of the discussion I was having with serpicojr.
    Reply With Quote  
     

  18. #17  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    OK, so long as I am sitting here, let's press on. I warn you all, the ascent get rather steep for a while, but then we will reach a high plateau.

    Recall I introduced the functor - the Hom-functor - that takes arrows in an arbitrary category C to the objects in Set which I called Hom-sets.

    In fact we recognize two such functors, the first of which is entirely benign. So, to give myself room for the symbols I need, I'm going to invert notation slightly; let X be an arbitrary category, with A, B, C, D ∈ X.

    Let us now consider all the arrows out of A. I set k: A → B, f: B → C etc as shown here;



    Notice that I encounter no difficulty in expressing the arrows A → C and A → D in terms of the arrows A → B, B → c etc, as shown.

    I may think of this as sliding the tip of the "k-arrow" along f in the direction of f etc.

    This is called the "push-forward" of k along f, or more loosely, the push-forward of f.

    The relevant Hom-sets will be k ∈ Hom(A, B), f ⋅ k ∈ Hom(A, C) etc, as shown. So I now seek a functor that takes f to the Hom-set Hom(A,B), k ⋅ f to the Hom-set Hom(A,C) etc. This functor I will call Hom(A, -): XSet.

    The pushforward defines the functor Hom(A,-) as a covariant functor

    I now seek a set function that takes Hom(A,B) to Hom(A,C) etc. This I will denote, using the diagram as a guide, by Hom(A, f) (since f; B → C, A being fixed), or alternatively as f<sub>*</sub>. I don't like this so well, and I'll tell you why for free; Hom(A,f) is a function on sets - Hom-sets - like I said. But f<sub>*</sub> is a sort of "modified" category theoretic arrow.

    However, using this notion, we may see that f<sub>*</sub>(k) = f ⋅ k.

    All this is summarized in this picture;



    Unfortunately, the alter-ego of this functor is thoroughly malign, even I need to gird my loins for this bastard.

    Later
    Reply With Quote  
     

  19. #18  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    Quote Originally Posted by Guitarist
    My purpose had been to try and illustrate the point that the exact nature of the poset elements, in this case regarded as objects in a category, is entirely immaterial, which brings me to...
    I hate to beat a dead horse, but do you agree with what I said? When you construct categories from posets, you end up with a whole slew of different categories.

    Recall I was at pains not to refer to the collection of objects that comprise a category as a set. Well, it turns out that the collection of arrows from one object in a category to another object in the same category is in fact a set.
    This isn't the case. The basic axioms of category theory do not require or imply that the class of morphisms between two objects is a set.
    Reply With Quote  
     

  20. #19  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    Quote Originally Posted by Guitarist
    The relevant Hom-sets will be k ∈ Hom(A, B), f ⋅ k → Hom(A, C) etc, as shown. So I now seek a functor that takes f to the Hom-set Hom(A,B), k ⋅ f to the Hom-set Hom(A,C) etc. This functor I will call Hom(A, -): XSet.
    So you really mean here that Hom(A,-) takes B to Hom(A,B), C to Hom(A,C), etc.
    Reply With Quote  
     

  21. #20  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    Quote Originally Posted by serpicojr
    I hate to beat a dead horse, but do you agree with what I said? When you construct categories from posets, you end up with a whole slew of different categories.
    Yes, but the point being that, from a purely category theoretic point of view, there is no reason to regard them as distinct iff we disregard the differences between the objects in these categories.

    Leave it, it is a dead horse, in fact it is starting to decay

    This isn't the case. The basic axioms of category theory do not require or imply that the class of morphisms between two objects is a set.
    Well according to Mac Lane and his students, they do.

    Let's see if we can agree on the definition of a set. I say that a set is a collection of objects for which I can devise a characterization, and that is well-defined in the sense that, for any object chosen at random from the universe of objects, an object is definitely in the set or definitely not in it.

    I will further say that the operation of set union is defined - in the present case this corresponds to the composition of arrows.

    I will also say that that the operation of set intersection is defined. In the present case, the intersection is almost always empty, but that doesn't mean it isn't defined.

    Finally I will say there is an arrow, called a set function, that maps a set to another set, element by element. (This set function I called Hom(A,f) earlier)

    Can you point out where the collection of arrows between 2 objects in a category fails these tests?

    So you really mean here that Hom(A,-) takes B to Hom(A,B), C to Hom(A,C), etc.
    Well, of course. But Hom(A,-) is a functor; it is a mapping form the category X to the category of sets, as I said. True, it respects objects, so that, yes, Hom(A,-) takes B to Hom(A,B) etc.

    It also respects arrows, so it takes the arrow f in X to the set function Hom(A,f), which takes the set Hom(A,B) to Hom(A,C)

    P.S by edit: Ok fair enough, I checked back, and for my assertions to be true, I require my category to be small, specifically locally small.

    I strongly suspect, but have given it no thought, that any other sort of category is somewhat pathological. Dunno, out of time for now
    Reply With Quote  
     

  22. #21  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    Quote Originally Posted by Guitarist
    Ok fair enough, I checked back, and for my assertions to be true, I require my category to be small, specifically locally small.

    I strongly suspect, but have given it no thought, that any other sort of category is somewhat pathological. Dunno, out of time for now
    I agree with you that we may as well deal with locally small categories, as most categories we care about have set-sized hom sets. I can't, off the top of my head, think of one where the hom sets wouldn't be sets.

    (Oh, wait, yes I can. So given a group G, we can define a category with one object, let's call it O, and for each element g of G, we have a morphism g: O -> O. Composition is defined via the group law. If we relax the definition of group so that G need not be a set, for example let G be the additive group of surreal numbers, which is a proper class, then you get a proper class of morphisms. Since there's only one object, there's only one hom class, and so it must contain all morphisms and hence must be a proper class.)

    In any case, I think we're cool, and I'd love to see where you're going to take us next!
    Reply With Quote  
     

  23. #22  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    So, we talked about the covariant Hom-functor Hom(A,-), this being the guy that takes all arrows out of A to the relevent Hom-sets in a coherent way.

    Lemme quickly bore you with a piece of notation; whereas set theorists use the terms domain/codomain for set functions, category theorists use the terms source/target for functors. Let's pretend that we are category theorists.

    So, a covariant functor induces a pushforward in the target category of some arrow in the source category

    Let us now consider all the arrows into A, like this



    Obviously starting at A isn't going to get me anywhere. But if I start at B, go along the top, then down the RHS, I recover an arrow B → A.

    Like this



    I can think of this as sliding the tail of the "h-arrow" back along g, then back along f. This is called the pullback of h along g and f, or more usually the pullback of g etc. This defines the the functor Hom(-,A) to be a contravariant functor.

    The relevant set functions are now as shown



    where again I have included the "alternative" notation f<sup>*</sup>.

    Tugging your beard a bit, and comparing diagrams, you will see that g<sup>*</sup>(h) = h ⋅ g. Compare this to the pushforward, and we get an immediate intuition as to the origin of the term contravariant.

    Lemme say 3 things quickly, as it's supposed to be a family day.

    First, don't run away with the idea tha I am being Micky-Mouse in showing diagrams; they are a standard an indispensable tool in categoty theory. It's almost like they are the algebra of the theory.

    Second, we have encountered the first example if a key concept of the theory. It's called "duality"; for each category theoretic property, the will be a dual, co-property.

    Finally, if any of you struggled through my Vectors Spaces thread of last year, you may have been surprised by my refusal to use the terms co- and contravriant in respect of tensors. You now see why; type (s,0) tensors induce the pushforward T<sub>*</sub>M, type (0,r) tensors induce the pullback T<sup>*</sup>M. So I would have to call the former co variant and the latter contravriant. This is, of course, the opposite of the physicist's convention, so I avoided it altogether.

    I fear this is a little garbled. If I have been unclear, or made mistakes, just shout
    Reply With Quote  
     

  24. #23  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    OK, so we encountered the co- and contravariant Hom-functors, respectively Hom(A,-) and Hom(-, A) as mappings from our arbitrary category to the category of sets.

    Let's now see how these guys are related, and in so doing, I will introduce you to a fun game.

    Let us first gather the tools we shall need. Let A, B, C, D ∈ X as objects in an arbitrary category.

    Let f: A → B, and g: C → D ∈ X.

    Now let's consider the image of f under the action of the covariant functor Hom(D,-) = Hom(D, f): Hom(D,A} → Hom(D, B).

    Likewise, let's say that the image of the arrow g: C → D under the contravariant functor Hom(-, A) is Hom(g,A): Hom(D, A} → Hom(C, A).

    Recall that this functor reverses arrows. This is shown in this diagram.



    So, the rules of the game are these; starting in the top left corner, is it the case that all routes (here two) to the bottom right corner are identical?

    On first encounter with diagrams of this sort (they are called commutaive diagrams), it is tempting to say "why yes, it's obvious". but recall we are doing mathematics of a sort, so we need to be a bit more rigourous.

    First, for ease of notation, I will invoke the "equivalence" Hom(D, f) ≡ f<sub>*</sub> as the pushforward of f. and Hom(g, A) ≡ g<sup>*</sup> as the pullback of g.

    So now I want to start with an element in Hom(D, A), top left. Let's call it ϥ: D → A. Going along the top, and applying the pushforward f<sub>*</sub> to this guy, I get that f<sub>*</sub>(ϥ) = f ⋅ ϥ ∈ Hom(D, B).

    I now go down the RHS, and apply the pullback g<sup>*</sup>( f ⋅ ϥ) = f ⋅ ϥ ⋅ g ∈ Hom(C, B).

    Now, starting again top left in my diagram, and moving rather more swiftly (since we learned a bit already) I see that g<sup>*</sup>(ϥ) = ϥ ⋅ g ∈ Hom(C, A), and, along the bottom, the pusforward f<sub>*</sub>(ϥ ⋅ g) = f ⋅ ϥ ⋅ g ∈ Hom(C, B), and we're done.

    We will say my diagram commutes.

    Yay!
    Reply With Quote  
     

  25. #24  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    OK, so we (if there is still a "we") encountered Hom-sets which we thought of alternatively as all the arrows out of a fixed object, and all the arrows into a fixed object. These were the images of the Hom-functors Hom(A, -) (covariant) and Hom(-, A) (contravariant, respectively.

    I should really go on and talk about limits next, using the notion of initial and terminal objects as a bridging concept.

    However, I also promised to say something more about functors, so let's do this first. Suppose the functor U: Grp → Set. Since G ∈ Grp is a structured set, we may assume that UG ∈ Set has in some sense lost the structure, specifically the group operation. The functor U is called the "forgetful functor". It isn't very interesting.

    Now consider, though, the functor F: Set → Grp. Now functors are not very clever, they certainly lack the ability to conjure up the group operation and the group axioms and apply them to a set.

    But don't panic! We know what we have here, it's called the "free group"; it is a set together with the operation of element juxtaposition subject to the following constraints.

    Let S ∈ Set, and let FS ∈ Grp be a free group. Then for each a ∈ S, the element aa ∈ FS may be written as a<sup>2</sup>. There is also a unique element b such that ab = ( ).

    The free group element ab is called a "word, and the element ( ) is called the "empty word". It is natural, in the above circumstance, to set ab = aa<sup>-1</sup> = ( ). This is, after all, how the inverse is defined in a standard group. Notice by the above that no element can be written next to itself or to its inverse.

    The functor F is called the "free functor" for this reason. No doubt we could dream up a whole list of dual pairs of free and forgetful functors. This "is left as an exercise for the reader"!!
    Reply With Quote  
     

  26. #25  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    So when you say F and U are dual, do you mean that we have a "natural isomorphism" (whatever that means) between Hom(F(X),G) and Hom(X,U(G))? I mean, we do in this case, because a map from X to the underlying set of G uniquely determines a homomorphism from F(X) to G, as X generates F(X), and any map F(X) to G restricts to a unique map from X to G, so there's a correspondence. But is this the general definition?

    Also, I think this is usually where I begin to get tripped up in category theory. What is the appropriate sense of "natural isomorphism" that describes the duality between F and U?
    Reply With Quote  
     

  27. #26  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    OK, this is my second attempt at a response. My first was terribly misleading, so if anyone read it, I suggest you forget what you read
    Quote Originally Posted by serpicojr
    So when you say F and U are dual, do you mean that we have a "natural isomorphism" (whatever that means) between Hom(F(X),G) and Hom(X,U(G))? I mean, we do in this case, because a map from X to the underlying set of G uniquely determines a homomorphism from F(X) to G, as X generates F(X), and any map F(X) to G restricts to a unique map from X to G, so there's a correspondence. But is this the general definition?
    It was a bit naughty of me to use the word "dual" in this context. The construction you wrote is known as an "adjunction", so-named because of its notational resemblance to the adjoint operator equation.

    One says that U is left adjoint to F (F right adjoint to U) since, as you say, Hom(FX, G) ≅ Hom(X,UG). And for any pair of functors going in opposite directions, I will have an iff in the above.

    I shan't say any more on this at present, but it's a fun thing to talk about after a bit more groundwork
    What is the appropriate sense of "natural isomorphism" that describes the duality between F and U?
    Yes, adjunction, Strictly, duality arises as follows; a left adjoint preserves all colimits in its codomain, a right adjoint preserves all limits in its domain.

    So now we need to know what naturality, limits and colimits are, right?

    I guess that'll be next, then
    Reply With Quote  
     

  28. #27  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    Gotcha. I like the analogy to adjoint linear operators.
    Reply With Quote  
     

  29. #28  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    Before I take my medicine, and try to make sense of algebraic number theory, I want to say a few words about the category theoretic notion of limits. But first this, and quickly, as it isn't very interesting. Recall we talked about the Hom-sets of the form Hom(A, B), Hom(A, c),.... as being the set of all the arrows out of A, and also the Hom-sets Hom(b, A), Hom(C, A) as being the set of all the arrows into A.

    The definition of an "initial" object in a category, (if it exists) is that object in the category for which there is at least one, and at most one, arrow to every other object in the same category.

    The example I shall use is the least element in a preorder considered as a category whose objects are merely placeholders for any and all elements in a set that can be so ordered.

    A "terminal" object is dual to this; if it exists, it is the greatest such element in a preorder, again considered as a single category.

    A "zero" object, if it exists, is both initial and terminal.

    I did it this way, as it sort of leads on to limits, like this......

    First consider a preordered set, not as a category as above, but as an object in the category of preordered sets. Let some object in this category be preordered by divisibility of its elements. Then I will say that x ≤ y iff x|y.

    Now we remember from school that, if for any pair of elements a and b I can find a common divisor, I will call the largest such divisor as hcd(a, b). By definition I will have that hcd(a, b)|a and hcd(a, b)|b. And if there is some c such that c|a and c|b, then of neccesity c|hcd(a, b). Let's be posh, and call this the "infimum of a and b

    But this is a preoreder, so I will write hcd(a, b) ≡ a∧b - you'll see why in a bit.

    Now I am going to think of this preorder as a category, and call the symbol ≤ an arrow. Like this

    where the dashed arrow denotes the "of necessity" condition above. Category theorists call this the induced arrow that is unique up to isomorphism. More on this later.

    Now recall that the symbol ∧ I used for the infimum, is also the Boolean AND operator. This gives us a clue as to how to generalize.

    I will say that the operator A x B is a suitable generalization; it includes the infimum in the preorder category, the Cartesian product in the category of sets, the group direct product in the category of groups, the product topology in the category of topological spaces,.... you get the picture.

    So here is this generalization;




    Do I have enough information to say that A x B is a limit object (which it will only be if the dashed arrow in unique up to isomorphism)? Do I even know what I mean by a limit object, unless it is the image of some function or functor? I don't think so, what do you think?


    This getting a bit long, I'll leave it there for now
    Reply With Quote  
     

  30. #29  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,517
    Ah Category theory, my head hurts!!!

    I need more time to digest this, my cat theory is rusty.
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  31. #30  
    Forum Freshman
    Join Date
    May 2008
    Posts
    9
    Quote Originally Posted by Guitarist
    Quote Originally Posted by JaneBennet
    What’s the name for two vector spaces that are “essentially the same” (i.e. for which there exists a bijective linear transformation between them)?
    Isomorphic!
    I suppose homeomorphic topological spaces can also be called "isomorphic" to make the terminology more consistent with category theory.
    Reply With Quote  
     

  32. #31  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    Yeah, right, A.T, we do start to run out of terminology. BUT, the reason that the topological version of "isomorphism" is called a "homeomorphism" is this:

    Suppose that X and Y are topological spaces, and suppose that f: X → Y is continuous. Now suppose that g: Y → X. This will only be a homeomorphism if g is also continuous. It need not be!

    So, although it interrupts my thought-train slightly, let's hammer out the category theoretic version of isomorphism.

    Let C be an arbitrary category, with A, B ∈ C. Further, let id<sub>A</sub> be the identity morphism on A, and id<sub>B</sub> the identity morphism on B. Then, if it is the case that g ⋅ f = id<sub>A</sub>, and id<sub>B</sub> = f ⋅ g, then one says that f and g are mutual inverses, hence A and B are isomorphic under this mapping.

    As we are doing category theory, we may not assume that A and B are isomorphic under all mappings
    Reply With Quote  
     

  33. #32  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    I'm eagerly awaiting the arrival of limits!

    Do you have a specific goal in mind? I'd love to learn about abelian categories, if you're open to suggestion.
    Reply With Quote  
     

  34. #33  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    My goal (other than self-aggrandizement) to get to natural transformations adjunctions and monads. Abelian categories are rather fun, but conceptually hard (for me, at least). But we have a bit of work ahead of us yet.

    I doubt I shall get it all done, but we'll see.

    For now I have a slight timing problem. Every mid-summer we host a massive party in aid of the charity that supports Mary-Bernadette's severely handicapped brother. This is not as pious as it sounds; everyone eats too much, drinks too much and has an outrageously good time, but it takes a lot of work.

    And following that, we are camping for a few days to recover. I may have some time Sunday night; if I do, I have some questions for the algebraic number theory thread which I shall post then.

    In short, if I am silent for a bit, it doesn't mean I have lost interest.
    Reply With Quote  
     

  35. #34  
    Forum Ph.D.
    Join Date
    Apr 2008
    Posts
    956
    I’ve just read a brief description of categories and functors in a chapter of a book on algebraic topology :-D so let me see if I can recapitulate the main points in this thread (possibly in different words).

    A category is a collection of sets called objects together with functions between the objects called morphisms. If X and Y are objects in a category, the set of all morphisms from X to Y is denoted Hom(X,Y).

    Let C and D be categories. Suppose we have a function F:CD and for every morphism f between two objects in C we have a morphism F<sub>f</sub> between the two corresponding objects in D; further, if i is the identity morphism on an object XC, then F<sub>i</sub> is the identity morphism on the object F(X) ∊ D. Then, given X, Y, ZC with f ∊ Hom(X,Y) and g ∊ Hom(Y,Z),

    (i) if F<sub>f</sub> ∊ Hom(F(X),F(Y)), F<sub>g</sub> ∊ Hom(F(Y),F(Z)) and F<sub>g○f</sub> = F<sub>g</sub>○F<sub>f</sub>, F is called a covariant functor.

    (ii) if F<sub>f</sub> ∊ Hom(F(Y),F(X)), F<sub>g</sub> ∊ Hom(F(Z),F(Y)) and F<sub>g○f</sub> = F<sub>f</sub>○F<sub>g</sub>, F is called a contravariant functor.

    If F:CD is a functor and D is a category of a simpler structure than C, F is called a forgetful functor. For example, C might be the category of topological spaces with continuous functions as morphisms and D the category of sets whose morphisms are ordinary set fuctions.
    Reply With Quote  
     

  36. #35  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    Hi Jane! Yeah, Ive been meaning to get back to this thread. Frankly speaking, I stalled because I found myself unable to complete a proof I need to continue.

    Lemme try again tonight.

    Regarding your post: It is not correct to state, as you did, that each and every categorical object is a set. Where the objects in a category are structured (or unstructured) sets, the category is called "concrete". I gave an example of a non-concrete category, the preorder category, whose objects may be, say. set elements, and whose morphisms are arrows of the form, ≤

    Second, although I cannot say your characterization of the co- and contravariant functors is wrong, I don't like it so well. I guess it's just personal preference, though.

    Oh, for function/arrow composition, enclose #8901 in & ; like this g ⋅ f.
    Reply With Quote  
     

  37. #36  
    Forum Ph.D.
    Join Date
    Apr 2008
    Posts
    956
    You are right, the objects in a category are not merely sets, but sets equipped with structures. That’s what I meant but the words slipped out of me.

    I suppose the definition I’ve given of covariant and contravariant functors are less intuitive than your diagrammatic method, but I’m following the definition given in my book (A First Course in Algebraic Topology (2005) (2nd edition) by B.K. Lahiri). I actually find Lahiri’s definition easier to follow than the diagrammatic approach.

    As for the circle denoting composition of functions, I use &#*9675; (I’ve also used &#*8728; but I’ve found that while this displays okay on IE it doesn’t display very well on Firefox). I prefer the circle to the dot (which BTW can also be typed with ALT+0183). I guess it's just personal preference, though.
    Reply With Quote  
     

  38. #37  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    Quote Originally Posted by Guitarist
    Second, although I cannot say your characterization of the co- and contravariant functors is wrong, I don't like it so well. I guess it's just personal preference, though.
    I think her definitions are not only just fine but are standard.

    Quote Originally Posted by JaneBennet
    You are right, the objects in a category are not merely sets, but sets equipped with structures.
    No, the point is that the objects don't even have to be sets.

    Quote Originally Posted by JaneBennet
    I prefer the circle to the dot.
    Same here! It was taught the circle for composition.
    Reply With Quote  
     

  39. #38  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    OK, let's grab this one by the throat, as it tells us something important about our our theory (even though it interrupts my thought-train about limits).

    Consider first a set with preorder. Then I may say this is an object in the category of preordered sets, whose morphisms are monotone functions (i.e. order-preserving functions).

    But, looking at the preorder axioms, I find they differ in no essential respect from the axioms of our theory. In which case, I will form the category which is the "notional" preordered set, whose objects are the "notional" elements in this category and whose category-theoretic morphisms are arrows of the form ≤.

    This illustrates that out theory cares little about the nature of objects - they are merely anchors for what our theory really cares about, the arrows.

    Here's another, rather dissimilar example. I may think of the category of groups as the collection of objects - sets with a group structure - whose morphisms are group homomorphisms.

    Once again, looking at the group axioms, I see there is no essential difference between these and the axioms of our theory.

    Accordingly, I will say that the "notional" group is a 1-object category whose morphisms are the "notional" group elements under group multiplication. This may be made more clear by using the perfectly standard notation L<sub>g</sub>(h) = gh (left multiplication) and R<sub>g</sub>(h) = hg (right multiplication).

    There is no way that either of the alternative ways of looking at the preorder category and the group category can be thought of as structured sets.

    I repeat; in our theory, arrows are all, objects are useful book-keeping devices, nothing more.
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •