The category of finite sets and functions may be characterized (up to equivalence) as the category with finite coproducts freely generated from one object. Is there a similar nice characterization for the category of finite sets and _injective_ functions? Best regards, Andrej
Andrej, You can say that finite sets and injective functions is (up-to equivalence) the free symmetric monoidal category with an initial unit, on one generator. I think this is quite well known. I first learnt it from Marcelo Fiore, a long time ago, and we referred to it in our paper Comparing Operational Models of Name-Passing Process Calculi Information and Computation vol 204. 2006. I've also seen John Power refer to the result, e.g. in Semantics for Local Computational Effects MFPS XXII. ENTCS vol 158. 2006. I am intrigued about what you will use the category for. Sam On 4 Dec 2008, at 09:11, Andrej Bauer wrote:
The category of finite sets and functions may be characterized (up to equivalence) as the category with finite coproducts freely generated from one object. Is there a similar nice characterization for the category of finite sets and _injective_ functions?
Best regards,
Andrej
The category of finite sets and injective functions is the symmetric monoidal category freely generated from one pointed object (i.e., from one object A and one arrow I->A, where I is the tensor unit). -- Peter Andrej Bauer wrote:
The category of finite sets and functions may be characterized (up to equivalence) as the category with finite coproducts freely generated from one object. Is there a similar nice characterization for the category of finite sets and _injective_ functions?
Best regards,
Andrej
In Sets+Injective functions (Inj?) the disjoint sum A+B obeys a universal property which is slightly more restricted than coproduct: given two maps A ---> C <--- B such that their pullback is empty, then there exists a unique A+B ----> C with the usual coproduct- filler property. So I guess that if you look for the free category with one generator object, pullbacks, initial object and a bifunctor+natural transformations with that universal property, you will get FInj, but that has to be ascertained. Hope that helps, François On 4 déc. 08, at 10:11, Andrej Bauer wrote:
The category of finite sets and functions may be characterized (up to equivalence) as the category with finite coproducts freely generated from one object. Is there a similar nice characterization for the category of finite sets and _injective_ functions?
Best regards,
Andrej
On 4 Dec 2008, at 09:11, Andrej Bauer wrote:
The category of finite sets and functions may be characterized (up to equivalence) as the category with finite coproducts freely generated from one object. Is there a similar nice characterization for the category of finite sets and _injective_ functions?
It's the coaffine category (i.e. symmetric monoidal category whose unit is initial) freely generated by one object. See the following paper: @article{Petric:substruct, author = {Zoran Petric}, title = {Coherence in Substructural Categories}, journal = {Studia Logica}, volume = {70}, number = {2}, year = {2002}, pages = {271-296}, bibsource = {DBLP, http://dblp.uni-trier.de} } Paul
Dear Andrej, Here are a few: 1. It's the symmetric monoidal category freely generated by a pointed object (i.e. an object X with a map I-->X where I is the unit for the monoidal structure). 2. It's the "symmetric monoidal category with I=0" freely generated by an object. 3. It's the monoidal category freely generated by an object X equipped with an involution s:X^2-->X^2 satisfying the braid relations and a morphism i:I-->X satisfying s.Xi=s.iX. Steve. On 4/12/08 8:11 PM, "Andrej Bauer" <andrej.bauer@andrej.com> wrote:
The category of finite sets and functions may be characterized (up to equivalence) as the category with finite coproducts freely generated from one object. Is there a similar nice characterization for the category of finite sets and _injective_ functions?
Best regards,
Andrej
I thank everyone who answered. The answer is "the free symmetric monoidal category with an initial unit generated by one object". Some were curious to know what I am doing with the category. In a study of generalizations of relational databases with a student of mine we found that a good category to use for describing schemata (shapes of relations) is the category whose objects look like freely generated coproducts and the morphisms are injective functions. So I now know that this category is the freely generated symmetric monoidal category with an initial unit generated by the set of types that may appear in a schema. Thank you. Best regards, Andrej
Andrej Bauer wrote:
The category of finite sets and functions may be characterized (up to equivalence) as the category with finite coproducts freely generated from one object. Is there a similar nice characterization for the category of finite sets and _injective_ functions?
Best regards,
Andrej
There are two universal characterisations of the category of finite sets and injections: I - It is the free symmetric monoidal category on one generator, with an initial unit. II - It is the free symmetric monoidal category on one generator G, with a monoidal indeterminate x: I -> G. In both cases, the symmetric monoidal structure is given by finite coproducts. The general notion of 'monoidal indeterminates' requires some spelling out, but should be clear enough in this simple case. II implies I above; it follows from a general construction of monoidal indeterminates subject to a naturality constraint (which is trivial in this case). Regards, Claudio Hermida
participants (7)
-
Andrej Bauer -
Claudio Hermida -
Francois Lamarche -
Paul Levy -
Sam Staton -
selinger＠mathstat.dal.ca -
Steve Lack