nLab combinatorial category

Definition

A combinatorial category [Pultr (1973, Def. 1.7)] $C$ is a locally finite category satisfying the unnatural isomorphism property:

• For all objects $A, B \in C$, if there is an unnatural isomorphism $C(-, A) \cong C(-, B)$, then $A \cong B$.

Or equivalently

• For all objects $A, B \in C$, $\left|C(X, A)\right| = \left|C(X, B)\right|$ for all objects $X \in C$.

Properties

Proposition

Let $C$ be a combinatorial category and let $A, B, X \in \C$. If $A \times X \cong B \times X$ and $X$ is weakly terminal, then $A \cong B$.

Proof

For all $Y \in C$, we have

$$\left|C(Y, A)\right| \times \left|\C(Y, X)\right| = \left|C(Y, A \times X)\right| = \left|C(Y, B \times X)\right| = \left|C(Y, B)\right| \times \left|C(Y, X)\right|$$

Hence we may divide both sides by $\left|C(Y, X)\right|$ (which is nonzero since $X$ is weakly terminal) and so $\left|C(Y, A)\right| = \left|C(Y, B)\right|$ for all $Y \in \C$, from which we have $A \cong B$.

Related concepts

• finite category

• not related is the notion of combinatorial model category

References

• A. Pultr, Isomorphism types of objects in categories determined by numbers of morphisms, Acta Scientiarum Mathematicarum 35 (1973) 155-160 [pdf]

• Luca Reggio?, Polyadic sets and homomorphism counting, Advances in Mathematics 410 (2022): 108712.

• Shoma Fujino and Makoto Matsumoto, Lovász’s hom-counting theorem by inclusion-exclusion principle, arXiv:2206.01994 (2022).