nLab semicategory

Idea

The notion of semicategory or non-unital category is like that of category but omitting the requirement of identity-morphisms.

This generalizes the notions of semigroup, semiring, etc:

• a semigroup is (the hom-set of) a semicategory with a single object;

• a semiring is (the hom-set of) a semicategory enriched in Ab with a single object.

Semicategories, like categories, appear as semipresheaves on the category with two objects and two morphisms.

Definition

Definition

A (small) semicategory or non-unital category $\mathcal{C}$ consists of

• a set $\mathcal{C}_0$ of objects;

• a set $\mathcal{C}_1$ of morphisms (or arrows);

• two functions $s, t : \mathcal{C}_1 \to \mathcal{C}_0$ called source (or domain) and target (or codomain);

  • one writes $f : x \to y$ if $s(f) = x$ and $t(f) = y$;

• a function $\circ \colon \mathcal{C}_1 \times_{t,s} \mathcal{C}_1 \to \mathcal{C}_1$ (composition) from the set of pairs of morphisms such that the target of the first is the source of the second;

such that the following properties are satisfied:

• source and target are respected by composition: $s(g \circ f) = s(f)$ and $t(g\circ f) = t(g)$;

• composition is associative: $(h \circ g)\circ f = h\circ (g \circ f)$ whenever $t(f) = s(g)$ and $t(g) = s(h)$.

Remark

If one added to this definition the existence of a function $i \colon C_0 \to C_1$ such that for all $c \in C_0$ the morphism $i(c)$ is an identity on $c$ under the given composition, then one has the defintion of a category.

However, having identities is just an extra property on a semi-category, not extra structure. For more on this see below at Relation to categories.

Remark

One often writes $hom(x,y)$, $hom_C(x,y)$, or $C(x,y)$ for the collection of morphisms $f : x \to y$; the latter two have the advantage of making clear which category is being discussed. People also often write $x \in C$ instead of $x \in C_0$ as a short way to indicate that $x$ is an object of $C$. Also, some people write $Ob(C)$ and $Mor(C)$ instead of $C_0$ and $C_1$.

Definition

For $\mathcal{C}, \mathcal{D}$ two semicategories, a semi-functor $F \colon \mathcal{C} \to \mathcal{D}$ is a pair of functions $F_0 \colon \mathcal{C}_0 \to \mathcal{D}_0$, $F_1 \colon \mathcal{C}_1 \to \mathcal{D}_1$ that respects all the given structure in the obvious way.

Write $SemiCat$ for the (large) category whose objects are semicategories, and whose morphisms are semifunctors.

Properties

Relation to categories

We discuss the relation of semicategories to categories. (See for instance the beginning of (Harpaz) for a quick review of basics, with an eye towards their generalization to the relation between complete Segal spaces and complete semi-Segal spaces.)

Definition

There is an evident forgetful functor

$$U \colon Cat \to SemiCat$$

from the category Cat of categories to that of semicategories, def. , given simply by forgetting the identity-assigning map $i \colon \mathcal{C}_0 \to \mathcal{C}_1$ in a category.

Definition

For $\mathcal{C}$ a semi-category, def. , write

$$Id(\mathcal{C}_1) \hookrightarrow \mathcal{C}_1$$

for the subset on those morphisms which are endomorphisms on some object $x \in \mathcal{C}_0$ and such that they are neutral elements with respect to composition in $\mathcal{C}$.

Proposition

A semicategory is the semicategory underlying a category, hence is in the image of the functor $U$ of def. , precisely if every object has a neutral endomorphism, hence precisely if the composite diagonal function in

$$\array{ Id(\mathcal{C}_1) &\hookrightarrow& \mathcal{C}_1 \\ & {}_{\mathllap{\simeq}}\searrow & \downarrow^{\mathrlap{s}} \\ && \mathcal{C}_0 }$$

is an isomorphism, where the horizontal function is that of def. .

Moreover, if a semicategory lifts to a category, it does so in a unique way: the functor $U \colon Cat \to SemiCat$ is an injection on isomorphism classes.

Remark

Equivalently one could use the target map instead of the source map in the formulation of prop. .

Remark

The diagram appearing in prop. is a simple version of the univalence condition appearing in definition of a complete semi-Segal space, a semi-category object in an (infinity,1)-category. See there for more on this.

Proposition

The functor $U$ of def. has a left adjoint, which freely adjoins identity morphisms to a semicategory in the obvious way. It also has a right adjoint, which sends a semicategory $S$ to the category whose objects are the idempotents of $S$ and whose morphisms are the morphisms of $S$ that commute suitably with them, as described at Karoubi envelope. Indeed, the monad on Cat generated by this latter adjunction is exactly the monad for idempotent completion, also called Cauchy completion. (Note, however, that this is not a 2-monad, because the right adjoint of $U$ is not a 2-functor.)

Transitive relations

