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: uncomputable endofunctors on FinSet

Nathaniel Virgo (Aug 14 2024 at 02:42):

I was idly thinking about endofunctors on $\bf FinSet$. At first I conjectured that they are all polynomial functors (i.e. coproducts of representables), but I quickly realised this is wrong, because there is a powerset functor $\bf FinSet\to FinSet$. This maps $n$-element sets to $2^n$-element sets, and $2^n$ isn't polynomial in $n$.

This made me wonder what other functions are possible. In particular, is there an endofunctor on $\bf FinSet$ that maps $n$-element sets to $F(n)$-element setes, where $F:\N\to\N$ is an uncomputable function, such as the busy beaver function?

Or more broadly, is there an endofunctor on the skeleton of $\bf FinSet$ that is incomputable, in the sense that there is no Turing machine that can determine the image of every morphism?

It feels like the constraint of functoriality might be strong enough to prevent this from existing, but I might just not be hitting on the right counterexample.

David Michael Roberts (Aug 14 2024 at 04:06):

Can one diagonalise over all computable endofunctors of FInSet? That is, something like take $n\mapsto P(F_n(n))$, where $F_n$ is the $n^{th}$ computable endofunctor, assuming they are countable?

Nathaniel Virgo (Aug 14 2024 at 05:10):

How would such a diagonal functor act on morphisms?

Tobias Fritz (Aug 14 2024 at 05:44):

I seems helpful to think of such a functor as a symmetric set, which is a simplicial set with extra symmetries that amount to reordering the vertices of each simplex.

Tobias Fritz (Aug 14 2024 at 05:49):

Based on this, it should be possible to consider functors that are constant $1$ on any set of cardinality $< n$, such as taking a representable and identifying all its simplices in dimensions $d < n$. Topologically, this is an $n$-sphere.

Tobias Fritz (Aug 14 2024 at 05:51):

Then by taking coproducts of these, you can achieve arbitrarily fast growth, and in particular the map $n \mapsto |F([n])|$ can be uncomputable.

Tobias Fritz (Aug 14 2024 at 05:54):

I'm getting a little mixed up by extrapolating my understanding of simplicial sets to symmetric sets, so take the details with a grain of salt.

David Michael Roberts (Aug 14 2024 at 06:29):

Nathaniel Virgo said:

How would such a diagonal functor act on morphisms?

Good point. This would only be sensible on the core of FinSet, perhaps.

John Baez (Aug 14 2024 at 06:30):

I'm having trouble seeing how Toby's sort of functor $F$ achieves arbitrarily large growth while remaining finite for all finite sets. If $F(S)$ is huge for some large set $S$ and $f: S \to T$ maps $S$ to a smaller set $T$ we need $F(f)$ to be highly many-to-one, or else $F(T)$ will also be huge.

John Baez (Aug 14 2024 at 06:33):

For this reason it's proving much easier for me to invent uncomputable functors $F: \mathrm{core}(\mathsf{FinSet}) \to \mathsf{FinSet}$ than uncomputable functors $F: \mathsf{FinSet} \to \mathsf{FinSet}$.

John Baez (Aug 14 2024 at 06:35):

However, there must exist lots of uncomputable functors $F: \mathsf{FinSet} \to \mathsf{FinSet}$, simply because there are only countably many computable ones!

Tobias Fritz (Aug 14 2024 at 06:36):

I agree, I'm having trouble with that too :sweat_smile: so all I want to suggest is that thinking of it in topological terms of symmetric simplicial sets may be helpful for constructing examples of functors that take small values on small sets and really large values on larger sets.

John Baez (Aug 14 2024 at 06:40):

How can we prove that there are uncountably many endofunctors on $\mathsf{FinSet}$? It seems "obvious" but I don't immediately see how to prove it.

Tobias Fritz (Aug 14 2024 at 06:49):

Oh no, I even got confused about the variance :woozy_face: no more math before breakfast!

Jean-Baptiste Vienney (Aug 14 2024 at 07:23):

John Baez said:

How can we prove that there are uncountably many endofunctors on $\mathsf{FinSet}$? It seems "obvious" but I don't immediately see how to prove it.

For every object $X$ of a category, defines the endofunctor $1_X$ by $1_X(A)=X$ and $1_X(f)=\mathrm{id}_X$.

The collection $\{1_{\{x\}}:\mathbf{FinSet} \rightarrow \mathbf{FinSet},~x \in \mathbb{R}\}$ is an uncountable collection of endofunctors of $\mathbf{FinSet}$.

