(Off-topic) Question about categories
(I'm asking here because I believe there is some overlap between category theory and functional programming cognoscenti...) It has been suggested to me that categories may be a useful framework (more useful than set theory) for conceptualizing things for which there is no well-defined equality relationship. (The discussion is about resources in WWW.) I've done a little digging about category theory, and find some relatively approachable material at: http://www.wikipedia.org/wiki/Category_theory http://www.wikipedia.org/wiki/Class_(set_theory) and nearby. But I'm hitting a mental block with this (and other places I've look don't add anything I can grok). The definition of a category depends on the definition of a morphism, and in particular the existence of an identity morphism for every object in a category. The definition of an morphism is in terms of equality of compositions of morphisms: for f : A -> B we have Id[B]. f = f = f . Id[A] My problem is this: how does it make sense to define an equality of morphisms without some well-defined concept of equality on the underlying objects to which they apply? That is, given object X and an object Y, it is possible to examine them and determine whether or not they are the same object. And if the underlying objects have such a concept of equality, what prevents them from being sets or members of sets? But categories are presented as being more general than sets. Does anyone see the cause of my non-comprehension here? #g ------------ Graham Klyne GK@NineByNine.org
On donderdag, sep 18, 2003, at 14:44 Europe/Amsterdam, Graham Klyne wrote:
My problem is this: how does it make sense to define an equality of morphisms without some well-defined concept of equality on the underlying objects to which they apply? That is, given object X and an object Y, it is possible to examine them and determine whether or not they are the same object.
Yes; there is an equality relation on the objects. The collection of objects of a (small) category forms a set. You can only form sets of things which satisfy an equality relation, because the extensionality axiom, which defines when two sets are equal, is defined in terms of equality of members. By foundation, there has to be an equality relation on the individuals in any such universe of sets.
And if the underlying objects have such a concept of equality, what prevents them from being sets or members of sets?
I don't understand your confusion. The objects can certainly be sets; the category of sets and functions (which is not small, BTW) is the archetypal example. To determine if two sets are equal you use extensionality: sets A and B are equal iff they have equal members. Nothing prevents forming a set of objects either.
But categories are presented as being more general than sets.
They're more general in the sense that: a) the collection of objects can form a proper class, so a large discrete (no non-identity arrows) category is "bigger" than any set; b) the definition of a category involves more data than the definition of a set. To define a set, you only need to specify its elements. To define a category you need to give a collection of objects, an indexed collection of homsets and a composition operator. c) the collection of all sets forms one particular category.
Does anyone see the cause of my non-comprehension here?
AFAICT, the source of your confusion is that you erroneously believed that sets and/or members of sets couldn't (necessarily) be compared for equality, but the fact is they always can, by definition. If the category is large, there are additional issues, but there is still an equality relation on the objects. Does that clear things up? Regards, Frank
But I'm hitting a mental block with this (and other places I've look don't add anything I can grok).
Two things I found useful when learning category theory are: 1) Try reading the definitions as though categories were just graphs: Objects are nodes, morphisms are labelled edges and equality of morphism is modulo some equivalence on lists of labels. (Well, something like that - it's been a while since I played this game and it's most useful for you to work out all the ins and outs of it yourself.) 2) Look for lots and lots of examples of categories. Besides the obvious category of sets, there's domain theory (very useful to help you get a handle on pushouts, initial, final, and the like), and lots and lots of others. (Ask computer scientists for examples though - if you have to learn topology before you can understand the categories that mathematicians like to use, you won't gain much insight.) Actually, these are just two different ways of saying to look beyond the obvious Set category. The value of category theory is in its generalizations and, especially, in its ability to draw parallels between many different situations so looking at any one example for too long will tend to hold you back. -- Alastair Reid www.haskell-consulting.com
hello, i think what is importnat is that one can tell when two arrows are the same (how to specify that of course is tricky in general). equality on objects kind of follows from there. in fact one can describe a category without referring to objects at all: 1. pick a collection of arrows (call it A) 2. pick a sub-collection if A that you will call "identity" arrows (call that I) 3. give the following mappings (these are not arrows!) 3.1 source: A -> I 3.2 target: A -> I 3.3 compose: (A,A) -> A (this one is partial, and has to be defined, when the source and target match as usual). the trick is that essentially objects are represented by the identity arrows on them (as there is a 1-1 correspondance between the two). my favourite way to think of a category is as follows: 1. i think of objects as types 2. i think of an arrow: A -> B as value of type B, that has a free variable of type A 3. i think of composition as substitution hope this helps iavor Graham Klyne wrote:
(I'm asking here because I believe there is some overlap between category theory and functional programming cognoscenti...)
It has been suggested to me that categories may be a useful framework (more useful than set theory) for conceptualizing things for which there is no well-defined equality relationship. (The discussion is about resources in WWW.) I've done a little digging about category theory, and find some relatively approachable material at: http://www.wikipedia.org/wiki/Category_theory http://www.wikipedia.org/wiki/Class_(set_theory) and nearby.
But I'm hitting a mental block with this (and other places I've look don't add anything I can grok). The definition of a category depends on the definition of a morphism, and in particular the existence of an identity morphism for every object in a category. The definition of an morphism is in terms of equality of compositions of morphisms: for f : A -> B we have Id[B]. f = f = f . Id[A]
My problem is this: how does it make sense to define an equality of morphisms without some well-defined concept of equality on the underlying objects to which they apply? That is, given object X and an object Y, it is possible to examine them and determine whether or not they are the same object. And if the underlying objects have such a concept of equality, what prevents them from being sets or members of sets? But categories are presented as being more general than sets.
Does anyone see the cause of my non-comprehension here?
#g
------------ Graham Klyne GK@NineByNine.org
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- ================================================== | Iavor S. Diatchki, Ph.D. student | | Department of Computer Science and Engineering | | School of OGI at OHSU | | http://www.cse.ogi.edu/~diatchki | ==================================================
Graham Klyne wrote, on 18 september 2003 14:44 [...]
But I'm hitting a mental block with this (and other places I've look don't
add anything I can grok). The definition of a category depends on the definition of a morphism, and in particular the existence of an identity morphism for every object in a category. The definition of an morphism is
in terms of equality of compositions of morphisms: for f : A -> B we have Id[B]. f = f = f . Id[A] My problem is this: how does it make sense to define an equality of morphisms without some well-defined concept of equality on the underlying objects to which they apply? That is, given object X and an object Y, it is possible to examine them and determine whether or not they are the same
object. And if the underlying objects have such a concept of equality, what prevents them from being sets or members of sets? But categories are
presented as being more general than sets.
I am not a specialist, but my understanding is as follows: Category Theory is an axiomatic theory: a language with certain primitive notions and relations between these notions. Equality between objects is not a notion of category theory and you will not find any category-theoretic theorem proving that two objects are equal. (You may say that an object has an identity, as given by its identity morphism. A category actually can be defined using morphisms only.) Equality between morphisms however is a central notion of category theory. If you have a concrete category, you have to denote some things as objects, others as morphisms; before exploiting category theory, you have to prove that the objects and morphisms of your concrete category fulfill the category axioms, and for that you may, of course, use the equality relations in your concrete category. Peter J. Veger, Best Netherlands
----- Original Message -----
From: "Graham Klyne"
(I'm asking here because I believe there is some overlap between category theory and functional programming cognoscenti...)
It has been suggested to me that categories may be a useful framework (more useful than set theory) for conceptualizing things for which there is no well-defined equality relationship. (The discussion is about resources in WWW.) I've done a little digging about category theory, and find some relatively approachable material at: http://www.wikipedia.org/wiki/Category_theory http://www.wikipedia.org/wiki/Class_(set_theory) and nearby.
But I'm hitting a mental block with this (and other places I've look don't add anything I can grok). The definition of a category depends on the definition of a morphism, and in particular the existence of an identity morphism for every object in a category. The definition of an morphism is in terms of equality of compositions of morphisms: for f : A -> B we have Id[B]. f = f = f . Id[A]
My problem is this: how does it make sense to define an equality of morphisms without some well-defined concept of equality on the underlying objects to which they apply? That is, given object X and an object Y, it is possible to examine them and determine whether or not they are the same object. And if the underlying objects have such a concept of equality, what prevents them from being sets or members of sets? But categories are presented as being more general than sets.
Does anyone see the cause of my non-comprehension here?
#g
------------ Graham Klyne GK@NineByNine.org
Hi, There's some additional links about category theory in this LtU discussion: http://lambda.weblogs.com/discuss/msgReader$979. Also there's this presentation "Category Theory for Beginners" http://www.cs.toronto.edu/~sme/presentations/cat101.pdf. HTH. Best regards, Daniel Yokomiso. "Honesty is the best policy, but insanity is a better defense." --- Outgoing mail is certified Virus Free. Checked by AVG anti-virus system (http://www.grisoft.com). Version: 6.0.518 / Virus Database: 316 - Release Date: 12/9/2003
participants (6)
-
Alastair Reid -
Daniel Yokomiso -
Frank Atanassow -
Graham Klyne -
Iavor Diatchki -
Peter J. Veger