category of finite sets and functions / injections

category of finite sets and functions / injections

[Paul Blain Levy]

Hi,

The following statements seem plausible.

1.

Let Fin be the category of natural numbers and functions, i.e. the full
subcategory of Set on natural numbers, identifying n with {0, ... , n-1}.

For i+1 < n, let swap_i be the function n --> n that swaps i with i+1.

For i <= n, let discard_i be the function n --> n+1 that increments
everything >= i.

For i < n, let copy_i be the function n+1 --> n that?? decrements
everything > i.

Then the category Fin (not monoidal category, just category) is
generated by these operations, subject to a list of equations that treat
every possible pair of
operations.

2.

The same for the category of natural numbers and injections, using just
swap and discard.

3.

The same for the category of natural numbers and bijections, using just
swap.

Statement 3 is a standard theorem presenting the symmetric group.?? Is
there a reference for statements 1 and 2?

Paul



[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Re: category of finite sets and functions / injections

[Nicolai Kraus]

Hi Paul,

I think this is related to the [augmented] simplex category Delta.
This category has as objects [-1], [0], [1], ..., where [n] = {0,1,...,n},
and non-decreasing maps as morphisms. In this context, the maps
that you call "discard" and "copy" are referred to as "face maps"
and "degeneracy maps", and it's a standard lemma that face and
degeneracy maps generate Delta (the relevant equations are known
as the "simplicial identities").
The difference to your category in (1) is that you also want "swap".
I think you can write every function k -> m in your category (1) as
a bijection k -> k followed by a non-decreasing map k -> m, thus
your first statement should follow from the combination of the
statements for Delta and your (3).

Similarly to Delta, one has Delta_+, same objects as Delta but with
morphisms only the strictly increasing (= non-decreasing and
injective) maps; and it's again a standard lemma that these morphisms
are generated by the face maps.

  From this, you also get normal forms for the decomposition of functions;
what you get is that any function f: k -> m can be written as a
composition of a couple of swaps, then discards, then copies:

f = copy_i1 . ... . copy_in . discard_j1 . ... . discard_jp . swap_k1
... . swap_kq

https://ncatlab.org/nlab/show/simplex+category

Nicolai


On 13/08/18 20:41, Paul Blain Levy wrote:
> Hi,
>
> The following statements seem plausible.
>
> 1.
>
> Let Fin be the category of natural numbers and functions, i.e. the full
> subcategory of Set on natural numbers, identifying n with {0, ... , n-1}.
>
> For i+1 < n, let swap_i be the function n --> n that swaps i with i+1.
>
> For i <= n, let discard_i be the function n --> n+1 that increments
> everything >= i.
>
> For i < n, let copy_i be the function n+1 --> n that?? decrements
> everything > i.
>
> Then the category Fin (not monoidal category, just category) is
> generated by these operations, subject to a list of equations that treat
> every possible pair of
> operations.
>
> 2.
>
> The same for the category of natural numbers and injections, using just
> swap and discard.
>
> 3.
>
> The same for the category of natural numbers and bijections, using just
> swap.
>
> Statement 3 is a standard theorem presenting the symmetric group.?? Is
> there a reference for statements 1 and 2?
>
> Paul
>



[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Re: category of finite sets and functions / injections

[Richard Garner]

Hi Paul,

Your (1) is Theorem 4.2 in

Marco Grandis, Finite sets and symmetric simplicial sets, Theory and Applications of Categories, Vol. 8, 2001, No. 8, pp 244-252.

Richard


On Tue, Aug 14, 2018, at 5:41 AM, Paul Blain Levy wrote:
> Hi,
>
>  The following statements seem plausible.
>
>  1.
>
>  Let Fin be the category of natural numbers and functions, i.e. the full
>  subcategory of Set on natural numbers, identifying n with {0, ... , n-1}.
>
>  For i+1 < n, let swap_i be the function n --> n that swaps i with i+1.
>
>  For i <= n, let discard_i be the function n --> n+1 that increments
>  everything >= i.
>
>  For i < n, let copy_i be the function n+1 --> n that?? decrements
>  everything > i.
>
>  Then the category Fin (not monoidal category, just category) is
>  generated by these operations, subject to a list of equations that treat
>  every possible pair of
>  operations.
>
>  2.
>
>  The same for the category of natural numbers and injections, using just
>  swap and discard.
>
>  3.
>
>  The same for the category of natural numbers and bijections, using just
>  swap.
>
>  Statement 3 is a standard theorem presenting the symmetric group.?? Is
>  there a reference for statements 1 and 2?
>
>  Paul
>

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]