Jean-Baptiste Vienney (Aug 14 2024 at 07:29):

Of course, these endofunctors should be isomorphic for a good definition of morphism of endofunctors. So we should find an uncountable collection of non isomorphic sets if you want a solution in the stronger sense using these constant endofunctors. I don’t know much about cardinals but I think that it would boil down to proving that the collection of all cardinals is uncountable. Maybe this assertion is false, I don’t know.

Jean-Baptiste Vienney (Aug 14 2024 at 07:44):

For this story of constant endofunctors, it might be helpful to realize that every category is isomorphic to the full subcategory of constant endofunctors of its category of endofunctors (a natural transformation from the constant endofunctor $1_X$ to the constant endofunctor $1_Y$ is always a natural transformation $1_f:1_X \rightarrow 1_Y$ given by $(1_f)(A)=f:X=1_X(A) \rightarrow Y=1_Y(A)$ for some $f:X \rightarrow Y$). So that the category of endofunctors of a category is always bigger than the category. In particular there is an injection of the set of objects of a category into the set of object of its category of endofunctors. So if $\mathrm{Ob}_\mathcal{C}$ is uncountable, then $\mathrm{Ob}_{\mathrm{End}(\mathcal{C})}$ is uncountable.

David Michael Roberts (Aug 14 2024 at 07:54):

One then has to worry whether the natural isomorphism between a computable endofunctor and an arbitrary one is computable, but I think if your endofunctor is constant, it should be computable. And if the constant object is has no nontrivial endomorphisms then any two such constant functors taking _values_ that are isomorphic, they are uniquely isomorphic, and so the natural isomorphism is also constant. And so that should be computable, too.

John Baez (Aug 14 2024 at 08:09):

Jean-Baptiste Vienney said:

John Baez said:

How can we prove that there are uncountably many endofunctors on $\mathsf{FinSet}$? It seems "obvious" but I don't immediately see how to prove it.

The collection $\{1_{\{x\}}:\mathbf{FinSet} \rightarrow \mathbf{FinSet},~x \in \mathbb{R}\}$ is an uncountable collection of endofunctors of $\mathbf{FinSet}$.

Haha! True, but this is like asking a genie "make me a milkshake" - and then he turns you into a milkshake. :smirk:

I should have asked: can anyone find uncountably many natural isomorphism classes of endofunctors of $\mathsf{FinSet}$?

Or equivalently: if $\mathsf{F}$ is a skeleton of $\mathsf{FinSet}$, can anyone find uncountably many endofunctors of $\mathsf{F}$?

Nathaniel Virgo (Aug 14 2024 at 08:11):

I think we should be talking about the skeleton of $\bf FinSet$ if we want to talk about computability anyway

John Baez (Aug 14 2024 at 08:12):

It makes life simpler, for sure.

Morgan Rogers (he/him) (Aug 14 2024 at 08:16):

John Baez said:

How can we prove that there are uncountably many endofunctors on $\mathsf{FinSet}$? It seems "obvious" but I don't immediately see how to prove it.

Surprisingly, there aren't.
For a locally finite category $C$ (I.e. such that homsets are finite), $[C^{\mathrm{op}},\mathrm{FinSet}]$ is the free finitary cocompletion of $C$; all of its objects are naturally isomorphic to a finite colimit of representables by the coYoneda lemma. Taking $C$ to be the opposite of the category of finite sets, we obtain that every endofunctor of finite sets is a finite colimit of representables!!

John Baez (Aug 14 2024 at 08:17):

Wow, amazing - yet simple in retrospect!

Morgan Rogers (he/him) (Aug 14 2024 at 08:18):

(And there are countably many since there are countably many isomorphism classes of finite diagram)

John Baez (Aug 14 2024 at 08:20):

So now I've completely flip-flopped: it now seems "obvious" that every endofunctor of $\mathsf{FinSet}$ is computable - or if that concept seems too murky, every endofunctor on the skeleton $\mathsf{F}$ of $\mathsf{FinSet}$ with objects $\{\}, \{0\}, \{0,1\}, ...$ is computable.

John Baez (Aug 14 2024 at 08:21):

That's because I believe a finite colimit of representable functors on $\mathsf{F}^{\textrm{op}}$ is computable.

John Baez (Aug 14 2024 at 08:26):

It takes a bit of work to define when a functor $f: \mathsf{F} \to \mathsf{F}$ is "representable", though... and now I'm getting confused about this.

Nathaniel Virgo (Aug 14 2024 at 08:36):

