List of "almost"-categories

Question

Can we create a big list of interesting "almost"-categories in the sense that

• we have a collection of objects
• for every pair of objects we have a set of morphisms
• we can compose morphisms

but either

• there are no identity morphisms*
• or the associativity law does not hold

and

• the failure of these laws is not completely trivial, maybe even surprising
• the "almost"-category is not just a contrived example but instead actually appears in mathematical practice?

The last two items mean that I want to exclude boring examples such as "take a transitive relation $R$ which is not reflexive and take a unique morphism $x \to y$ whenever $(x,y) \in R$" or "take a non-associative magma $(X,\cdot)$ / ring / whatever and consider it as a one-object almost-category". These will not be considered as answers since they are not interesting. So I will require in particular that

• there is more than one object
• between two objects there can be more than one morphism

Also, something like "product of a category with a non-associative magma" is not what I am asking for, as this is a contrived example.

My question is related to Example of non-associative composition of morphisms but not identical to it. There, an interesting example was already mentioned: composing paths (indexed by $[0,1]$) in a topological space is not associative. It is only associative up to homotopy. I assume there are many more examples where associativity only holds up to homotopy or isomorphism, but I am curious if there are other interesting examples, i.e. that do not come from weak $2$-categories.

Another example of this type is the category of spans of, say, sets. Objects are sets, and morphisms from $X$ to $Y$ are diagrams of the form $X \leftarrow S \rightarrow Y$, called spans. The composition of two spans $X \leftarrow S \rightarrow Y \leftarrow T \rightarrow Z$ is $X \leftarrow S \times_Y T \rightarrow Z$. This is only associative up to isomorphism.

Background. I am working on some teaching material for category theory. I want to include some non-examples of categories as well, because generally speaking, I think it is a good way to explain a concept by adding also a counterexample. It is easy to give boring counterexamples, as mentioned, but I am interested in more interesting counterexamples, maybe even examples of "almost"-categories where you might first think that it is a category which however turns out to be wrong. I think this will provide an interesting choice for the teaching material since it highlights the importance of checking properties in detail. The example with the path "almost"-category qualifies as such an example, since when you only draw some paths you might forget the reindexing under the hood which then breaks associativity.

*Here my treatment of the identities is not consistent with the treatment of the composition of morphisms, because I regard them as a property instead of data, which is bad (even though you can sometimes find this definition of a category, similar to the - bad - definition of a group where the identity is regarded as a property). I should have said that every object has a specific morphism to itself, but it might not be an identity. But now it's too late to change this since a couple of answers now already refer to the original (inconsistent) requirements.

---

EDIT: All the answers that have been posted so far are interesting, but unfortunately most of them don't fit to the context that I have given above (but it's on my side to not make this more clear). Imagine you are a beginner and read the definition of a category, and the non-examples talk about monads, $(\infty,1)$-categories, pointed endofunctors, ... all of which already assumes a thorough understanding of category theory. Now it's of course too late to change the requirements what I am looking for. But I have added the education tag, and I hope that more elementary, but still interesting, examples will come in. But more advanced answers are appreciated as well!

Answer 1

The class of (complex, say) Banach spaces as objects and compact linear operators as morphisms is certainly attractive for functional analysists. But only finite dimensional spaces have identity morphisms.

Answer 2

I always find it fascinating that infinite matrix multiplication (when defined) is not necessarily associative, even though composition of linear maps is. For example if $A$ is the matrix with rows and columns indexed by $\mathbb{N}$ with $A_{ij}=1$ for all $i,j \in \mathbb{N}$ and $X$ is the matrix (with same indexing) with $1$'s along the main diagonal, $-1$'s immediately above the main diagonal, and $0$'s elsewhere, then: $$(AX)A=A,\qquad A(XA)=0.$$

We can turn this into an "almost" category by selecting objects, and defining the morphisms between each pair of objects to be a set of matrices, so that the support of a column of an incoming matrix always has finite intersection with the support of a row of an outgoing matrix. Then composition of morphisms can be given by matrix multiplication.

