Comcategories and Multiorders

May 30, 2015

Gus Wiseman

Abstract

Multiorders are related to comcategories (co-multi-categories) in the same way that partial orders (posets) are related to categories. There is no consensus in the literature concerning the intended meaning of “multicategory”, and the algorithmic complexity involved in our new formulation is also regrettable. While the fundamental equivalence between decompositions and contractions of triangles in multiorders can be discussed in many ways, the program established here is intended to be sufficient to the exhaustion of that discussion. Our many applications and examples come primarily from the domain of enumerative combinatorics.

Multiset/sequence notation

 denotes the set of all non-empty finite sequences of elements of a set  while  denotes the set of all finite non-empty weakly-increasing sequences of elements of a totally ordered set  The contents of square-brackets may comprise either sets, sequences, or multisets. The two special symbols  have the following meanings.

A definition of comcategory

A comcategory  is comprised of a totally ordered set  of objects, a set  of multiarrows with two functions

whose dual image may be summarized

and a multiproduct  having the following character of a composition operation. A pair

is composable if

and the set of all composable pairs is denoted . Composition is a function  for which we use the notation

when this is not ambiguous. Naturally one should have

where  connotes the obvious transformation

If  is a sequence of multiarrows, define a (strict) total ordering relation  on the index set  by letting  iff

 or

 and

If  is the -ordered sequence of indices, we define the semi-ordering  to be the reordering

The comcategory analogue of associativity is imposed by the multiproduct axiom

apprised for every pair  such that  Equivalently,

Given a totally-ordering of the object-set, any multicategory, symmetric or non-symmetric, can be made into an equivalent comcategory. For example, assume  is a totally ordered set of objects. The comcategory of rooted sequences has a multiarrow

for every pair  Formally constructing the multiproduct of composable pairs and verifying the multiproduct axiom would be a difficult surgery, but the following picture may be entirely satisfying.

Multiorders

A multiorder is a comcategory  satisfying the following conditions.

1. There is at most one multiarrow with given head and ground.
2. Each object  has a unit multiarrow 
3. A multiarrow  is a unit iff

A triangle is a triple  satisfying the following three (obvious) boundary conditions.

Notice that the set   of all triangles in a comcategory  does not depend on the particular multiproduct (composition) operation, and in the case of multiorders a triangle is simply a composable pair together with its multiproduct (ie. ).

It is useful and traditional to suppose a (multi)arrow in a (com)category to belong to the common domain of two functions (viz.  and ), and we will prefer to regard triangles in comcategories in the same way. Hence the meaning of our three pseudo-functions (composite, domain, codomain) will be such that

for all

A decomposition is a pair

A contraction is a pair

The set of decompositions and the set of contractions, both of which involve only triangles in  are denoted  and  respectively.

Theorem. Combinatorial equivalence

Suppose  is a multiorder. If  define two functions

Noting that  is a contraction, it remains to construct two more functions  and  so that these four maps together comprise inverse bijections

Suppose  Since the sequence  is a permutation of  there is at least one way to choose, for each entry  of  a subsequence  of  such that  is a sequence of triangles for which  is a permutation of  Moreover there is a unique such choice (this is the hard part of the proof) satisfying  namely  We then have

To summarize with a picture, let  be the set of all quadruples  where  is a contraction in bijection with a decomposition . Writing

for all  we have the following commutative diagram.

Applications

Contraction category and decomposition comcategory

If a triangle in a multiorder  is regarded as a morphism

or as a multiarrow

then the composable pairs, whether for morphisms of a category or for multiarrows of a comcategory, are respectively all pairs  for  and all pairs  for  Setting

completes the definitions of a contraction category of a multiorder, and of a decomposition comcategory of a multiorder. Compare the well-known constructions of left and right comma-categories.

Lattice-form

For any multiarrow  of a multiorder  the subset of triangles  is a finite partially ordered set with unique minimum and maximum (but not in general a lattice), where the ordering relation is given by

 iff for some  we have

The lattice-form of a multiorder is the indexed family of posets