Morgan Rogers (he/him) said:

Taking $C$ to be the opposite of the category of finite sets, we obtain that every endofunctor of finite sets is a finite colimit of representables!!

Wait, what? Where did I go wrong initially, then? Can the covariant power set functor be expressed as a finite colimit of representables in $\bf FinSet$?

John Baez (Aug 14 2024 at 08:41):

I don't immediately see the answer to your question, Nathaniel, so you may be on to something, but Morgan is talking about representable functors on $\mathsf{FinSet}^{\textrm{op}}$.

John Baez (Aug 14 2024 at 08:47):

This is fairly confusing! A representable functor on $\mathsf{FinSet}^{\textrm{op}}$ is a functor of the form

$\mathsf{FinSet}^{\textrm{op}}(-,x) : (\mathsf{FinSet}^{\textrm{op}})^{\textrm{op}} \to \mathsf{Set}$

for some $x \in \mathsf{FinSet}^{\textrm{op}}$. This is a convoluted way of saying a functor

$\mathsf{FinSet}(x,-) : (\mathsf{FinSet} \to \mathsf{Set}$

for some $x \in \mathsf{FinSet}^{\textrm{op}}$.

Tobias Fritz (Aug 14 2024 at 08:48):

The point must be that the colimit can still be infinite: an infinite coproduct, plus infinitely many identifications that result in the colimit functor still taking finite values.

Tobias Fritz (Aug 14 2024 at 08:49):

Morgan Rogers (he/him) said:

Surprisingly, there aren't.
For a locally finite category $C$ (I.e. such that homsets are finite), $[C^{\mathrm{op}},\mathrm{FinSet}]$ is the free finitary cocompletion of $C$; all of its objects are naturally isomorphic to a finite colimit of representables by the coYoneda lemma.

In other words, why is the colimit necessarily finite?

John Baez (Aug 14 2024 at 08:49):

So you're claiming this is false, @Tobias Fritz:

Morgan Rogers (he/him) said:

For a locally finite category $C$ (I.e. such that homsets are finite), $[C^{\mathrm{op}},\mathrm{FinSet}]$ is the free finitary cocompletion of $C$; all of its objects are naturally isomorphic to a finite colimit of representables by the coYoneda lemma.

Tobias Fritz (Aug 14 2024 at 08:51):

Yes, for a simpler counterexample just take $C$ to be a category having infinitely many objects and only identity morphisms. Then the finite colimits of representables are only those functors that take almost all objects to the empty set.

John Baez (Aug 14 2024 at 09:10):

Right. Okay. So I no longer believe Morgan's argument that there are only countably many endofunctors on FinSet, up to natural isomorphism. He just stated his claim with such conviction that I was bowled over.

So I still don't know if there are uncountably many endofunctors on FinSet, up to natural isomorphism. :cry:

Tobias Fritz (Aug 14 2024 at 09:15):

Tobias Fritz said:

I seems helpful to think of such a functor as a symmetric set, which is a simplicial set with extra symmetries that amount to reordering the vertices of each simplex.

I still think that this is a good way of constructing examples of fast-growing functors $\mathsf{FinSet}^\mathrm{op} \to \mathsf{FinSet}$, which can then be composed with the contravariant power set functor to get examples of fast-growing functors $\mathsf{FinSet} \to \mathsf{FinSet}$.

Tobias Fritz (Aug 14 2024 at 09:15):

Here's a concrete example inspired by that and which is also in the spirit of species. Fix $k \in \mathbb{N}$, and for a finite set $A$ let $F_k(A)$ be the set of $k$-uniform hypergraphs with vertex set $A$. Here, a $k$-uniform hypergraph is a subset of the set of $k$-element subsets of $A$, and I'm using these because there's only one $k$-uniform hypergraph structure on a set with fewer than $k$ elements. This $F_k$ can easily be made into a functor: for $f : A \to B$ and a $k$-hypergraph structure $H \in F_k(A)$, we can say that a subset $S \subseteq B$ belongs to the transported hypergraph structure $F_k(f)(H)$ on $B$ if and only if $f^{-1}(S)$ contains a subset belonging to $H$. In terms of drawing hypergraphs, you just map hyperedges to hyperedges and discard those for which $f$ identifies vertices.

The upshot now is that $F_k(A)$ is singleton precisely for $|A| < k$. So by taking finite colimits of these functors, one can achieve arbitrarily large growth, and in particular uncomputable growth. It also shows that there are uncountably many (isomorphism classes) of endofunctors.

John Baez (Aug 14 2024 at 09:34):

So let's see if I get this right. You're claiming that:

1) There's a functor $F_k: \mathsf{FinSet} \to \mathsf{FinSet}$ such that on objects $F_k(A) = P(P_k(A))$ where:

