Comcategories and Multiorders
May 30, 2015
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.
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 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
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.
A multiorder is a comcategory satisfying the following conditions.
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
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.
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.
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.
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
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
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
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
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
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
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).
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
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
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.