Incidence algebra and Möbius function

Let  be the set of rational-valued functions with domain . We call  a lattice-form map and denote its arguments by subscripts  For  we have a binary operation  defined by

The correspondence between contractions and decompositions ensures that this operation is associative, and makes  into an algebra which we call the incidence algebra of . Moreover the presence of minimum and maximum triangles means that any lattice-form map that is nonzero on all unit arrows has a compositional inverse. The Möbius function   is the compositional inverse of  where  for all  Compare the well-known constructions of the incidence algebra and Möbius function of a poset. Our (new) Möbius function of a multiorder is related to the (old) Möbius function on intervals of the lattice-form posets by

for all

Examples

Multisets of integers

Let  be the set of positive integers. For  let  be a multiarrow  The multiorder  then has a unique arrow

for each finite multiset  of positive integers. It is easy to see that a distinct triangle  exists for each sequence  of multisets of positive integers whose sequence of minima is weakly increasing. The contraction category  then has a morphism

:

for every such triangle  This is the simplest known category of multisets. An example of a morphism of  is the following.

The following is a picture of the (truncated) lattice-form of

Let  be the Möbius function of  If  then  is equal to the number of distinct permutations of the multiset

Pointed multisets

Assuming  is a totally ordered set, the multiorder of pointed multisets  has a multiarrow  for each pair  with . For any pair  with  we have a triangle

The following is a picture of a sub-poset of the lattice-form of

Integer Partitions

An integer partition of is any finite weakly decreasing sequence of positive integers  where  denotes the reverse-ordered set of positive integers. Let  be the obvious multiorder of integer partitions, where

For each sequence of integer partitions  whose sequence of sums  is weakly decreasing, we have a unique triangle

The following picture shows all morphisms of the contraction category of  restricted to , arranged in a matrix according to source and target.

The following two pictures show the lattice form posets  and

Counterexamples

A multisystem is a pair  where  is a totally ordered set and  is a set of “multiedges”  A multisystem is said to be transitive iff its edges are the multiarrows of a multiorder, where we make the obvious identification  A multisystem  is said to be partitive iff for every pair  satisfying  and , we have  The definition of the set  of triangles, and of the sets  and  of contractions and decompositions, are generalized from multiorders to multisystems in the obvious way.

A multisystem  is said to be contractible iff for all  we have  this implies that the injection  is well-defined. Dually, a multisystem is said to be decomposable iff the inverse injection  is well-defined on  with image contained in  Note that any transitive multisystem is contractible, and any partitive multisystem is decomposable.

Let  be the set of positive integers with the usual total ordering. Each of the following four cases defines a contractible and decomposable multisystem

1. [transitive, partitive] = finite pointed sets.
2. [transitive, partitive] = finite sets (head = minimum).
3. [transitive, partitive] = finite pointed multisets.
4. [transitive, partitive] = finite multisets (head = minimum).

Clutters

A clutter  is a finite connected spanning hypergraph  where no edge  is a subset of any other edge. Let  be the multisystem of all clutters, where

Without loss of generality, we may assume that  is the set of all finite subsets of positive integers, ordered lexicographically. The reader should be able verify that  is neither transitive nor partitive, but is contractible. That  is not decomposable is somewhat more difficult to demonstrate (please consult the author’s article on the subject).

Strict partitions

A strict partition  is any finite set of positive integers, traditionally sorted in decreasing order. Letting  be the reverse-ordered set of positive integers, and  the set of all strict partitions  It is not hard to show that  is neither transitive nor partitive, but is decomposable. That  is not contractible follows from the observation that, if  is the decomposition given by

then one must have

Open problem

If  is a finite set, let  be the free abelian group generated by the symbols

We have a chain of boundary homomorphisms

and it seems that this construction can be extended inductively in a very natural way. It would be interesting to construct, describe, and characterize the homology groups  of multiorders

Acknowledgement

The author is not supported by academia in any way, and this work was made possible only through considerable ongoing medical and financial support from the United States’ mental health system.