• $P_k(A)$ is the set of $k$-element subsets of $A$

and

• $P(S)$ is the power set of $S$.

2) $F_k(A)$ has just one element if $|A| \lt k$.

Tobias Fritz (Aug 14 2024 at 09:36):

Yep, that's a good way to put it. Note that 2) is a consequence of 1) because of $P(P_k(A)) = P(\emptyset) = 1$ if $|A| < k$.

John Baez (Aug 14 2024 at 09:39):

Okay, great. The only thing I'm worrying about is how $F_k$ is defined on morphisms. You explained it, but... is it the composite of some covariant functors $P$ and $P_k$ that are defined on objects as I said, and defined somehow on morphisms? Or maybe is it the composite of two contravariant functors $P$ and $P_k$ that are defined on objects as I said?

Tobias Fritz (Aug 14 2024 at 09:41):

I don't yet know how to describe the action on morphisms in terms of a factorization into $P_k$ and $P$, but it may be possible to do so by composing suitable versions of these functors that go $P_k : \mathsf{FinSet}^{\mathrm{op}} \to \mathsf{FinRel}$ and $P : \mathsf{FinRel}^{\mathrm{op}} \to \mathsf{FinSet}$.

Tobias Fritz (Aug 14 2024 at 09:42):

The first one seems quite clear: given $f : A \to B$ and a $k$-element subset $S \subseteq B$, it's related precisely to all the $k$-element subsets of $f^{-1}(S)$, and this defines $P_k(f) : P_k(B) \to P_k(A)$.

John Baez (Aug 14 2024 at 09:43):

In case it wasn't obvious, it's $P_k$ that I'm worried about. I don't know a covariant or contravariant "$k$-element subset functor".

John Baez (Aug 14 2024 at 09:43):

But if you can clearly explain to me (again?) what $F_k$ does on morphisms without factoring it into two functors, that's fine too.

John Baez (Aug 14 2024 at 09:44):

I've got a set $S$ of $k$-element subsets of $A$, and a function $f: A \to B$. I want a set of $k$-element subsets of $B$.

Tobias Fritz (Aug 14 2024 at 09:48):

Actually I think the factorization works, with $P_k$ as above and $P : \mathsf{FinRel}^{\mathrm{op}} \to \mathsf{FinSet}$ the usual thing, namely taking a relation $R : A \to B$ to the map $P(R) : P(B) \to P(A)$ which maps every subset $S \subseteq B$ to the subset of all elements of $A$ that are related to something in $S$.

Tobias Fritz (Aug 14 2024 at 09:50):

John Baez said:

I've got a set $S$ of $k$-element subsets of $A$, and a function $f: A \to B$. I want a set of $k$-element subsets of $B$.

It's the set of all $k$-element subsets of $B$ whose preimage contains an element of $S$ as a subset.

Tobias Fritz (Aug 14 2024 at 09:52):

For $k=2$, we're talking about graphs (in the combinatorialists' sense) with vertex set $A$. We can transport such a graph along $f$ just by pushing forward edges in the obvious way. We get into trouble for those edges whose vertices are identified under $f$, but we can just ignore those.

John Baez (Aug 14 2024 at 09:55):

Okay, I think it's sinking in.

John Baez (Aug 14 2024 at 10:09):

So it looks like we can prove there are uncomputable functors $F: \mathsf{F} \to \mathsf{F}$ (where $\mathsf{F}$ is some skeleton of $\mathsf{FinSet}$) in at least two ways:

1) Show that there are countably many natural isomorphism classes of computable functors $F: \mathsf{F} \to \mathsf{F}$. Show there are uncountably many natural isomorphism classes of functors $F: \mathsf{F} \to \mathsf{F}$. For the latter, use functors the form

$F = \sum_{n = 0}^\infty F_{k(n)}$

where $k : \mathbb{N} \to \mathbb{N}$ is a strictly increasing sequence, and show that distinct such sequences give nonisomorphic functors $F$.

2) Show that if $k : \mathbb{N} \to \mathbb{N}$ is uncomputable, the functor

$\sum_{n = 0}^\infty F_{k(n)}$

is uncomputable.

Morgan Rogers (he/him) (Aug 14 2024 at 10:39):

John Baez said:

