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