You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.
Carlos Zapata-Carratala (May 04 2022 at 01:18):I am currently working on higher arity generalizations of category-like structures and I would like to gether some sentiment from this community about multisets vs tuples. Suppose one is not interested in sequential information, e.g. focus on counting, hypergraph topology, etc., my question is: are there any general reasons (other than tradition) to use n-tuples over multisets of fixed cardinality n to encode the primitive notion of a collection of n (possibly repeating) elements?
The main example I have in mind are homsets in categories: in the standard definition of category homsets are defined on 2-tuples of objects so that C(A,B) =/= C(B,A), which is convenient when thinking of morphisms as directed links between objects. One could define an "undirected" category so that given a pair of objects A and B only the homset C(AB), where AB denotes a multiset of cardinality 2, is defined. As far as I can see, all the usual notions of categories (composition, associativity, identities) appy in this "undirected" setting.
In a higher arity generalization of a category homsets may take the form C(ABCD...) where n-ary morphisms are defined on multisets of objects of cardinality n. This approach seems to allow us to preserve a great deal of the compositional structure of categories into the higher arity realm while relaxing the rigidity of sequentiality imposed by tuples. Can you see any major issues with this approach?
Zhen Lin Low (May 04 2022 at 02:15):It is unclear to me what kinds of examples you have in mind, so it is difficult to judge whether the approach has "major issues".
Zhen Lin Low (May 04 2022 at 02:30):But here is something to think about. If there is some kind of "undirected" analogue of the notion of category it should be a generalisation of the notion of groupoid. In a groupoid there is certainly a canonical bijection between Hom(A, B) and Hom(B, A), and if we take Hom(A, B, ..., Z) to be the set of tuples of morphisms A → B, B → C, ..., Y → Z, then there are canonical bijections between e.g. Hom(A, B, C) and Hom(C, A, B). But then now we have two potentially different bijections between Hom(A, B, B) and Hom(B, A, B), induced by the canonical bijection between Hom(A, B, C) and Hom(C, A, B) or Hom(B, A, C) after substituting C = B. This ambiguity means it is not feasible to think of Hom(A, B, ..., Z) as being indexed by a plain multiset (A, B, ..., Z).
Ralph Sarkis (May 04 2022 at 07:36):I vaguely remember a discussion about "undirected" categories on here (more than a year ago), but I couldn't find it.
Morgan Rogers (he/him) (May 04 2022 at 08:37):Categories of relations (e.g. allegories) have the form that you describe @Carlos Zapata-Carratala, although as @Zhen Lin Low pointed out, if you want to compose relations where one of the codomains is repeated you have to be careful about which way around the relation is, at which point the set might as well be ordered.
Fabrizio Genovese (May 04 2022 at 11:47):Carlos Zapata-Carratala said:
I am currently working on higher arity generalizations of category-like structures and I would like to gether some sentiment from this community about multisets vs tuples. Suppose one is not interested in sequential information, e.g. focus on counting, hypergraph topology, etc., my question is: are there any general reasons (other than tradition) to use n-tuples over multisets of fixed cardinality n to encode the primitive notion of a collection of n (possibly repeating) elements?
The main example I have in mind are homsets in categories: in the standard definition of category homsets are defined on 2-tuples of objects so that C(A,B) =/= C(B,A), which is convenient when thinking of morphisms as directed links between objects. One could define an "undirected" category so that given a pair of objects A and B only the homset C(AB), where AB denotes a multiset of cardinality 2, is defined. As far as I can see, all the usual notions of categories (composition, associativity, identities) appy in this "undirected" setting.
In a higher arity generalization of a category homsets may take the form C(ABCD...) where n-ary morphisms are defined on multisets of objects of cardinality n. This approach seems to allow us to preserve a great deal of the compositional structure of categories into the higher arity realm while relaxing the rigidity of sequentiality imposed by tuples. Can you see any major issues with this approach?
It will make a big difference imho if at some point you plan to implement this or not. Computers like tuples much more than multisets, in general*. Also, as I think @Zhen Lin Low already said, you could also use tuples + symmetries that allow you to shuffle things around. Tuples + symmetries form a groupoid and, in some way, this allows you to work as if you were working with multisets but at the same time it allows you to be more explicit about them.
*By this I mean that a good 40% of day-to-day programming is about manipulating lists of things, and there are countless tools and libraries developed to operate on lists in any possible way one can imagine. The same cannot be said of multisets.
Carlos Zapata-Carratala (May 04 2022 at 12:00):Fabrizio Genovese said:
It will make a big difference imho if at some point you plan to implement this or not. Computers like tuples much more than multisets, in general*. Also, as I think Zhen Lin Low already said, you could also use tuples + symmetries that allow you to shuffle things around. Tuples + symmetries form a groupoid and, in some way, this allows you to work as if you were working with multisets but at the same time it allows you to be more explicit about them.
*By this I mean that a good 40% of day-to-day programming is about manipulating lists of things, and there are countless tools and libraries developed to operate on lists in any possible way one can imagine. The same cannot be said of multisets.
Yes, I completely agree. There will be a big difference for computational implementation. Our modern digital computers are very sequential machines deep down.
Carlos Zapata-Carratala (May 04 2022 at 12:31):Morgan Rogers (he/him) said:
Categories of relations (e.g. allegories) have the form that you describe Carlos Zapata-Carratala, although as Zhen Lin Low pointed out, if you want to compose relations where one of the codomains is repeated you have to be careful about which way around the relation is, at which point the set might as well be ordered.
Yes, using the multiset approach for homsets of repeated objects seems like a potential issue. As far as I can see there is a trade-off: either you insist that all your morphisms bind different objects (no endomorphisms) or you allow for repeated objects in which case the ambiguity for composition is encoded in permutations of repeated objects shared between morphisms. I can see that tuples are efficient in doing away with this issue at the cost of introducing "a priori" sequentiality.
Morgan Rogers (he/him) (May 04 2022 at 13:02):There could be an interesting version of this idea with an antisymmetry condition that forces C(AB...) to be trivial (a one-element set) whenever there are repeated indices.
Simon Burton (May 05 2022 at 01:05):Carlos Zapata-Carratala said:
The main example I have in mind are homsets in categories: in the standard definition of category homsets are defined on 2-tuples of objects so that C(A,B) =/= C(B,A), which is convenient when thinking of morphisms as directed links between objects. One could define an "undirected" category so that given a pair of objects A and B only the homset C(AB), where AB denotes a multiset of cardinality 2, is defined. As far as I can see, all the usual notions of categories (composition, associativity, identities) appy in this "undirected" setting.
Sounds good to me: categories are to directed graphs as undirected categories are to undirected graphs.. Also, this reminds me of dagger categories.
Carlos Zapata-Carratala (May 05 2022 at 10:57):Simon Burton said:
Sounds good to me: categories are to directed graphs as undirected categories are to undirected graphs.. Also, this reminds me of dagger categories.
That was my intuition behind that example too. Higher arity generalizations of categories will take hypergraphs (whether directed or undirected).
Simon Burton (May 05 2022 at 12:50):So my next question is, what are the structure preserving morphisms between undirected categories (ucategories) ? It would seem that these morphisms would be directed, which just comes from the underlying use of sets and functions. So instead of "structure preserving morphisms", we would want some kind of "structure relating umorphisms" between ucategories. Right? I'm guessing these things look like (labelled? simplicial?) cobordisms between ucategories, where we are thinking of a ucategory as some kind of labelled simplicial set.
Carlos Zapata-Carratala (May 05 2022 at 20:42):Simon Burton said:
So my next question is, what are the structure preserving morphisms between undirected categories (ucategories) ? It would seem that these morphisms would be directed, which just comes from the underlying use of sets and functions. So instead of "structure preserving morphisms", we would want some kind of "structure relating umorphisms" between ucategories. Right? I'm guessing these things look like (labelled? simplicial?) cobordisms between ucategories, where we are thinking of a ucategory as some kind of labelled simplicial set.
I haven't thought much about the morphisms between these higher arity ucategories since I haven't settled on a definition yet but the cobordism picture makes sense. I also think that in direct analogy with the case of functors for categories you would need to define "hypergraphs of edges" in some sense too.
Nathanael Arkor (May 05 2022 at 21:44):If you want an undirected notion of category, doesn't the notion of [[groupoid]] suffice?
Amar Hadzihasanovic (May 06 2022 at 06:33):I think saying that "an undirected category is to an undirected graph what a category is to a directed graph" is incomplete, because you fail to specify what it is that you want to be able to compose. For a category, what matters is the ability to compose finite paths in a directed graph into single edges.
Amar Hadzihasanovic (May 06 2022 at 06:34):So in an undirected graph, you have different options.
You may still want to compose finite paths. But to speak of a path in an undirected graph, you are implicitly using a directed representation, where an edge is represented with a pair of directed edges going in opposite directions.
Amar Hadzihasanovic (May 06 2022 at 06:35):And then what you get, I think, would be exactly a dagger category.
Amar Hadzihasanovic (May 06 2022 at 06:35):Or a groupoid if you decide that going back and forth the same edge is the same as doing nothing.
Amar Hadzihasanovic (May 06 2022 at 06:37):But if what you are saying is that you want to replace the tuple A, B with the multiset AB, then you actually don't have the ability to distinguish between the direction in which you traverse an edge.
Amar Hadzihasanovic (May 06 2022 at 06:41):So what you could do, at best, is try to compose the support of a finite path, i.e. a connected set, or a list of edges... but what do you compose them to?
Amar Hadzihasanovic (May 06 2022 at 06:45):For a path, you have a notion of endpoints, so you compose to an edge between the endpoints. If you just look at the support of the path, you don't. So e.g. should the composite of an edge between A,B with an edge between B,A be a loop on B, or a loop on A, or something else?..
Amar Hadzihasanovic (May 06 2022 at 06:52):The only way I can conceivably think of something that makes sense would be to introduce some "higher homotopies" into your graph and say something like:
You can compose any connected subgraph, and its composite is a single-edge subgraph, together with a homotopy from the connected subgraph onto its composite.
Amar Hadzihasanovic (May 06 2022 at 06:56):Then, to get something that is “1-category-like”, you kill all the higher homotopies (make it so that “the space of contractions onto the composite of a subgraph is contractible”)...
Carlos Zapata-Carratala (May 06 2022 at 12:10):Nathanael Arkor said:
If you want an undirected notion of category, doesn't the notion of [[groupoid]] suffice?
Well the game here is not to aim for undirected (that's just a side-effect) but to use multisets of fixed cardinality instead of tuples in the basic definition of category, which then seems to extend to higher arity morphisms.
Carlos Zapata-Carratala (May 06 2022 at 12:21):Amar Hadzihasanovic said:
For a path, you have a notion of endpoints, so you compose to an edge between the endpoints. If you just look at the support of the path, you don't. So e.g. should the composite of an edge between A,B with an edge between B,A be a loop on B, or a loop on A, or something else?..
With the obvious definition of (unoriented) concatenation of paths there is no ambiguity in the sense you claim since edges between A,B and B,A are the same: edges of the "multihomset" AB. Without invoking any higher homotopy, couldn't this notion of concatenation of (unoriented) paths work just fine: two undirected paths (chains of edges) can be composed if they share exactly one end-vertex. You could extend this definition to account for sharing the two end-vertices by making the composition double-valued or simply giving two possibilities. In your example, given two edges f,h on vertices AB you can take the one-end-vertex composition in two possible ways and obtain a loop in AA and a lopp in BB.
Amar Hadzihasanovic (May 06 2022 at 12:45):Ok, I agree: if we place restrictions on composition (e.g. we can compose only “linear strings of edges”) or if we let composition be multi-valued, then it could work, but at least in the latter case I think you wouldn't get anything substantially different from a dagger category.
Amar Hadzihasanovic (May 06 2022 at 12:47):As in, you would have the exact same data as a dagger category, but you wouldn't allow yourself to compose a path with a specific orientation, and instead you would let composition return the set of composites of all directed paths ranging over all suitable orientations of the edges.
Amar Hadzihasanovic (May 06 2022 at 12:58):(Actually I'm not sure of this, I'd need to think more...)
Carlos Zapata-Carratala (May 06 2022 at 13:42):Amar Hadzihasanovic said:
Ok, I agree: if we place restrictions on composition (e.g. we can compose only “linear strings of edges”) or if we let composition be multi-valued, then it could work, but at least in the latter case I think you wouldn't get anything substantially different from a dagger category.
In that case the closest analogue is a groupoid in particular.
Morgan Rogers (he/him) (May 06 2022 at 14:10):Following up on the "categories are to directed graphs as..." idea, I would propose starting by working out what you want a free undirected category on an undirected graph G to be. You can just take paths, but that's not so interesting when you always can put an ordering on paths with labelled end-points, and as has been discussed it seems to reduce to groupoids.
One alternative possibility would be to have, rather than hom-sets defined on pairs, have hom-multisets defined on all finite multisets of vertices, where an element of hom(ABC...) is an undirected graph whose vertex set is (ABC...), equipped with a graph homomorphism to G which preserves the labelling of vertices. The simplest notion of composition would be disjoint union, which makes it a total operation. An alternative is to make the composition relational, so that you can keep track of all of the possible ways of gluing graphs along vertices in the intersection of two multisets?
Morgan Rogers (he/him) (May 06 2022 at 14:11):Or you could take a disjoint union of all of the possible gluings if you don't mind things blowing up really fast ;)
Carlos Zapata-Carratala (May 06 2022 at 16:56):Morgan Rogers (he/him) said:
One alternative possibility would be to have, rather than hom-sets defined on pairs, have hom-multisets defined on all finite multisets of vertices, where an element of hom(ABC...) is an undirected graph whose vertex set is (ABC...), equipped with a graph homomorphism to G which preserves the labelling of vertices. The simplest notion of composition would be disjoint union, which makes it a total operation. An alternative is to make the composition relational, so that you can keep track of all of the possible ways of gluing graphs along vertices in the intersection of two multisets?
That's precisely my approach when defining higher arity generalizations of morphisms as undirected hyperedges. The fun starts when you try to think of hypergraph rewrite systems as generalizations of compositions (my current research). I wanted to keep the discussion focused on the "tuples vs fixed cardinality multisets" topic first just to see how much mathematical baggage one can leave behind when generalizing these sort of structures.