Right. Okay. So I no longer believe Morgan's argument that there are only countably many endofunctors on FinSet, up to natural isomorphism. He just stated his claim with such conviction that I was bowled over.

I had convinced myself too, although I hadn't checked what the conditions are on a base of enrichment for the standard results such as coYoneda to work

Tobias Fritz (Aug 14 2024 at 11:15):

John Baez said:

2) Show that if $k : \mathbb{N} \to \mathbb{N}$ is uncomputable, the functor

$\sum_{n = 0}^\infty F_{k(n)}$

is uncomputable.

Actually the product $\prod_{n=0}^\infty F_{k(n)}$ works better, because the infinite coproduct would require the functors to vanish for almost all $k$ on every finite set $A$, which doesn't work because if $F(A) = \emptyset$ for some nonempty $A$, then this must hold for all nonempty $A$. But for the product on the other hand, we need $F_k(A) = 1$ for almost all $k$, and this holds for example for the functors coming out of my construction with hypergraphs.

John Baez (Aug 14 2024 at 11:45):

Oh, whoops - for some reason I'd been imagining $F_k(A) = \emptyset$ when $|A| < k$, when in fact I knew it was the 1-element set. It's so easy to slip up - anyone watching this thread will see how easy.

So yes, the corrected problem set is:

1) Show that there are countably many natural isomorphism classes of computable functors $F: \mathsf{F} \to \mathsf{F}$. Show there are uncountably many natural isomorphism classes of functors $F: \mathsf{F} \to \mathsf{F}$. For the latter, use functors of the form

$F_j = \prod_{n = 0}^\infty F_{k(n)}$

where $j: \mathbb{N} \to \mathbb{N}$ is a strictly increasing sequence, and show that distinct such sequences give nonisomorphic functors $F_j$.

2) Show that if $j : \mathbb{N} \to \mathbb{N}$ is uncomputable, the functor $F_j$ is uncomputable.

Tobias Fritz (Aug 14 2024 at 11:50):

I think both of those approaches work. For 2) in particular, by taking the index sequence $k(n)$ to grow slowly enough, we can make $f(m) \coloneqq \bigg|\prod_n F_{k(n)}([m])\bigg|$ grow faster than the busy beaver function. Now we're done because any function lower bounded by busy beaver is uncomputable: if it was computable, we could also compute the busy beaver function on $m$ simply by running all $m$-state Turing machines up to time $f(m)$.

John Baez (Aug 14 2024 at 11:53):

There's still some work required to show that distinct strictly increasing sequences $j$ give nonisomorphic functors $F_j$, but I think this approach should be manageable, though a bit sweaty:

Compute $f_{j,n} = |F_j\{1, \dots, n\}|$ as a function of $j$ and $n$, and then use that to show that distinct strictly increasing functions $j$ give distinct sequences $f_{j,0}, f_{j,1}, \dots$, hence nonisomorphic functors $F_j$.

Tobias Fritz (Aug 14 2024 at 11:55):

The index sequence $j$ should grow slowly in order for $f_{j,n}$ to grow fast in $n$, no? So it may be better to merely require $j$ to be non-strictly increasing.

John Baez (Aug 14 2024 at 11:57):

Tobias Fritz said:

I think both of those approaches work. For 2) in particular, by taking the index sequence $j(n)$ to grow slowly enough, we can make $f(m) \coloneqq \bigg|\prod_n F_{j(n)}([m])\bigg|$ grow faster than the busy beaver function. Now we're done because any function lower bounded by busy beaver is uncomputable: if it was computable, we could also compute the busy beaver function on $m$ simply by running all $m$-state Turing machines up to time $f(m)$.

Okay, that would work if we take $j$ to be increasing but not strictly so. I was taking $j$ to be strictly increasing but that makes the argument harder (see above), since then what you're calling $f$ can't grow super-fast. I believe $f$ can still be uncomputable just by taking $j$ to be uncomputable, but checking everything takes a lot more work than in your approach!

John Baez (Aug 14 2024 at 11:57):

That is, I think that just by looking at $f$ you can figure out the sequence $j$, but it's a hassle to check this.

John Baez (Aug 14 2024 at 11:59):

For your approach to work we still require that $j$ eventually get larger than any fixed natural number - to make sure $F_j(A)$ is always finite.

Tobias Fritz (Aug 14 2024 at 12:02):

It's probably possible to choose $F_k$ such that the cardinalities $|F_k(A)|$ are all powers of a fixed prime depending on $k$. With these primes all chosen distinct, I think your approach of reconstructing the indexing sequence from the functor should work, most easily so if the sequence is strictly increasing.

