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$, if $\left|C(X, A)\right| = \left|C(X, B)\right|$ for all objects $X \in C$ then $A \cong B$.

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

• Věra Trnková, Unnatural isomorphisms of products in a category, Category Theory: Applications to Algebra, Logic and Topology Proceedings of the International Conference Held at Gummersbach, July 6–10, 1981. Berlin, Heidelberg: Springer Berlin Heidelberg.

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

• Ehsan Momtahan, Afshin Amini, and Babak Amini, From $Hom (A, X) \cong Hom(B, X)$ to $A \cong B$, Filomat 32.11 (2018): 4079-4087.

• 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).