---

Edit in response to comment by @MartinBrandenburg

One concrete example of the above is simply to take objects $X_1, X_2, X_3, X_4$ and set $${\rm Hom}(X_1,X_2)=\{A\},\\ {\rm Hom}(X_2,X_3)=\{X\},\\ {\rm Hom}(X_3,X_4)=\{A\},\\ {\rm Hom}(X_1,X_3)=\{0\},\\ {\rm Hom}(X_2,X_4)=\{AX\},\\ {\rm Hom}(X_1,X_4)=\{0,A\},$$ where the matrices $A,X$ are as before. Composition of morphisms is always defined here (and not associative), but the whole construction is a little artificial.

Conversely, one could take the category of all vector spaces with canonical basis, and take relevant matrices to be morphisms. This definition is more natural, but now composition of morphisms is not always defined.

In an effort to get the best of both worlds, I considered taking pairs $(S,T)$ as objects, where $S,T\subseteq P(\mathbb{N})$, satisfy $U\cap V$ finite for all $U\in S$, $V\in T$. The morphisms $(S,T)\to (S',T')$ would then be matrices whose columns have support in an element of $S'$ and whose rows have support in an element of $T$.

This forces matrix multiplication resulting from composition of morphisms to always be defined. Unfortunately the resulting matrix may not be a valid morphism (e.g. its rows and columns may not have the right support).

I am not sure if this line of thinking can be fixed to yield a nicer more natural example of an "almost" category.

Answer 3

If $(T,\eta\colon\mathrm{id}\to T)$ is a pointed endofunctor, e.g. coming from a monad, on a category $\mathcal{C}$, then we can form an almost-category $\mathcal{D}$ whose objects are those of $\mathcal{C}$, and with $\mathcal{D}(x,y):=\mathcal{C}(Tx,y)$. The composition of $Tx\to y$ and $Ty\to z$ is $Tx\to y\xrightarrow{\eta}Ty\to z$. This means composition in $\mathcal{D}$ is associative. The problem is that there are no identity morphisms in general.

By picking particular examples of such functors $T$, you can avoid assuming people already know what pointed endofunctors are. For instance, you can pick $T=\pi_0$ on topological spaces, or $T$ being a powerset monad on sets, or $-\otimes_\mathbb{Z}\mathbb{Q}$ on abelian groups,...

Edit: To clarify, I do not propose that you actually talk about pointed endofunctors to your students, but that you pick a particular example, like powersets, and present the resulting almost-category in a concrete manner. By talking about pointed endofunctors I could make it clearer why this example works, and present a large class of examples to pick from, instead of a single one.

Answer 4

Let $\mathcal{C}$ have as objects some suitable class of (associative) algebras, and as morphisms from $A$ to $B$ $A$-$B$-bimodules. Compositions of morphisms are given by ${}_AH_B \circ {}_BK_C = {}_AH \otimes_B K_C$. Then composition is only associative up to isomorphism. In case algebras in $\mathcal{C}$ are all unital and all bimodules are assumed to respect the unities, i.e., the unities in $A$ and $B$ act as the identity map on ${}_AH_B$ for all $A$-$B$-bimodules that we include in $\mathcal{C}$, then identity morphisms exist, up to isomorphism (namely the bimodule ${}_AA_A$ would be the identity morphism at $A$). Without the unitality assumptions, identity morphisms may not exist, even up to isomorphism.

Answer 5

You could also take the category of $K$-vector spaces with morphisms from $V$ to $W$ given by $V'\otimes W$ (here $V'$ denotes the usual dual space). These morphisms can be naturally interpreted as the space of linear maps of finite rank (which makes this example similar to the Banach spaces with compact operators I guess). The composition is inherited from that interpretation but can just as easily be defined intrinsically (by bilinear extension of the rule $(f\otimes w) \circ (g \otimes x)=g(w)f\otimes x$). This then (again) only fails to be a category because infinite dimensional spaces will not have an identity morphism.

