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: learning: questions

Topic: Endofunctors of FinSet

John Baez (Aug 15 2024 at 11:06):

This is a question about endofunctors on FinSet, but I think it will be easier if we work with a skeleton $\mathsf{F}$ of FinSet. So let's say $\mathsf{F}$ is the category with one object

$n := \{0,1,\dots, n-1\}$

for each natural number, and all functions between these finite sets as morphisms.

Question. Is there an endofunctor $g: \mathsf{F} \to \mathsf{F}$ which on objects works like this:

$g(n) = 1$ if $n \lt 3$

$g(n) = 2$ if $n \ge 3$

?

(I doubt using the number $3$ is very important, but I wanted a small number bigger than $1$ and I didn't want to use $2$ because we're already using that for something else.)

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

Some motivation: talking to @Tobias Fritz here, I got interested in this question: for which sequences $a_n$ of natural numbers is there a functor $g: \mathsf{F} \to \mathsf{F}$ with $g(n) = a_n$?

In an offhand remark on Mathstodon, Bartosz Milewski guessed that such a functor always exists. I asked him if there is a functor $g$ with

$g(n) = 1$ if $n = 100$
$g(n) = 0$ otherwise

and he agreed that no such functor exists. That got me interested in some other examples.

Todd Trimble (Aug 15 2024 at 11:58):

I just got up a few minutes ago, so this might affect the quality, but if $\mathbf{2} = (0 \to 1)$ is the walking arrow, then the evident inclusion $\mathbf{2} \hookrightarrow \mathsf{F}$ has a left adjoint that sends a finite set $n$ to the image of $n \to 1$. Let $M$ be the monad on $\mathsf{F}$ obtained by composing these functors. It should remind you of the Heaviside function.

Let $I = \mathrm{Inj}(3, -): \mathsf{F} \to \mathsf{F}$ be the functor that takes a finite set $n$ to the set of injective functions $3 \to n$. Then form this composite:

$\mathsf{F} \overset{I}{\to} \mathsf{F} \overset{M}{\to} \mathsf{F} \overset{(-)+1}{\to} \mathsf{F}.$

I think this should do the trick.

Amar Hadzihasanovic (Aug 15 2024 at 12:30):

How is $I$ a functor on $\mathsf{F}$? We have $\mathrm{Inj}(3, 3) = 3!$ but $\mathrm{Inj}(3, 1) = \varnothing$, so there can be no way to interpret $Ip$ for $p: 3 \to 1$ the only function of its type.

Amar Hadzihasanovic (Aug 15 2024 at 12:33):

I do not have an example of a counterexample for the specific question that John is asking, but I have thought of some constraints.

One simple observation is that because all epimorphisms/monomorphisms between non-empty sets in $\mathsf{F}$ are split, they must be preserved by $g$. And because in $\mathsf{F}$ there exists a (split) mono from $n$ to $m$ if and only if $n \leq m$, it follows that $n \mapsto g(n)$ must be a non-decreasing sequence for all $n \geq 1$.

Amar Hadzihasanovic (Aug 15 2024 at 12:39):

