Comcategories and Multiorders v9

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

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.

A multiorder is a comcategory satisfying the following conditions.

- There is at most one multiarrow with given head and ground.
- Each object has a unit multiarrow
- 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.

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

for all

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

- [transitive, partitive] = finite pointed sets.
- [transitive, partitive] = finite sets (head = minimum).
- [transitive, partitive] = finite pointed multisets.
- [transitive, partitive] = finite multisets (head = minimum).

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

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.