Answer 6

Here is an example from homotopy theory.

Let $\mathcal{C}$ be a category of fibrant objects and let $X$ and $Y$ be objects in $\mathcal{C}$. A correspondence $X ⇸ Y$ is an object $\tilde{X}$, a fibration $v : \tilde{X} \to X$, and a fibration $p : \tilde{X} \to Y$, such that $\langle p, v \rangle : \tilde{X} \to X \times Y$ is also a fibration. A correspondence is functional if (in the same notation) $v$ is a trivial fibration.

Let $\mathcal{C}^\textrm{cor} (X, Y)$ be the category of correspondences $X ⇸ Y$. It is a full subcategory of the slice category $\mathcal{C}_{/ (X \times Y)}$ and is itself a category of fibrant objects. Let $\mathcal{C}^\textrm{fun} (X, Y)$ be the full subcategory of functional correspondences. Notice that all morphisms in $\mathcal{C}^\textrm{fun} (X, Y)$ are weak equivalences; after all, they correspond to commutative diagrams of the form below: $$\require{AMScd} \begin{CD} X @<{\simeq}<< \tilde{X}' @>>> Y \\ @| @VV{\simeq}V @| \\ X @<<{\simeq}< \tilde{X} @>>> Y \end{CD}$$ Furthermore, any correspondence weakly equivalent to a functional correspondence is functional, i.e. $\mathcal{C}^\textrm{fun} (X, Y)$ is a homotopically replete full subcategory of $\mathcal{C}^\textrm{cor} (X, Y)$.

It is known that the nerve of $\mathcal{C}^\textrm{fun} (X, Y)$ is a model for the homotopy type of the space of morphisms $X \to Y$ in the homotopy (∞, 1)-category of $\mathcal{C}$. We have a model for composition: given fibrations $\tilde{X} \to X \times Y$ and $\tilde{Y} \to Y \times Z$, we have a product fibration $\tilde{X} \times \tilde{Y} \to X \times Y \times Y \times Z$, and pulling back along a path object $\textrm{Path} (Y) \to Y \times Y$ and projecting away the middle yields a fibration $\tilde{X}' \to X \times Z$; if $\tilde{X} \to X \times Y$ and $\tilde{Y} \to Y \times Z$ are functional correspondences, then so too is $\tilde{X}' \to X \times Z$. $$\begin{CD} \tilde{X}' @>>> X \times \textrm{Path} (Y) \times Z @>>> X \times Z \\ @VVV @VVV \\ \tilde{X} \times \tilde{Y} @>>> X \times Y \times Y \times Z \end{CD}$$ The interesting thing about this composition is that it is associative up to isomorphism (after choosing path objects for all objects in $\mathcal{C}$), because pullbacks are associative up to isomorphism. However, it fails to be unital (even up to isomorphism)! Morally, path objects should be units for this composition, but usually $X \not\cong \textrm{Path} (X)$. This phenomenon seems to be related to Simpson's conjecture regarding strictification of higher categories.

We can even see this construction "in action" in category theory: take $\mathcal{C}$ to be the category of categories, internal to some Barr-exact category $\mathcal{S}$ (such as $\textbf{Set}$). The fibrations are the isofibrations, i.e. functors with the isomorphism lifting property. The weak equivalences are the functors that are fully faithful and essentially surjective on objects. Functional correspondences are then special anafunctors. If all regular epimorphisms in $\mathcal{S}$ split (as they do in $\textbf{Set}$ when we have the axiom of choice), then we do not gain anything much by considering functional correspondences rather than ordinary (i.e. strict) functors; in fact, given a regular epimorphism in $\mathcal{S}$ that does not split, we can construct a weak equivalence in $\mathcal{C}$ with no quasi-inverse. This is basically why we are forced to consider anafunctors in settings where the axiom of choice is not available.

Answer 7