A transitive relation is a semicategory enriched on truth values, or a semicategory $C$ where there is at most one morphism from every object $a$ to object $b$ in $C$

Nerves and semi-simplicial sets

The nerve of a semicategory is a semi-simplicial set which satisfies the Segal conditions.

Examples

Start with the category of metric spaces and short maps. An occasionally useful semicategory can be formed from it by considering the nonempty spaces and strictly contractive functions.

This is a semicategory, since:

• the composition of two strictly contractive functions is strictly contractive
• identity maps are not contractive (they are trivial isometries)

The interest in this semicategory arises from the fact that all morphisms $f : A \to A$ have unique fixed points, by Banach’s fixed point theorem.

In higher category theory

The concept of semicategory has more or less evident analogs and generalizations in higher category theory.

For models of higher categories by simplicial sets, i.e. presheaves on the simplex category (such as Kan complexes, quasi-categories, weak complicial sets) the corresponding semi-category notion is obtained by discarding the degeneracy maps (which are the identity-assigning maps in the simplicial framework), i.e. by considering just presheaves on the subcategory $\Delta_+ \subset \Delta$ on injective morphisms (see the discuss of $\Delta_+$ at Reedy model structure for more details).

Accordingly, there is the semi-category analog of a Segal space, called a semi-Segal space.

Simpson's conjecture says that every $\infty$-category has a model where all composition operations are strict and only the unit laws hold up to coherent homotopies. This would mean that the $\infty$-semicategory underlying any $\infty$-category can always be chosen to be strict.

Related concepts

• dagger semicategory?

• semipresheaf

• regular semicategory

• non-unital ring

• semi-simplicial set

• semi-Segal space

algebraic structure	oidification
magma	magmoid
pointed magma with an endofunction	setoid/Bishop set
unital magma	unital magmoid
quasigroup	quasigroupoid
loop	loopoid
semigroup	semicategory
monoid	category
anti-involutive monoid	dagger category
associative quasigroup	associative quasigroupoid
group	groupoid
flexible magma	flexible magmoid
alternative magma	alternative magmoid
absorption monoid	absorption category
cancellative monoid	cancellative category
rig	CMon-enriched category
nonunital ring	Ab-enriched semicategory
nonassociative ring	Ab-enriched unital magmoid
ring	ringoid
nonassociative algebra	linear magmoid
nonassociative unital algebra	unital linear magmoid
nonunital algebra	linear semicategory
associative unital algebra	linear category
C-star algebra	C-star category
differential algebra	differential algebroid
flexible algebra	flexible linear magmoid
alternative algebra	alternative linear magmoid
Lie algebra	Lie algebroid
monoidal poset	2-poset
strict monoidal groupoid?	strict (2,1)-category
strict 2-group	strict 2-groupoid
strict monoidal category	strict 2-category
monoidal groupoid	(2,1)-category
2-group	2-groupoid/bigroupoid
monoidal category	2-category/bicategory

References

Semicategories were introduced in

• Barry Mitchell, The dominion of Isbell, Transactions of the American Mathematical Society 167 (1972) 319-331 [doi:10.2307/1996142]

Enriched semicategory theory is developed in

• M.-A. Moens, U. Bernani-Canani, F. Borceux, On regular presheaves and regular semi-categories , Cah. Top. Géom. Diff. Cat. XLIII no.3 (2002) pp.163-190. (numdam)

This is turned one notch further in

• Isar Stubbe, Categorical structures enriched in a quantaloid : regular presheaves, regular semicategories , Cah. Top. Géom. Diff. Cat. XLVI no.2 (2005) pp.99-121. (numdam)

Semicategories and semigroups are mentioned in section 2 in

• W. Dale Garraway, Sheaves for an involutive quantaloid, Cahiers de Topologie et Géométrie Différentielle Catégoriques, 46 no. 4 (2005), p. 243-274 (numdam)

Semicategories with an eye towards their generalization to semi-Segal spaces are briefly discussed at the beginning of

• Yonatan Harpaz, Quasi-unital $\infty$-Categories (arXiv:1210.0212)

Structures obtained by further relaxing also the associativity law are discussed in

• Salvatore Tringali, Plots and Their Applications - Part I: Foundations (arXiv:1311.3524)

Topologically enriched semicategories are used for studying some aspects of concurrency theory in computer science. It is necessary to work with semicategories to have functorial definitions of the branching and merging homologies of a concurrent system. A starting point for reading the theory can be the paper

• Philippe Gaucher, Flows revisited: the model category structure and its left determinedness, Cahiers de Topologie et Géométrie Différentielle Catégoriques, vol LXI-2 (2020) (published, arXiv:1806.08197)

Semi-categories, semi-adjunctions and semi-cartesian closed categories have been used to study the lambda calculus since

• Susumu Hayashi, Adjunction of semifunctors: Categorical structures in nonextensional lambda calculus, Theoretical Computer Science Volume 41, 1985, Pages 95-104 doi:10.1016/0304-3975(85)90062-3