John Baez (Aug 14 2024 at 12:06):

Now you're making me imagine an alternative universe where Goedel had to encode everything as endofunctors on FinSet.

Jean-Baptiste Vienney (Aug 14 2024 at 12:14):

Jean-Baptiste Vienney said:

Of course, these endofunctors should be isomorphic for a good definition of morphism of endofunctors. So we should find an uncountable collection of non isomorphic sets if you want a solution in the stronger sense using these constant endofunctors. I don’t know much about cardinals but I think that it would boil down to proving that the collection of all cardinals is uncountable. Maybe this assertion is false, I don’t know.

Sorry for this, I wrote this in the middle of the night. I should have remembered that finite sets are finite. So there are only countably many finite sets up to bijection.
And that a morphism of functor is called a natural transformation :rolling_eyes:

The solution is very cool though!

EDIT: But if I understand, this candidate solution is maybe not true finally.

Jean-Baptiste Vienney (Aug 14 2024 at 12:15):

Morgan Rogers (he/him) said:

(And there are countably many since there are countably many isomorphism classes of finite diagram)

This is maybe simple but how do we prove this?

John Baez (Aug 14 2024 at 12:16):

Morgan Rogers (he/him) said:

I had convinced myself too, although I hadn't checked what the conditions are on a base of enrichment for the standard results such as coYoneda to work

I shouldn't blame you too much: I wasn't just bowing to your authority, the argument really convinced me. This is especially unfortunate because right now I'm working on a problem where the same issue comes up. It's easiest to state the issue in its decategorified form: for an infinite set $X$, there are more functions $f: X \to \mathbb{N}$ than finite sums of Kronecker delta functions. This is so obvious nobody would mix them up! But I've been dealing with $\mathsf{FinVect}$-valued presheaves on locally finite categories and there I keep making analogous mistakes.

Morgan Rogers (he/him) (Aug 14 2024 at 12:58):

So I've concluded that one needs the category to be "FinSet-small" (I.e. finite) for my original assertion about the finitary cocompletion to work, and otherwise you need to stick to finite colimits of representables for it to hold (as in Tobias' counterexample). It's a nice sandbox for thinking about size issues around the presheaf construction.

Tobias Fritz (Aug 14 2024 at 13:07):

Tobias Fritz said:

It's probably possible to choose $F_k$ such that the cardinalities $|F_k(A)|$ are all powers of a fixed prime depending on $k$.

And here's a way to achieve that, for any prime or general natural number $p$, based on the construction of $F_k = P P_k$ we've discussed earlier. We just replace the $2$ in the definition of the power set functor $P : \mathsf{FinRel}^{\mathrm{op}} \to \mathsf{FinSet}$ by $[p] = \{0,\dots, p-1\}$, where the action on morphisms can be defined as follows: for $R : A \to B$, map a given $S : B \to [p]$ to $R^* S : A \to [p]$ defined by $(R^* S)(a) = \max \{S(b) \mid a R b\}$.

Tobias Fritz (Aug 14 2024 at 13:09):

On objects, this takes every finite set $A$ to the set of maps $A \to [p]$, so the cardinality is $p^{|A|}$.

Tobias Fritz (Aug 14 2024 at 14:23):

So, to summarize:

1. For every $k \in \mathbb{N}$, there is a functor $F_k : \mathsf{FinSet} \to \mathsf{FinSet}$ such that the cardinality of every $F_k(A)$ is a power of the $k$-th prime, and equal to $1$ if and only if $|A| < k$.
2. Hence for any indexing sequence $k(n)$ with $\liminf_{n \to \infty} k(n) = \infty$, the functor $F \coloneqq \prod_{n=0}^\infty F_{k(n)}$ still lands in $\mathsf{FinSet}$.
3. For any two distinct choices of strictly increasing indexing sequence, the two resulting functors are not isomorphic. Therefore there are uncountably many isomorphism classes of functors $\mathsf{FinSet} \to \mathsf{FinSet}$. In particular there are uncomputable ones.
4. By instead making $k(n)$ grow slowly with $n$, we can make $|F(A)|$ grow arbitrarily fast with the cardinality of $A$, and in particular faster than the busy beaver function. Making such a choice gives an explicit example of an uncomputable functor. (That is as explicit as it can get, given the uncomputability.)

John Baez (Aug 14 2024 at 15:15):

That's an excellent roundup of the conversation, @Tobias Fritz!