Suppose you have an almost-monad $T$, which has the syntactic components of a monad but does not satisfy the semantics (relations) of a monad. For example, if $m$ is a noncommutative monad on $\mathsf{Set}$ (e.g. a writer monad $M \times {-}$ where $M$ is a noncommutative monoid, or a state monad), then the composition $X \mapsto m(\mathrm{list}(X))$ would in general be such an object. Then in general, you can form an almost-category based on the Kleisli category construction. (On the other hand, as far as I can tell, the Eilenberg-Moore category construction would still work; it's just that without $T$ being a monad, you don't get an adjoint pair of functors factoring $T$.)

I admit this might be a bit complex for an introductory-level counterexample, though, even if you take one concrete example of such an almost-monad $T$, $X \mapsto M \times \mathrm{list}(X)$.

Answer 8

Working on @quarague's answer: category of all paths in digraph (free category) is indeed just a category, but consider 'category' of all simple paths in digraph. We define composition as follows: if we have multiple occurence of vertex (not in id morhism), we cut off a part between them, getting simple path again. I find it amusing, that this is not a category!
I suppose it is good example for students.

Answer 9

With the education aspect in mind, graphs can be an example of an almost-category. Given a graph we want the vertices to be the objects and the edges to be the morphisms. This does not quite work, there are a few 'fixes' we need to do.

First, the morphism should have a direction, so it is more natural to look at a directed graph instead. Second the composition of two edges is not an edge. However, the composition of two directed edges is a path and the composition of two paths is a path again. So the morphisms need to be paths in the graph not just edges. Finally, we don't yet have the identity morphisms. For that we need to add a loop at every vertex. Only after we make these adjustments the graph does become a category.

Answer 10

H-groups, also known as homotopy associative H-spaces, seem to fit this bill. They are an important concept in homotopy theory.

Suppose you start from the concept of a topological group. Every topological group is, of course, a category, with a single object, and with one morphism per element of the group, that morphism being invertible; the composition law of the category is, of course, the group operation.

An H-space is a topological space $H$ equipped with a certain continuous function $\mu : H \times H \to H$ which replaces the group operation, and a certain element $e$ which replaces the identity element. So one would expect each of the two functions $x \mapsto \mu(x,e)$ and $x \mapsto \mu(e,x)$ to be the identity function, but that is not required, those two functions need only be homotopic to the identity.

Also, associativity is all about the composition $H \times H \times H \mapsto H \times H \xrightarrow{\mu} H$ where you consider two different candidates for the first map: $(a,b,c) \mapsto (\mu(a,b),c)$ or $(a,b,c) \mapsto (a,\mu(b,c))$. The associative law would require that the two maps $H \times H \times H \mapsto H$ that you get using these two different candidates are the same map. But in an $H$-group, the homotopy associativity law only requires that those two maps be homotopic to each other.

Answer 11

Let $F:\mathcal{C} \to \mathcal{D}$ be a functor. Then, a natural question is to look for a good notion of $\operatorname{im}{F}$. The correct way of approaching this is to look for a categorical construction endorsing the structure of categories but one could be more naive and try to define the naive image (which I just named adhoc'ly) set-theoretically via

• $\operatorname{Ob}(\operatorname{im}^{\mathrm{naive}}{F}) = F(\operatorname{Ob}(\mathcal{C}))$,
• $\operatorname{Mor}(\operatorname{im}^{\mathrm{naive}}{F}) = F(\operatorname{Mor}(\mathcal{C}))$.

However, $\operatorname{im}^{\mathrm{naive}}{F}$ is not a category, one potentially cannot compose morphisms as discussed in MSE/413138. In that regard, this is not an answer to the posed question but the OP deemed that it was worth posting as an answer. More importantly, it shows that this naively defined image purely on the level of sets neglects categorical structure and cannot be the correct notion of a categorical image. Instead, one should close up under all the given structure, i.e. composition.

So in a certain sense, the naive image could be regarded as a partially defined category which generates the categorical image.