A less obvious constraint (if I haven't made a mistake in my argument) is the following:

If $n \geq 5$ and $g(n) < n$, then $g(m) = g(n)$ for all $m \geq n - 2$.

That is, any endofunctor whose associated sequence does not satisfy $n \leq g(n)$ for all $n \geq 5$ must be “eventually constant”, starting from $n - 2$ where $n$ is such that $g(n) < n$.
This does not exclude John's example -- but it would exclude any variation in which the $n$ at which the value changes is strictly larger than 3...

(ERRATA For now I have an argument only for something weaker, see later messages)

John Baez (Aug 15 2024 at 12:41):

I like your "simple observation", Amar. In my conversation with Tobias we naturally gravitated to nondecreasing sequences, but now I know better why!

Amar Hadzihasanovic (Aug 15 2024 at 12:41):

The argument is the following.
By restricting to just the automorphisms of $n$, every such endofunctor defines a sequence of group homomorphisms $\mathrm{Aut}(n) = S_n \to S_{g(n)} = \mathrm{Aut}(g(n))$.

John Baez (Aug 15 2024 at 12:44):

I know that there are nontrivial homomorphisms $S_n \to S_m$ with $m < n$ only for $m = 2$ (for all $n$) and $m = 3$ (for $n = 4$). But I haven't put this to use yet to understand what you're claiming. I'd love to use this juicy fact for something.

Amar Hadzihasanovic (Aug 15 2024 at 12:45):

Suppose $g(n) < n$. Then the homomorphism $S_n \to S_{g(n)}$ cannot be injective, so it must have non-trivial kernel. If $n \geq 5$, the only non-trivial normal subgroups of $S_n$ are the entire group and the alternating group $A_n$. So $g$ must take any even permutation of $n$ to the identity of $g(n)$.

Amar Hadzihasanovic (Aug 15 2024 at 12:49):

So suppose $n \geq 5$ and $g(n) < n$ and consider an injection $i: n -2 \to n-1$.
Then, take a surjective map $p: n-1 \to n-2$ which only identifies two elements of $n-1$, and let $f = i \circ p$, a function $n - 1 \to n - 1$.

Amar Hadzihasanovic (Aug 15 2024 at 12:51):

I claim that we can factorise $f$ as an injective map $j: n-1 \to n$ followed by a surjective map $q: n \to n-1$, and we can find an even permutation $\sigma$ of $n$ such that $q \circ \sigma \circ j$ is an isomorphism.

Amar Hadzihasanovic (Aug 15 2024 at 12:53):

(Basically, $j$ only misses one element of $n$, and $q$ only identifies two elements of $n$, and we can “rearrange” the elements of $n$ in the middle in such a way that one of the elements identified by $q$ is the one missed by $j$)

Amar Hadzihasanovic (Aug 15 2024 at 12:55):

But then $g(i) \circ g(p) = g(f) = g(q) \circ g(j) = g(q) \circ g(\sigma) \circ g(j)$ because $g(\sigma)$ is the identity, and the latter is an isomorphism, which implies that $g(i)$ is an isomorphism (it is injective by my “simple observation” and surjective because it has a section, namely $g(p)$), so $g(n-1) = g(n-2)$.

Amar Hadzihasanovic (Aug 15 2024 at 12:58):

Now, I thought I had an argument why this can be used to trigger an inductive step and show that $g$ is “eventually constant” but perhaps I didn't :D

Amar Hadzihasanovic (Aug 15 2024 at 13:01):

(Of course, it does work at least to show that if $g(n) < n$ for all $n \geq N$, then $g(n) = g(N-2)$ for all $n \geq N-2$)

John Baez (Aug 15 2024 at 13:04):

Wow, this is cool but I'll need to think about it sometime when I'm not busy writing a math paper! Just to check: is it true that you are now only claiming that

If $n \geq 5$ and $g(n) < n$, then $g(n-1) = g(n-2)$

but not

If $n \geq 5$ and $g(n) < n$, then $g(m) = g(n)$ for all $m \geq n - 2$.

?

Amar Hadzihasanovic (Aug 15 2024 at 13:06):

Yes, that's correct, and what I am claiming implies

If $N \geq 5$ is such that $g(n) < n$ for all $n \geq N$, then $g(n) = g(N-2)$ for all $n \geq N-2$.

Amar Hadzihasanovic (Aug 15 2024 at 13:26):

I think it should be possible to extend the argument as follows: for all $k \geq 1$ and $m \geq 0$ such that $n := 3k + m \geq 5$ and $g(n) < n$, we have $g(k + m) = g(2k + m)$.

(The argument above is the case $k = 1$ and $m = n - 3$. For the generalisation, replace the injection $i: n - 2 \to n -1$ with an injection $i: k + m \to 2k + m$.)

Amar Hadzihasanovic (Aug 15 2024 at 13:26):

I'm sure one can tweak it further...

Amar Hadzihasanovic (Aug 15 2024 at 13:30):

On the other hand, this should be able to exclude John's example with $k := 2$ and $m := 0$, since $g(6) = 2 < 6$ but $g(2) \neq g(4)$.

Amar Hadzihasanovic (Aug 15 2024 at 13:35):

Ok, I think I can instantiate this to a concrete counterexample to John's sequence.

Amar Hadzihasanovic (Aug 15 2024 at 13:39):

We let

• $i: 2 \to 4$ be defined by $i(0) = 0$ and $i(1) = 2$,
• $p: 4 \to 2$ be defined by $p(0) = p(1) = 0$ and $p(2) = p(3) = 1$,
• $j: 4 \to 6$ be defined by $j(0) = 0$, $j(1) = 1$, $j(2) = 3$, $j(3) = 4$,
• $q: 6 \to 4$ be defined by $q(0) = q(1) = 0$, $q(2) = 1$, $q(3) = q(4) = 2$, $q(5) = 3$,
• $\sigma: 6 \to 6$ be the even permutation $(12)(45)$

Amar Hadzihasanovic (Aug 15 2024 at 13:43):

Then we have $i \circ p = q \circ j: 4 \to 4$, and $q \circ \sigma \circ j$ is equal to the identity on $4$.

Amar Hadzihasanovic (Aug 15 2024 at 13:46):

Since $g$ induces a homomorphism $S_6 \to S_{g(6)} = S_2$, and the kernel of this homomorphism must contain $A_6$, $g(\sigma)$ is the identity on 2.

Amar Hadzihasanovic (Aug 15 2024 at 13:48):

It follows that $g(i) \circ g(p) = g(q) \circ g(j) = g(q) \circ g(\sigma) \circ g(j) = g(q \circ \sigma \circ j) = g(\mathrm{id}_4) = \mathrm{id}_2$, but then $g(i): g(2) = 1 \to g(4) = 2$ has $g(p)$ as a section, which is impossible.

Amar Hadzihasanovic (Aug 15 2024 at 14:40):

Btw this is how I think of the functions $p, i, j, q, \sigma$ graphically, seeing $\mathsf{F}$ as the symmetric monoidal category generated by a commutative monoid.

.be58628b-773d-4cb3-966c-b89bd273ff45.jpg

Amar Hadzihasanovic (Aug 15 2024 at 14:42):

($\sigma$ should have $m$ wires at the right end which I forgot to draw)

Tobias Fritz (Aug 15 2024 at 15:07):

Conjecture: Every bounded endofunctor of $\mathsf{FinSet}$ is constant on all nonempty sets (and morphisms between them). Equivalently, every such functor is a finite coproduct of the terminal functor (which sends everything to 1) and the subterminal functor which maps $\emptyset \mapsto 1$ and takes everything else to $\emptyset$.

Tobias Fritz (Aug 15 2024 at 15:07):

Does this look plausible now? It's possible that I'm missing some obvious counterexample.

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

It's a bit annoying that the empty set plays a special role: a functor $F : \mathsf{FinSet} \to \mathsf{FinSet}$ can be pretty arbitrary on the empty set, which doesn't have any morphisms into it. So maybe it would be more elegant to remove the empty set from $\mathsf{FinSet}$? Like this, the conjecture is that every bounded functor $\mathsf{FinSet}\setminus \emptyset \to \mathsf{FinSet}$ is a finite coproduct of the terminal functor with itself.

Tobias Fritz (Aug 15 2024 at 15:24):

(I've corrected a silly error in the conjecture and comments.)

Amar Hadzihasanovic (Aug 15 2024 at 16:20):

One more consequence of my earlier observation: if $g$ is bounded, then eventually (when $n$ is strictly larger than the bound) $g(n) < n$, so $g$ is eventually constant.

What is the eventual value of $g$? Well, let $N := \min \{ m \mid g(n) < n \text{ for all } n \geq m \}$.
Then $g$ is constant after $N-2$ with value $g(N-2)$. But $g(N-1) = g(N) < N$, yet $g(N-1) \geq N-1$ by definition of $N$. It follows that $g(N-1) = N-1$, that is, the eventual value of $g$ is $N-1$.

Amar Hadzihasanovic (Aug 15 2024 at 16:30):

(I guess this needs $N$ to be at least 5 for my argument to apply)

Tobias Fritz (Aug 15 2024 at 16:45):

Do you know of any examples that are eventually constant, but not actually constant (on nonempty sets)?

Amar Hadzihasanovic (Aug 15 2024 at 16:48):

No, I think your conjecture sounds very plausible, I'm trying to make steps towards proving it.

Amar Hadzihasanovic (Aug 15 2024 at 16:50):

This says that if $g$ is eventually constant with value $m \geq 4$, it must have already stabilised at $m-1$, so it restricts how "long" such an endofunctor can vary...

Tobias Fritz (Aug 15 2024 at 16:55):

I'm probably being dense, but doesn't eventually constant in particular mean that the functor $g$ takes every constant map $n \to n$ (with sufficiently large $n$) to the identity? Then since splitting of idempotents is an absolute (co)limit, it would follow that $g(1) = g(n)$?

Tobias Fritz (Aug 15 2024 at 16:59):

I mean that a constant map $n \to n$ is an idempotent that is split by $1$, and $g$ must preserve this splitting. But if $g$ sends the constant map to the identity, then we get $g(1) \cong g(n)$.

Clémence Chanavat (Aug 15 2024 at 16:59):

If the goal is merely to prove $(g(n))_n$ eventually constant when bounded, since it is not decreasing as Amar observed, it is already implied by the usual properties of sequences of natural numbers.

Tobias Fritz (Aug 15 2024 at 17:05):

Right, every bounded monotone sequence of natural numbers is eventually constant. But I think what we'd like to have is the stronger statement that such a functor $g$ is an eventually constant functor, meaning that it takes every map between sufficiently large sets to one and the same identity map. (This is in terms of language assuming a skeleton, as John suggested originally.) Is this obvious as well?

Clémence Chanavat (Aug 15 2024 at 17:20):

Yes I agree, I specifically did not say anything about morphisms because I did not have anything relevant to say about that, I don't think it is obvious at all. The only thing I can say is that if $g$ is always constant on objects, then it sends epis and monos to iso (for cardinality reasons again), thus every map to an iso (by the epi-mono factorisation). I have no idea how to show that these isos are always the identity

Tobias Fritz (Aug 15 2024 at 17:21):

Ha, actually they're not always identity! Because even with functors $\mathsf{F} \to \mathsf{F}$, where $\mathsf{F}$ is a skeleton of $\mathsf{FinSet}$, we still can have 'constant' functors that act like $g(n) = k$ for fixed $k$ on objects, and as $g(f : n \to m) = \sigma_m \sigma_n^{-1}$, where $\sigma_n \in \mathsf{F}(k, k)$ is an arbitrary sequence of automorphisms, on morphisms.

Tobias Fritz (Aug 15 2024 at 17:22):

These are precisely the functors that are naturally isomorphic to functors that are actually constant in the sense of mapping every morphism to an identity.

Tobias Fritz (Aug 15 2024 at 17:22):

So I suppose the right definition of 'constant functor' is a functor that is naturally isomorphic to one which sends all morphisms to one and the same identity morphism.

Kevin Carlson (Aug 15 2024 at 18:50):

Your conjectured Liouville’s theorem for FinSet is very beautiful, @Tobias Fritz!

Tobias Fritz (Aug 15 2024 at 20:03):

Among the many Liousville's theorems, I suppose you're referring to the complex analysis one, @Kevin Carlson ? That's a really interesting analogy actually, because maybe there is some connection with analytic functors (about which I know nothing)?

Kevin Carlson (Aug 15 2024 at 20:17):

Yes, I was struck by how much it sounds like “every bounded complex analytic function is constant.”

Kevin Carlson (Aug 15 2024 at 20:18):

Conceivably there is a relation, but I also have no idea.

Jean-Baptiste Vienney (Aug 15 2024 at 20:20):

Maybe linked to some differential linear logic (although you very probably don't need any of this to prove your conjecture) :smirk:

Marcelo Fiore, Nicola Gambino, Martin Hyland, Monoidal bicategories, differential linear logic, and analytic functors: arXiv:2405.05774

Jean-Baptiste Vienney (Aug 15 2024 at 20:22):

Maybe there exists a differential linear logic Liouville theorem and this conjecture as well as the theorem in complex analysis would be special cases of it :smirk:

Jean-Baptiste Vienney (Aug 15 2024 at 20:26):

But don't worry about this, I just write it for me :face_in_clouds:

Todd Trimble (Aug 16 2024 at 02:38):

Amar Hadzihasanovic said:

How is I a functor on F? We have Inj(3,3)=3! but Inj(3,1)=∅, so there can be no way to interpret Ip for p:3→1 the only functio

Oops, yes; thanks. That I warned that the quality of my response might be affected by having just woken up now seems prescient (and I should listen to such warnings!). Oh, well.

Amar Hadzihasanovic (Aug 16 2024 at 06:57):

Ok, I think I can improve my earlier argument to prove Tobias's conjecture.

Amar Hadzihasanovic (Aug 16 2024 at 07:02):

Suppose $g$ is bounded, so it is eventually constant with value $N$.
Let $m \geq 1$, and pick $k \geq 0$ such that $g(2k + m) = N$ and $g(4k + m) < 4k + m$; this is always possible by picking $k$ large enough.

Amar Hadzihasanovic (Aug 16 2024 at 07:12):

Then define the following functions:

• $i: m \to 2k + m$ by $i(j) := j$ for all $j \in \{0, \ldots, m-1\}$,
• $p: 2k + m \to m$ by $p(j) := j$ for $j \in \{0, \ldots, m-1 \}$ and $p(j) := m-1$ for $j \in \{m, \ldots, 2k + m - 1\}$,
• $q: 2k + m \to 4k + m$ by $q(j) := j$ for all $j \in \{0, \ldots, 2k + m - 1\}$,
• $\ell: 4k + m \to 2k + m$ by $\ell(j) := j$ for $j \in \{0, \ldots, m-1 \}$, $\ell(j) := m-1$ for $j \in \{m, \ldots, 2k + m - 1\}$, and $\ell(j) := j - 2k$ for $j \in \{2k + m, \ldots, 4k + m - 1\}$,
• $\sigma: 4k + m \to 4k + m$ is the permutation exchanging $m + j$ and $2k + m + j$ for all $j \in \{0, \ldots, 2k - 1\}$.

Notice that $\sigma$ is the product of $2k$ transpositions so it is even.

Amar Hadzihasanovic (Aug 16 2024 at 07:15):

Then, as in the earlier argument, we have $i \circ p = q \circ \ell$ but $q \circ \sigma \circ \ell = \mathrm{id}_{2k+m}$.

Amar Hadzihasanovic (Aug 16 2024 at 07:19):

Moreover, by the same argument as before about homomorphisms of symmetric groups, $g(\sigma) = \mathrm{id}_{g(4k+m)}$.

It follows that $g(i \circ p) = g(i) \circ g(p) = \mathrm{id}_{g(2k+m)}$, which implies that $g(i): g(m) \to g(2k +m) = N$ is an isomorphism, so $g(m) = N$.

Amar Hadzihasanovic (Aug 16 2024 at 07:21):

Because $m \geq 1$ was arbitrary, $g$ is constant with value $N$ on non-empty sets.

Amar Hadzihasanovic (Aug 16 2024 at 07:33):

As Tobias was noting, $g$ can do what it wants on $0$ and the unique function $0 \to 1$, and can send functions between non-empty sets to arbitrary automorphisms of $N$.

This is because we can always apply the unit of the adjunction between preorders and categories to $\mathsf{F}$, which sends it to the preorder $0 < 1 \simeq 2 \simeq \ldots \simeq n \simeq \ldots$, and then a functor from this preorder to $\mathsf{F}$ is exactly a choice of a function $g(0) \to g(1) = N$ and an arbitrary sequence of automorphisms of $N$.

Oscar Cunningham (Aug 16 2024 at 07:41):

I half-remember some result about endofunctors of FinSet and absolutely monotonic sequences. A sequence is absolutely monotonic if its differences $a_{i+1} - a_i$ are all positive, and the differences of its differences, and so on. I can't remember the result or find a reference though. Perhaps it was that all such sequences extend to functors?

Amar Hadzihasanovic (Aug 16 2024 at 07:44):

In fact as we have seen we can relax "bounded" to "eventually sub-identity", that is, the stronger statement is the following:

Suppose $g: \mathsf{F} \to \mathsf{F}$ is an endofunctor. If there exists $m$ such that, for all $n \geq m$, $g(n) < n$, then $g$ is constant on non-empty sets.

Clémence Chanavat (Aug 16 2024 at 07:50):

Oscar Cunningham said:

I half-remember some result about endofunctors of FinSet and absolutely monotonic sequences. A sequence is absolutely monotonic if its differences $a_{i+1} - a_i$ are all positive, and the differences of its differences, and so on. I can't remember the result or find a reference though. Perhaps it was that all such sequences extend to functors?

maybe you are referring to this paper , the Theorem 1.2 indeed gives a sufficient and necessary condition involving the iterated differences!

Amar Hadzihasanovic (Aug 16 2024 at 07:54):

Oh that's too bad, so the question has already been answered completely :D

Tobias Fritz (Aug 16 2024 at 08:12):

Very nice find! There seems to be a fun story behind that paper:

I would like to thank George Bergman for suggesting this problem (on a
homework assignment—I did not get much other homework done in that course)

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

Wow, it's been answered! I am not surprised that Randall Dougherty did it, because he was a math prodigy and I mainly know him for his mind-blowing work on this sequence:

1, 1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, …

John Baez (Aug 16 2024 at 09:11):

This sequence is defined in a fairly simple purely combinatorial way, where the nth term involves the free shelf on n elements. A shelf is a set with a binary operation that distributes over itself.

For details of how the sequence is defined, go here:

• John Baez, Shelves and the infinite

John Baez (Aug 16 2024 at 09:15):

It looks like this sequence increases to 16 and then stops, but assuming the existence of an extremely large cardinal, called a 'I3 rank-into-rank cardinal' Richard Laver showed in the late 1980s that it grows unboundedly! My article gives a simple explanation of what an I3 rank-into-rank cardinal is.

So, this is an extremely slow-growing sequence whose basic properties may go beyond what we can study in ZFC without extra axioms.

John Baez (Aug 16 2024 at 09:16):

What Randall Dougherty did is prove a lower bound on how far you have to go into the sequence before it increases beyond 16. His lower bound was A(9,A(8,A(8,255))) where A(-,-) is a certain two-variable Ackermann function.

John Baez (Aug 16 2024 at 09:17):

So, Dougherty is the kind of guy who can sink his teeth into really hard combinatorial problems and not let go.

John Baez (Aug 16 2024 at 09:24):

We should not feel bad that he beat us to the solution of this problem. Thanks for finding his paper, @Clémence Chanavat!

Tom Hirschowitz (Aug 16 2024 at 11:38):

I (shamefully) can't read the theorems: do they also solve the conjecture about bounded analytic functors?

This seems to follow relatively easily once the definition is known: an endofunctor of FinSet is

• near-representable when it is a quotient of a representable functor $𝐲ₙ$ by some subgroup of the automorphism group $𝔖ₙ$ of $n$, and
• analytic when it is a pointwise coproduct of near-representable functors.

In order to land in FinSet, such coproducts need to be finite.

Let us now consider any bounded, analytic endofunctor $F \cong \coprod_i 𝐲_{nᵢ}/{Gᵢ}$ on FinSet, where $𝐲_n/{G}$ denotes the quotient of $𝐲ₙ$ by the subgroup $G$ of $𝔖ₙ$.

For any non-empty $n$ and subgroup $G$ of $𝔖ₙ$, $𝐲ₙ/{G}$ cannot be bounded, so all $nᵢ$'s are empty and $F$ is constant.

Am I making any sense?

John Baez (Aug 16 2024 at 11:43):

Tom Hirschowitz said:

I (shamefully) can't read the theorems: do they also solve the conjecture about bounded analytic functors?

Which theorems can't you read? Let me tell you Dougherty's theorem about which sequences are functorial.

Valery Isaev (Aug 16 2024 at 11:45):

This mathoverflow question seems to be related to the discussion https://mathoverflow.net/questions/346290/when-is-an-integer-sequence-the-trace-of-a-monad-on-finset

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

Let's say a function $a : \mathbb{N} \to \mathbb{N}$ is functorial if there's some functor $g: \mathsf{FinSet} \to \mathsf{FinSet}$ that sends each set with $n$ elements to a set with $a(n)$ elements.

Dougherty's Theorem 1.2 gives necessary and sufficient conditions for a function $a : \mathbb{N} \to \mathbb{N}$ to be functorial.

We've seen that the case $a(0)$ is funny, so Dougherty allows us to tweak that value:

Theorem. A function $a : \mathbb{N} \to \mathbb{N}$ is functorial if and only if there exists a positive integer $r \le a(1)$ such that if we define a new function $b: \mathbb{N} \to \mathbb{N}$ with

$b(0) = r$
$b(n) = a(n)$ for $n \gt 0$

then

$(\Delta^k b)(0) \ge 0$

for all $k = 0, 1, 2, ...$.

Here $\Delta$ is the difference operator, defined on functions $f: \mathbb{N} \to \mathbb{N}$ by

$(\Delta f)(n) = f(n+1) - f(n)$

$\Delta^k$ is the $k$ th power of that operator, e.g.

$(\Delta^2 f)(n) = f(n+2) - 2 f(n+1) + f(n)$

John Baez (Aug 16 2024 at 11:58):

Now, it's possible that since we know the theorem, we can prove it more beautifully than Dougherty did, using more category theory.

Here's an obvious question: can we categorify the difference operator?

Given a functor $g : \mathsf{FinSet} \to \mathsf{FinSet}$, can we find a functor

$\Delta g : \mathsf{FinSet} \to \mathsf{FinSet}$

such that

$g(n+1) \cong g(n) + (\Delta g)(n)$ ?

It would be nicest if this isomorphism were a natural isomorphism, but we don't even need that for this to imply that

$|g(n+1)| \ge |g(n)|$

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

I feel that what I'm asking is closely related to Amar's slick proof that any functorial sequence is nondecreasing:

Amar Hadzihasanovic said:

One simple observation is that because all epimorphisms/monomorphisms between non-empty sets in $\mathsf{F}$ are split, they must be preserved by $g$. And because in $\mathsf{F}$ there exists a (split) mono from $n$ to $m$ if and only if $n \leq m$, it follows that $n \mapsto g(n)$ must be a non-decreasing sequence for all $n \geq 1$.

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

Unfortunately while Amar's argument here shows there is a (split) mono from $g(n)$ to $g(n+1)$, it doesn't seem to give a natural mono $g(n) \to g(n+1)$, much less a functor that plays the role of $\Delta g$, namely

"$(\Delta g)(n) = g(n+1) - g(n)$"

with quotes because subtraction involves a choice of splitting.

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

Hmm, here's a weird idea: we just drop the requirement that $\Delta g$ be a functor! We just define it as some map from finite sets to finite sets. It will still have the property that the cardinality of $(\Delta g)(n)$ is nonnegative, which is enough to ensure the cardinalities $|g(n)|$ are increasing. But are we then able to define $\Delta^2 g$, or do we get stuck? Dougherty's theorem seems to imply that $\Delta^k$ is a good thing to study for all $k = 0 , 1, 2, ....$

Oscar Cunningham (Aug 16 2024 at 12:10):

@John Baez Is that really all that Dougherty's theorem says? It looks like there's some more stuff about the function he calls $\Phi$.

Amar Hadzihasanovic (Aug 16 2024 at 13:14):

@John Baez One thought I have is whether it is worth thinking about endofunctors of finite sets and partial functions, first; let's call their category $\mathsf{P}$.

There is a free-forgetful adjunction between $\mathsf{F}$ and $\mathsf{P}$, where the latter is seen as the Kleisli category of the $- + 1$ (maybe) monad on $\mathsf{F}$, so in a certain sense any endofunctor of one can be transported to the other along the adjunction.

Now, suppose $g$ is an endofunctor on $\mathsf{P}$. There is a pointed endofunctor $- + 1$ on $\mathsf{P}$, with natural inclusions $\eta_n: n \to n + 1$ which are total injective functions.
I would propose defining $\Delta g$ as sending

• $n$ to the complement of the image of $g(\eta_n): g(n) \to g(n + 1)$ in $g(n + 1)$,
• a partial function $f: n \to m$ to the partial function obtained by restricting $g(f + 1)$ to $\Delta g(n)$ and “corestricting” it to $\Delta g(m)$, that is, making the restriction undefined whenever the image of an element is not in $\Delta g(m)$.

It seems plausible to me that this is in fact an endofunctor on $\mathsf{P}$, although I haven't checked carefully -- by naturality of $\eta_n$, it is at least true that $g(f + 1)$ maps the image of $g(\eta_n)$ to the image of $g(\eta_m)$, which prevents an element from “leaving” $\Delta g$ and then “returning” to it -- this would disrupt functoriality.

Amar Hadzihasanovic (Aug 16 2024 at 13:16):

By construction, this would satisfy $g(n+1) = g(n) + \Delta g(n)$.

ADDENDUM: ...as long as $g(\eta_n)$ is total and injective. I think these should both always be true as long as $\eta_n$ is a split mono, which is true when $n \geq 1$.

Otherwise, perhaps we have to restrict to $g$ sending $0 \to 1$ to a total injective function? (Again what endofunctors do on 0 seems to be always a sticking point.)

Amar Hadzihasanovic (Aug 16 2024 at 13:25):

So, if this is correct, let $F: \mathsf{F} \to \mathsf{P}$ and $U: \mathsf{P} \to \mathsf{F}$ be the left and right adjoint functors, and suppose $g$ is an endofunctor on $\mathsf{F}$.

Then we get an endofunctor $FgU$ on $\mathsf{P}$, which at the level of objects sends $n$ to $g(n + 1)$, so there is just a “shift by 1” of everything -- this may hint at why 0 is a bit of a special case...

Amar Hadzihasanovic (Aug 16 2024 at 13:27):

And then for this endofunctor we can take a “functorial difference”, which gives another endofunctor on $\mathsf{P}$. The fact that this can be iterated would explain why all the iterated differences must be positive.

John Baez (Aug 16 2024 at 13:32):

Oscar Cunningham said:

John Baez Is that really all that Dougherty's theorem says? It looks like there's some more stuff about the function he calls $\Phi$.

Oh, ugh! You're right. I thought conditions (1) and (2) were equivalent characterizations of functorial sequences but he says a sequence is functorial if one or the other of these conditions hold. Condition (1) is the one I stated, and condition (2) is more complicated and involves something called $\Phi$.

John Baez (Aug 16 2024 at 13:34):

Since I don't want to think about condition (2) right now, I'd be happy to show that condition (1) implies functoriality, i.e.:

John Baez (Aug 16 2024 at 13:37):

We say a function $a : \mathbb{N} \to \mathbb{N}$ is functorial if there's some functor $g: \mathsf{FinSet} \to \mathsf{FinSet}$ that sends each set with $n$ elements to a set with $a(n)$ elements.

Theorem. A function $a : \mathbb{N} \to \mathbb{N}$ is functorial if there exists a positive integer $r \le a(1)$ such that if we define a new function $b: \mathbb{N} \to \mathbb{N}$ with

$b(0) = r$
$b(n) = a(n)$ for $n \gt 0$

then

$(\Delta^k b)(0) \ge 0$

for all $k \in \mathbb{N}$, where $\Delta$ is the difference operator, defined on functions $f: \mathbb{N} \to \mathbb{N}$ by

$(\Delta f)(n) = f(n+1) - f(n)$

Amar Hadzihasanovic (Aug 16 2024 at 13:58):

This picture should illustrate why $\Delta g$ is functorial on partial functions...
Screenshot-from-2024-08-16-16-54-27.png
Some of the elements of $\Delta g(n)$ may be mapped by $g(f+1)$ to elements of $g(m)$ resulting in $\Delta g(f)$ being undefined on them, but once they are, they “stay there”.

So $\Delta g(h \circ f)$ is completely specified by the pair of $\Delta g(h)$ and $\Delta g(f)$.

Amar Hadzihasanovic (Aug 16 2024 at 14:00):

The fact that $g(n)$ can be identified with its image through $g(\eta_n)$ in $g(n+1)$ relies on $g(\eta_n)$ being total and injective, which is ensured by $\eta_n$ being a split mono when $n \geq 1$, but probably needs to be made an extra assumption for $\eta_0$.

By the way this “extra assumption” looks very similar to the fact that the sequence $a$ needs to be “redefined” on 0 so that $b(0) \leq b(1)$ in the theorem we are looking at!

Amar Hadzihasanovic (Aug 16 2024 at 14:08):

(But even if that is not true of $g$, the only thing that changes is that $g(1) = \mathrm{im} g(\eta_0) + \Delta g(0)$, where the image of $g(\eta_0)$ may be smaller than $g(0)$ itself).

Amar Hadzihasanovic (Aug 16 2024 at 14:11):

So if I haven't made any mistakes, I'm claiming the following:

Let $\mathsf{P}$ be the category of finite sets and partial functions and let $g$ be an endofunctor on $\mathsf{P}$.

Then there exists an endofunctor $\Delta g$ on $\mathsf{P}$ which, for all $n \geq 1$, satisfies $g(n+1) = g(n) + \Delta g(n)$ at the level of objects.

Moreover, if $\eta: 0 \to 1$ is the only (partial) function of its type, and $g(\eta)$ is total and injective, then also $g(1) = g(0) + \Delta g(0)$.

Amar Hadzihasanovic (Aug 16 2024 at 14:18):

Moreover,

Let $g$ be an endofunctor on $\mathsf{F}$, the category of finite sets and functions.
Then there exists an endofunctor $\hat{g}$ on $\mathsf{P}$ which satisfies $\hat{g}(n) = g(n+1)$ for all $n \geq 0$ at the level of objects.

Moreover, this endofunctor is such that $\hat{g}(\eta)$ is total and injective.

Proof: define $\hat{g}$ as $FgU$. The latter fact comes from $U(\eta)$ being equal to an inclusion $1 \to 2$, which is a split mono, so $FgU(\eta)$ is also a split mono.

Amar Hadzihasanovic (Aug 16 2024 at 14:35):

Dually,

Let $g$ be an endofunctor on $\mathsf{P}$.
Then there exists an endofunctor $\bar{g}$ on $\mathsf{F}$ which satisfies $\bar{g}(n) = g(n) + 1$ for all $n \geq 0$ at the level of objects.

Proof: define $\bar{g}$ as $UgF$.

Amar Hadzihasanovic (Aug 16 2024 at 14:41):

(Maybe the latter fact is not that useful after all.)

Amar Hadzihasanovic (Aug 16 2024 at 14:52):

I feel like I should be able to combine these facts in a way that proves that iterated difference operators on $g(n)$ are positive at least on $n \geq 1$, but I am getting tired and I am struggling to find the best way, so I will stop here for now :D

Ivan Di Liberti (Aug 16 2024 at 15:32):

For this delta operator, please see the last paper by Pare on the arxiv and it might be relevant for the functor to be (thought as) taut, otherwise, a good notion of difference is not well defined.

Amar Hadzihasanovic (Aug 17 2024 at 07:27):

I realised that, unlike in $\mathsf{F}$, in $\mathsf{P}$ the unique function from $0$ to any other object is also a split monomorphism, whose left inverse is the totally undefined partial function, so the extra assumption was unnecessary. The simpler statement is:

Let $\mathsf{P}$ be the category of finite sets and partial functions and let $g$ be an endofunctor on $\mathsf{P}$.

Then there exists an endofunctor $\Delta g$ on $\mathsf{P}$ which for all $n \geq 0$ satisfies $g(n+1) = g(n) + \Delta g(n)$ at the level of objects.

Iterating this construction, this means that, if $a_n := g(n)$ as a sequence of natural numbers, we do have, for all $k, n \geq 0$, that $\Delta^k a_n \geq 0$.

Amar Hadzihasanovic (Aug 17 2024 at 07:31):

Now if $g$ is an endofunctor of $\mathsf{F}$, with associated sequence $a_n := g(n)$, we have seen that there is an endofunctor $\hat{g}$ of $\mathsf{P}$ whose associated sequence is $\hat{a}_n := a_{n+1}$.

It follows that:

Let $\mathsf{F}$ be the category of finite sets and functions, let $g$ be an endofunctor on $\mathsf{F}$, and let $a_n := g(n)$ as a sequence of natural numbers.

Then for all $k \geq 0$ and $n \geq 1$, it holds that $\Delta^k a_n \geq 0$.

Amar Hadzihasanovic (Aug 17 2024 at 07:38):

I'd conjecture that the sufficient condition can also be simplified for endofunctors on $\mathsf{P}$, that is, a sequence $a_n$ is functorial wrt $\mathsf{P}$ if and only if $\Delta^k a_0 \geq 0$ for all $k \geq 0$.

John Baez (Aug 17 2024 at 11:02):

Very nice, @Amar Hadzihasanovic! I have not had time to check your arguments, so I hope that someone (e.g. my future self) does that sometime. I still have some questions. You get an equation on object

$g(n+1) = g(n) + (\Delta g)(n)$

Can you show this sometimes does not extend to a natural isomorphism of endofunctors

$g(n+1) \cong g(n) + (\Delta g)(n)$ ?

(If we did always have a natural isomorphism of endofunctors, that would be worth knowing.)

Amar Hadzihasanovic (Aug 17 2024 at 14:02):

I think the double (contravariant) powerset functor (adapted to $\mathsf{P}$) should be a counterexample.

So

• $g(n)$ is the set of families $\mathcal{F}$ of subsets $S \subseteq n = \{0, \ldots, n-1\}$,
• given $f: n \to m$, $g(f)$ sends $\mathcal{F}$ to $\{T \subseteq m \mid f^{-1}T \in \mathcal{F} \}$,
• $\Delta g(n)$ is the subset of $g(n+1)$ on families $\mathcal{F}$ such that at least one $S \in \mathcal{F}$ contains $n$.

Let $f: 2 \to 1$ be the only total function of its type, and let $\mathcal{F} := \{ \{0, 2 \} \} \in g(3)$.
Then $\mathcal{F} \in \Delta g(2)$, but $g(f + 1)(\mathcal{F}) = \varnothing \not\in \Delta g(1)$, because there is no subset of $2$ whose inverse image through $f + 1$ is $\{0, 2\}$.

So $\Delta g(f)$ must be undefined on $\mathcal{F}$, but $g(f + 1)$ is everywhere defined, so $g(- + 1)$ does not split into $g + \Delta g$.

Amar Hadzihasanovic (Aug 17 2024 at 14:05):

(I looked at the double powerset after @Ivan Di Liberti's suggestion, since it is an example of a functor that is not taut).

Tobias Fritz (Aug 19 2024 at 08:21):

I've been trying to catch up on this a bit, and wonder if there's a simple explanation of why tautness is relevant?

Tobias Fritz (Aug 19 2024 at 08:21):

Given a taut endofunctor on $\mathsf{F}$, does this imply that it can be extended to $\mathsf{P}$? Could this be what's going on?

Amar Hadzihasanovic (Aug 19 2024 at 09:07):

@Tobias Fritz Well, the idea is that the difference operator is always well-defined on endofunctors on $\mathsf{P}$, so in particular one can take an endofunctor of $\mathsf{F}$, transport it to an endofunctor of $\mathsf{P}$ using $g \mapsto FgU$, and apply $\Delta$ on there. But $\Delta (F g U) = F (\Delta g) U$ for some endofunctor $\Delta g$ of $\mathsf{F}$ if (and only if?) $g$ is taut.

Amar Hadzihasanovic (Aug 19 2024 at 09:09):

(Doubt the “only if” part, since only very specific inverse images have to be preserved in order for $\Delta g$ to be well-defined.)

Amar Hadzihasanovic (Aug 19 2024 at 09:14):

On the other hand, since the sequence of $FgU$ is just the sequence of $g$ shifted by one, it seems to me that one can make the argument about iterated differences more cleanly by working with $\mathsf{P}$, and the “shift by one” explains why the value of the sequence at $0$ may need to be readjusted in Dougherty's condition.

Tobias Fritz (Aug 19 2024 at 09:24):

Amar Hadzihasanovic said:

But $\Delta (F g U) = F (\Delta g) U$ for some endofunctor $\Delta g$ of $\mathsf{F}$ if (and only if?) $g$ is taut.

Excellent, thanks, that's what I've been wondering. This seems interesting independently of the current discussion, as it may help explain the significance of tautness more broadly.