The n-Category Café

No! Not if by “algebraic gadget” we mean something described by a bunch of operations obeying equational laws — that is, an algebra of a Lawvere theory.

This follows from a result of László Lovász in 1967:

• László Lovász, Operations with structures, Acta Mathematica Academiae Scientiarum Hungarica 18, (1967) 321–328.

On Mastodon, Omar Antolín sketched a proof that greases the wheels with more category theory. It relies on a rather shocking lemma:

Super-Yoneda Lemma. Let $\mathsf{C}$ be the category of algebras of some Lawvere theory, and let $A, B \in \mathsf{C}$ be two algebras whose underlying sets are finite. If the functors $\mathrm{hom}(-,A)$ and $\mathrm{hom}(-,B)$ are unnaturally isomorphic, then $A \cong B$.

Here we say the functors $\mathrm{hom}(-,A)$ and $\mathrm{hom}(-,B)$ are unnaturally isomorphic if

$$\mathrm{hom}(X,A) \cong \mathrm{hom}(X,B)$$

for all $X \in \mathsf{C}$. We’re not imposing the usual commuting naturality square — indeed we can’t, since we’re not even giving any specific choice of isomorphism!

If $\mathrm{hom}(-,A)$ and $\mathrm{hom}(-,B)$ are naturally isomorphic, you can easily show $A \cong B$ using the Yoneda Lemma. But when they’re unnaturally isomorphic, you have to break the glass and pull out the Super-Yoneda Lemma.

Given this shocking lemma, it’s easy to show this:

Theorem. Let $A, B$ be two algebras of a Lawvere theory whose underlying sets are finite. If $A^k \cong B^k$ for some natural number $k$ then $A \cong B$.

Here’s how. Since $A^k \cong B^k$, we have natural isomorphisms

$$\mathrm{hom}(-,A)^k \cong \mathrm{hom}(-, A^k) \cong \mathrm{hom}(-, B^k) \cong \mathrm{hom}(-,B)^k$$

so for any $X \in \mathsf{C}$ the sets $\mathrm{hom}(X,A)^k$ and $\mathrm{hom}(X,B)^k$ have the same cardinality. This means we have an unnatural isomorphism

$$\mathrm{hom}(-,A) \cong \mathrm{hom}(-,B)$$

The lemma magically lets us conclude that

$$A \cong B$$

Now, how do we use this to solve our puzzle? Let $a(n)$ be the number of isomorphism classes of algebras whose underlying set has $n$ elements. We must have

$$a(n^k) \ge a(n)$$

since we’ve just seen that nonisomorphic algebras with $n$ elements give nonisomorphic algebras with $n^k$ elements. So, for example, we can never have $a(4) \lt a(2)$, since $4 = 2^2$. Thus, the sequence can’t look like the one I showed you, with

$$a(0) = 1, \; a(1) = 1, \; a(2) = 2, \; a(3) = 1,\; a(4) = 1, ...$$

Nice! So let’s turn to the lemma, which is the really interesting part.

I’ll just quote Omar Antolín’s proof, since I can’t improve on it. I believe the ideas go back to Lovász, but a bit of category theory really helps. Remember, $A$ and $B$ are algebras of some Lawvere theory whose underlying sets are finite:

Let $\mathrm{mon}(X, A)$ be the set of monomorphisms, which here are just homomorphisms that are injective functions. I claim you can compute the cardinality of $\mathrm{mon}(X, A)$ using the inclusion-exclusion principle in terms of the cardinalities of $\mathrm{hom}(Q, A)$ for various quotients of $X$.

Indeed, for any pair of elements $x, y \in X$, let $S(x, y)$ be the set for homomorphisms $f \colon X \to A$ such that $f(x) = f(y)$. The monomorphisms are just the homomorphisms that belong to none of the sets $S(x, y)$, so you can compute how many there are via the inclusion-exclusion formula: you’ll just need the cardinality of intersections of several $S(x_i, y_i)$.

Now, the intersection of some $S(x_i, y_i)$ is the set of homorphisms $f$ such that for all $i$, $f(x_i) = f(y_i)$. Those are in bijection with the homorphisms $Q \to A$ where $Q$ is the quotient of $X$ obtained by adding the relations $x_i=y_i$ for each $i$.

So far I hope I’ve convinced you that if $\mathrm{hom}(-, A)$ and $\mathrm{hom}(-, B)$ are unnaturally isomorphic, so are $\mathrm{mon}(-, A)$ and $\mathrm{mon}(-, B)$. Now it’s easy to finish: since $\mathrm{mon}(A, A)$ is non-empty, so is $\mathrm{mon}(A, B)$, so $A$ is isomorphic to a subobject of $B$. Similarly $B$ is isomorphic to a subobject of $A$, and since they are finite, they must be isomorphic.

Beautiful!

But if you look at this argument you’ll see we didn’t use the full force of the assumptions. We didn’t need $A$ and $B$ to be algebras of a Lawvere theory. They could have been topological spaces, or posets, or simple graphs (which you can think of as reflexive symmetric relations), or various other things. It seems all we really need is a category $\mathsf{C}$ of gadgets with a forgetful functor

$$U \colon \mathsf{C} \to \mathsf{FinSet}$$

that is faithful and has some extra property… roughly, that we can take an object in $\mathsf{C}$ and take a quotient of it where we impose a bunch of extra relations $x_i = y_i$, and maps out of this quotient will behave as you’d expect. More precisely, I think the extra property is this:

Given any $X \in \mathsf{C}$ and any surjection $p \colon U(X) \to S$, there is a morphism $j \colon X \to Q$ such that the morphisms $f \colon X \to Y$ that factor through $j$ are precisely those for which $U(f)$ factors through $p$.

Can anyone here shed some light on this property, and which faithful functors $U \colon \mathsf{C} \to \mathsf{FinSet}$ have it? These papers should help:

• Luca Reggio, Polyadic sets and homomorphism counting.

• Anuj Dawar, Tomás Jakl and Luca Reggio, Lovász-Type theorems and game comonads.

• Shoma Fujino and Makoto Matsumoto, Lovàsz’s hom-counting theorem by inclusion-exclusion principle.

but I haven’t had time to absorb them yet.

By the way, there’s a name for categories where the super-Yoneda Lemma holds: they’re called right combinatorial.

And there’s a name for the sequences I’m talking about. If $T$ is a Lawvere theory, the sequence whose $n$th term is the number of isomorphism classes of $T$-algebras with $n$ elements is called the fine spectrum of $T$. The idea was introduced here:

• Walter Taylor, The fine spectrum of a variety, Algebra Universalis 5 (1975), 263–303.

though Taylor used not Lawvere theories but an equivalent framework: ‘varieties’ in the sense of universal algebra. For a bit more on this, go here.

I’m interested in which sequences are the fine spectrum of some Lawvere theory. You could call this an ‘inverse problem’. The direct problem — computing the fine spectrum of a given Lawvere theory — is already extremely difficult in many cases. But the case where there aren’t any equational laws (except trivial ones) is manageable:

• Michael A. Harrison, The number of isomorphism types of finite algebras, Proceedings of the American Mathematical Society 17 (1966), 731–737.

Some errors in Harrison’s paper were corrected here:

• Philip Tureček, Counting finite magmas.

I suspect Harrison and Tureček’s formulas could be nicely derived using species, since they’re connected to the tree-like structures discussed here:

• François Bergeron, Gilbert Labelle and Pierre Leroux, Combinatorial Species and Tree-Like Structures, Cambridge U. Press, Cambridge, 1998.

For all I know these authors point this out! It’s been a while since I’ve read this book.