Re: Finite sets and injective maps

Re: Finite sets and injective maps

[Andrej Bauer]

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

Re: Finite sets and injective maps

[Claudio Hermida]

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

Re: Finite sets and injective maps

[Steve Lack]

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
>
>

Re: Finite sets and injective maps

[Paul Levy]

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

Re: Finite sets and injective maps

[Francois Lamarche]

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
>

Re: Finite sets and injective maps

[Peter Selinger]

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
>
>

Re: Finite sets and injective maps

[Sam Staton]

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
>
>

Finite sets and injective maps

[Andrej Bauer]

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