Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: theory: category theory

Topic: counting algebraic structures

John Baez (Sep 09 2023 at 08:54):

The number of groups with n elements goes like this, starting with $n = 0$:

0, 1, 1, 1, 2, 1, 2, 1, 5, ...

The number of semigroups with $n$ elements goes like this:

1, 1, 5, 24, 188, 1915, 28634, 1627672, 3684030417, 105978177936292, ...

Here I'm counting isomorphic guys as the same.

Is there any sort of algebraic gadget where the number of these gadgets with $n$ elements goes like this?

1, 1, 2, 1, 1, 1, 1, 1, ...

John Baez (Sep 09 2023 at 08:55):

No! Not if by "algebraic gadget" we mean something described by a bunch of operations obeying equational laws --- that is, by 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}(-,A)$ are unnaturally isomorphic, then $A \cong B$.

John Baez (Sep 09 2023 at 08:55):

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, we can show $A \cong B$ using the Yoneda Lemma. But when they're unnaturally isomorphic, we have to break the glass and pull out the Super-Yoneda Lemma.

John Baez (Sep 09 2023 at 08:56):

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$

John Baez (Sep 09 2023 at 08:57):

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.

John Baez (Sep 09 2023 at 08:58):

I'll just quote Omar Antolín's proof, since I can't improve on it. 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!

John Baez (Sep 09 2023 at 08:59):

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 various other things. 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$.

John Baez (Sep 09 2023 at 09:00):

Can anyone shed more light on what generalizations of Lawvere theories describe mathematical gadgets like this?

By the way: if $T$ is any Lawvere theory, its fine spectrum is the sequence whose $$n$$th term is the number of isomorphism classes of $T$-algebras with $n$ elements. 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.

Nathanael Arkor (Sep 09 2023 at 09:24):

There is a recent paper of Luca Reggio in which is proven general "homomorphism counting" results (what you call the "Super-Yoneda Lemma"): Polyadic Sets and Homomorphism Counting.

John Baez (Sep 09 2023 at 09:28):

Oh, good!

Kevin Arlin (Sep 09 2023 at 16:14):

Wow, that lemma is so fun! The only thing I can think of that subsumes both categories of models of Lawvere theories and the category of topological spaces is categories with a solid functor into set. But I haven’t tried to see yet whether that’s actually the right idea

John Baez (Sep 09 2023 at 17:03):

Yes, the great thing about the lemma is that the statement is all category theory - but the proof relies so heavily on good old inclusion-exclusion as beloved by combinatorists!

There's a theory of [[topological concrete categories]], but I don't know if that's the right way forward.

Nathanael Arkor (Sep 09 2023 at 19:10):

(For what it's worth, Reggio's proof is also based on the inclusion–exclusion principle.)

Kevin Arlin (Sep 10 2023 at 18:48):

I'm thinking Omar's proof will go through in the following context:

• A category $\mathbf C$, concrete over finite sets, such that
• There's a proper factorization system $(E,M)$, i.e. the $E$-maps are epimorphisms, and the underlying function of an $E$-map is surjective, while
• The $E$-quotient object lattice of an object $X\in \mathbf C$ has joins and is mapped injectively by the forgetful functor into the quotient set lattice of its underlying set (So a bijection under $X$ between underlying sets of two quotient objects lifts to an isomorphism, though the underlying functor is perhaps not actually conservative or injective on isomorphism classes. EDIT: I suppose a convenient way to get this condition is to assume that the forgetful functor is an isofibration with unique lifting, or in other terminology that $\mathbf C$ admits unique transport of structure.)

Under these assumptions, we can say that $\mathbf C(X,A)-\mathrm{mon}(X,A)$ is the union of the sets $h_Q$ of morphisms $X\to A$ factoring through the $E$-map $X\to Q$, that this union is finite since the underlying set $|X|$ has only finitely many quotients, and that PIE gets us $|\mathbf C(X,A)-\mathrm{mon}(X,A)|$ once we know all the $|h_Q|$ since $|h_Q\cap h_{Q'}|=|h_{Q\vee Q'}|$ (and similarly for further iterated intersections. )So I think that recovers the argument.

Kevin Arlin (Sep 10 2023 at 18:58):

These conditions hold if $\mathbf C$ is the category of finite spaces in some topological category over $\mathbf{Set}$ (which might be basically the same as being a category topological over $\mathbf{FinSet}$?), where we have a factorization system with $E$ given by strong=extremal=regular epis just like in $\mathbf{Top}$, by equipping the middle object of the epi-mono factorization of some map in $\mathbf{Set}$ with the terminal $\mathbf{C}$-structure making the image inclusion continuous. These conditions look like they also hold if $\mathbf C$ is the finite algebras for any monad over $\mathbf{Set}$, again with $E$ the strong=extremal=regular epis.

So I continue to guess that if you have a solid functor into finite sets, which subsumes these two cases and not too much more, you can probably get the same place by using a semi-final lift instead of a final lift to construct the factorization system. But I'm not totally sure about this.

John Baez (Sep 11 2023 at 07:49):

Thanks! I don't know solid functors well, but reading the nLab article a few times I'm starting to get the idea, and it may be good. One funny thing is that in my own guess as to the required property I didn't use a general sink, but just a sink with a single morphism:

John Baez (Sep 11 2023 at 07:50):

The functor $U \colon \mathsf{C} \to \mathsf{FinSet}$ is faithful and 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$.

Claudio Pisani (Sep 15 2023 at 12:07):

John Baez said:

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}(-,A)$ are unnaturally isomorphic, then $A \cong B$.

some time ago I posed a related question on mo.
I will explain my motivations.

John Baez (Sep 15 2023 at 13:08):

Interesting. Above I gave a conjectured answer to your question - sufficient conditions on a category for the super-Yoneda Lemma to hold, perhaps not necessary. So did Kevin Arlin. I see your question got some other useful answers on Math Overflow. Thanks for letting me know about those.

Some people call categories for which the super-Yoneda Lemma holds right combinatorial.

Claudio Pisani (Sep 16 2023 at 13:15):

In fact my original interest was in left (rather than right) combinatorial (cartesian closed) categories, as I explain here.