← Levels and Natural Transformations of the Functor F_A
AI-generated+AdditionalObservstion.tex
\begin{filecontents*}{fa_refs.bib}
@article{adamek-milius-moss-urbat2015,
author = {Ji{\v r}{\'\i} Ad{\'a}mek and Stefan Milius and Lawrence S. Moss and Henning Urbat},
title = {On finitary functors and their presentations},
journal = {Journal of Computer and System Sciences},
volume = {81},
number = {5},
pages = {813--833},
year = {2015},
doi = {10.1016/j.jcss.2014.12.002}
}
@misc{dahlqvist-neves2018,
author = {Fredrik Dahlqvist and Renato Neves},
title = {Compositional semantics for new paradigms: probabilistic, hybrid and beyond},
year = {2018},
eprint = {1804.04145},
archiveprefix= {arXiv},
primaryclass = {cs.LO}
}
@article{gumm-schroeder2001,
author = {H. Peter Gumm and Tobias Schr{\"o}der},
title = {Monoid-labeled transition systems},
journal = {Electronic Notes in Theoretical Computer Science},
volume = {44},
number = {1},
pages = {185--204},
year = {2001},
doi = {10.1016/S1571-0661(04)80908-3}
}
@misc{hora-kamio-maehara2025,
author = {Ryuya Hora and Yuhi Kamio and Yuki Maehara},
title = {Lawvere's fourth open problem: Levels in the topos of symmetric simplicial sets},
year = {2025},
eprint = {2503.03439},
archiveprefix= {arXiv},
primaryclass = {math.CT}
}
@article{kelly-lawvere1989,
author = {G. M. Kelly and F. W. Lawvere},
title = {On the complete lattice of essential localizations},
journal = {Bulletin de la Soci{\'e}t{\'e} Math{\'e}matique de Belgique. S{\'e}rie A},
volume = {41},
number = {2},
pages = {289--319},
year = {1989}
}
@article{kennett-riehl-roy-zaks2011,
author = {Carolyn Kennett and Emily Riehl and Michael Roy and Michael Zaks},
title = {Levels in the toposes of simplicial sets and cubical sets},
journal = {Journal of Pure and Applied Algebra},
volume = {215},
number = {5},
pages = {949--961},
year = {2011},
doi = {10.1016/j.jpaa.2010.07.002}
}
@misc{kori-watanabe2025,
author = {Mayuko Kori and Kazuki Watanabe},
title = {A No-go Theorem for Coalgebraic Product Construction},
year = {2025},
eprint = {2504.06592},
archiveprefix= {arXiv},
primaryclass = {cs.LO},
note = {To appear in FoSSaCS 2026}
}
@article{menni2019,
author = {Mat{\'\i}as Menni},
title = {Monic skeleta, boundaries, {A}ufhebung, and the meaning of `one-dimensionality'},
journal = {Theory and Applications of Categories},
volume = {34},
number = {25},
pages = {714--735},
year = {2019}
}
@article{menni2024,
author = {Mat{\'\i}as Menni},
title = {The successive dimension, without elegance},
journal = {Proceedings of the American Mathematical Society},
volume = {152},
number = {3},
pages = {1337--1354},
year = {2024},
doi = {10.1090/proc/16638}
}
@article{watanabe-junges-rot-hasuo2025,
author = {Kazuki Watanabe and Sebastian Junges and Jurriaan Rot and Ichiro Hasuo},
title = {A Unifying Approach to Product Constructions for Quantitative Temporal Inference},
journal = {Proceedings of the ACM on Programming Languages},
volume = {9},
number = {OOPSLA1},
pages = {1575--1603},
year = {2025},
doi = {10.1145/3720501}
}
@misc{abramsky2014,
author = {Samson Abramsky},
title = {Arrow's Theorem by Arrow Theory},
year = {2014},
eprint = {1401.4585},
archiveprefix= {arXiv},
primaryclass = {math.CT}
}
@article{leinster2013,
author = {Tom Leinster},
title = {Codensity and the ultrafilter monad},
journal = {Theory and Applications of Categories},
volume = {28},
number = {13},
pages = {332--370},
year = {2013}
}
@book{maclane-moerdijk1992,
author = {Saunders Mac Lane and Ieke Moerdijk},
title = {Sheaves in Geometry and Logic: A First Introduction to Topos Theory},
publisher = {Springer},
year = {1992}
}
@book{johnstone2002,
author = {Peter T. Johnstone},
title = {Sketches of an Elephant: A Topos Theory Compendium},
publisher = {Oxford University Press},
year = {2002}
}
@misc{caramello2010,
author = {Olivia Caramello},
title = {The unification of Mathematics via Topos Theory},
year = {2010},
eprint = {1006.3930},
archiveprefix= {arXiv},
primaryclass = {math.CT}
}
@article{lack-rosicky2011,
author = {Stephen Lack and Ji{\v r}{\'\i} Rosick{\'y}},
title = {Notions of Lawvere Theory},
journal = {Applied Categorical Structures},
volume = {19},
number = {1},
pages = {363--391},
year = {2011},
doi = {10.1007/s10485-009-9215-2}
}
@article{garner2014,
author = {Richard Garner},
title = {Lawvere theories, finitary monads and Cauchy-completion},
journal = {Journal of Pure and Applied Algebra},
volume = {218},
number = {11},
pages = {1973--1988},
year = {2014},
doi = {10.1016/j.jpaa.2014.02.018}
}
@article{joyal1981,
author = {Andr{\'e} Joyal},
title = {Une th{\'e}orie combinatoire des s{\'e}ries formelles},
journal = {Advances in Mathematics},
volume = {42},
number = {1},
pages = {1--82},
year = {1981},
doi = {10.1016/0001-8708(81)90052-9}
}
@article{gambino-kock2013,
author = {Nicola Gambino and Joachim Kock},
title = {Polynomial functors and polynomial monads},
journal = {Mathematical Proceedings of the Cambridge Philosophical Society},
volume = {154},
number = {1},
pages = {153--192},
year = {2013}
}
@misc{kamio-hora2024,
author = {Yuhi Kamio and Ryuya Hora},
title = {A solution to the first Lawvere's problem: A Grothendieck topos that has a proper class many quotient topoi},
year = {2024},
eprint = {2407.17105},
archiveprefix= {arXiv},
primaryclass = {math.CT}
}
@article{arrow1950,
author = {Kenneth J. Arrow},
title = {A Difficulty in the Concept of Social Welfare},
journal = {Journal of Political Economy},
volume = {58},
number = {4},
pages = {328--346},
year = {1950},
doi = {10.1086/256963}
}
@book{arrow1963,
author = {Kenneth J. Arrow},
title = {Social Choice and Individual Values},
edition = {2},
publisher = {Yale University Press},
year = {1963}
}
@article{baryshnikov1993,
author = {Yuliy M. Baryshnikov},
title = {Unifying impossibility theorems: A topological approach},
journal = {Advances in Applied Mathematics},
volume = {14},
number = {4},
pages = {404--415},
year = {1993},
doi = {10.1006/aama.1993.1020}
}
@article{tanaka2006,
author = {Yasuhito Tanaka},
title = {A topological approach to the Arrow impossibility theorem when individual preferences are weak orders},
journal = {Applied Mathematics and Computation},
volume = {174},
number = {2},
pages = {961--981},
year = {2006},
doi = {10.1016/j.amc.2005.05.021}
}
@article{rajsbaum-raventos2026,
author = {Sergio Rajsbaum and Armajac Ravent{\'o}s-Pujol},
title = {A combinatorial topology approach to Arrow's impossibility theorem},
journal = {Social Choice and Welfare},
volume = {66},
pages = {357--394},
year = {2026},
doi = {10.1007/s00355-025-01609-7}
}
@misc{kimelfeld-kolaitis-stoyanovich2018,
author = {Benny Kimelfeld and Phokion G. Kolaitis and Julia Stoyanovich},
title = {Computational Social Choice Meets Databases},
year = {2018},
eprint = {1805.04156},
archiveprefix= {arXiv},
primaryclass = {cs.DB}
}
@article{abramsky-brandenburger2011,
author = {Samson Abramsky and Adam Brandenburger},
title = {The sheaf-theoretic structure of non-locality and contextuality},
journal = {New Journal of Physics},
volume = {13},
pages = {113036},
year = {2011},
doi = {10.1088/1367-2630/13/11/113036}
}
@article{abramsky2014contextual,
author = {Samson Abramsky},
title = {Contextual Semantics: From Quantum Mechanics to Logic, Databases, Constraints, and Complexity},
journal = {Electronic Proceedings in Theoretical Computer Science},
volume = {172},
pages = {21--35},
year = {2014},
doi = {10.4204/EPTCS.172.2}
}
@inproceedings{abramsky-etal2015,
author = {Samson Abramsky and Rui Soares Barbosa and Kohei Kishida and Raymond Lal and Shane Mansfield},
title = {Contextuality, Cohomology and Paradox},
booktitle = {24th EACSL Annual Conference on Computer Science Logic (CSL 2015)},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {41},
pages = {211--228},
year = {2015},
doi = {10.4230/LIPIcs.CSL.2015.211}
}
@article{isham-butterfield1998,
author = {Chris J. Isham and Jeremy Butterfield},
title = {A topos perspective on the Kochen--Specker theorem: I. Quantum states as generalized valuations},
journal = {International Journal of Theoretical Physics},
volume = {37},
number = {11},
pages = {2669--2733},
year = {1998}
}
@misc{isham2010,
author = {Chris J. Isham},
title = {Topos methods in the foundations of physics},
year = {2010},
eprint = {1004.3564},
archiveprefix= {arXiv},
primaryclass = {quant-ph}
}
@article{varacca-winskel2006,
author = {Daniele Varacca and Glynn Winskel},
title = {Distributing probability over non-determinism},
journal = {Mathematical Structures in Computer Science},
volume = {16},
number = {1},
pages = {87--113},
year = {2006}
}
@article{zwart-marsden2022,
author = {Maaike Zwart and Dan Marsden},
title = {No-Go Theorems for Distributive Laws},
journal = {Logical Methods in Computer Science},
volume = {18},
number = {1},
year = {2022},
doi = {10.46298/lmcs-18(1:13)2022}
}
@article{klin-salamanca2018,
author = {Bartek Klin and Juli{\'a}n Salamanca},
title = {Iterated covariant powerset is not a monad},
journal = {Electronic Notes in Theoretical Computer Science},
volume = {341},
pages = {261--276},
year = {2018},
doi = {10.1016/j.entcs.2018.11.013}
}
@article{salamanca2020,
author = {Juli{\'a}n Salamanca},
title = {Lattices do not distribute over powerset},
journal = {Algebra Universalis},
volume = {81},
number = {4},
year = {2020},
doi = {10.1007/s00012-020-00680-8}
}
@inproceedings{goy-petrisan-aiguier2021,
author = {Alexandre Goy and Daniela Petri\c{s}an and Marc Aiguier},
title = {Powerset-Like Monads Weakly Distribute over Themselves in Toposes and Compact Hausdorff Spaces},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {198},
pages = {132:1--132:14},
year = {2021},
doi = {10.4230/LIPIcs.ICALP.2021.132}
}
@inproceedings{karamlou-shah2024,
author = {Amin Karamlou and Nihil Shah},
title = {No Go Theorems: Directed Containers That Do Not Distribute Over Distribution Monads},
booktitle = {Proceedings of the Thirty Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2024)},
pages = {69:1--69:13},
year = {2024},
doi = {10.1145/3661814.3662137}
}
@article{ong-ma-kozen2025,
author = {Shawn Ong and Stephanie Ma and Dexter Kozen},
title = {Probabilistic Kleene Algebra with Angelic Nondeterminism},
journal = {Proceedings of the ACM on Programming Languages},
volume = {9},
number = {PLDI},
pages = {897--919},
year = {2025},
doi = {10.1145/3729286}
}
@inproceedings{jacobs2021,
author = {Bart Jacobs},
title = {From Multisets over Distributions to Distributions over Multisets},
booktitle = {36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2021)},
pages = {1--13},
year = {2021},
doi = {10.1109/LICS52264.2021.9470678}
}
@article{keimel-plotkin2017,
author = {Klaus Keimel and Gordon D. Plotkin},
title = {Mixed powerdomains for probability and nondeterminism},
journal = {Logical Methods in Computer Science},
volume = {13},
number = {1},
year = {2017},
doi = {10.23638/LMCS-13(1:2)2017}
}
@book{barr-wells2005,
author = {Michael Barr and Charles Wells},
title = {Toposes, Triples and Theories},
series = {Reprints in Theory and Applications of Categories},
number = {12},
year = {2005},
pages = {1--288}
}
@article{uustalu-vene2008,
author = {Tarmo Uustalu and Varmo Vene},
title = {Comonadic Notions of Computation},
journal = {Electronic Notes in Theoretical Computer Science},
volume = {203},
number = {5},
pages = {263--284},
year = {2008},
doi = {10.1016/j.entcs.2008.05.029}
}
@incollection{uustalu-vene2006,
author = {Tarmo Uustalu and Varmo Vene},
title = {The Essence of Dataflow Programming},
booktitle = {Central European Functional Programming School},
series = {Lecture Notes in Computer Science},
volume = {4164},
pages = {135--167},
publisher = {Springer},
year = {2006},
doi = {10.1007/11894100_5}
}
@article{jacobs-bases2013,
author = {Bart Jacobs},
title = {Bases as Coalgebras},
journal = {Logical Methods in Computer Science},
volume = {9},
number = {3:23},
pages = {1--21},
year = {2013},
doi = {10.2168/LMCS-9(3:23)2013}
}
@article{abramsky-shah2021,
author = {Samson Abramsky and Nihil Shah},
title = {Relating Structure and Power: Comonadic Semantics for Computational Resources},
journal = {Journal of Logic and Computation},
volume = {31},
number = {6},
pages = {1390--1428},
year = {2021},
doi = {10.1093/logcom/exab048}
}
\end{filecontents*}
\documentclass{amsart}
\usepackage[left=2cm, right=2cm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{amsfonts, amsthm, amssymb, mathtools,etoolbox}
\usepackage{blindtext}
\usepackage{comment}
\usepackage[colorlinks=true, urlcolor=blue, linkcolor=blue, citecolor=blue]{hyperref}
\usepackage{tikz,tikz-cd}
\usepackage{cleveref}
\usepackage{xcolor}
\usepackage{array}
\usepackage[style=alphabetic,sorting=nyt, maxnames=4]{biblatex}
% \usepackage[style=authoryear, maxnames=4]{biblatex}
\renewbibmacro{in:}{}
\addbibresource{fa_refs.bib}
\tikzset{pullback/.style={minimum size=1.2ex,path picture={
\draw[opacity=1,black,-,#1] (-0.5ex,-0.5ex) -- (0.5ex,-0.5ex) -- (0.5ex,0.5ex);%
}}}
\usetikzlibrary{calc,arrows.meta,positioning}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[subsection]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{todo}[theorem]{Todo}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{claim}{Claim}[theorem]
\crefname{claim}{Claim}{Claims}
\renewcommand{\theclaim}{\thetheorem.\alph{claim}}
\theoremstyle{definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{puzzle}[theorem]{Puzzle}
\newtheorem{idea}[theorem]{Idea}
\newtheorem{question}[theorem]{Question}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\dq}[1]{``#1"}
\newcommand{\memo}[1]{\textcolor{red}{memo: #1}}
% \newcommand{\invmemo}[1]{\textcolor{blue}{memo: #1}}
\newcommand{\invmemo}[1]{}
\newcommand{\horamemo}[1]{\textcolor{green!70!black}{hora: #1}}
\newcommand{\para}[1]{\par\medskip\noindent\textbf{#1}\enspace}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\B}{\mathbb{B}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\F}{\mathbf{F}}
\renewcommand{\L}{\mathcal{L}}
\newcommand{\id}{\mathrm{id}}
\newcommand{\op}{\mathrm{op}}
\newcommand{\ob}{\mathrm{ob}}
\newcommand{\Set}{\mathbf{Set}}
\newcommand{\CMon}{\mathbf{CMon}}
\newcommand{\sSet}{\mathbf{sSet}}
\newcommand{\FinSet}{\mathbf{FinSet}}
\newcommand{\FinInj}{\mathbf{FinInj}}
\newcommand{\PSh}{\mathbf{PSh}}
\newcommand{\Sh}{\mathbf{Sh}}
\newcommand{\Cont}{\mathbf{Cont}}
\newcommand{\Func}[2]{[#1,#2]}
\newcommand{\abs}[1]{\left|#1\right|}
\newcommand{\demph}[1]{\textit{#1}}
\font\maljapanese=dmjhira at 2.5ex
\newcommand{\yo}{\textrm{\!\maljapanese\char"48}}
\newcommand{\Pow}{\mathcal{P}}
\newcommand{\ctx}[2]{\left[#1\,\middle|\,#2\right]}
\newcommand{\supp}{\operatorname{supp}}
\newcommand{\Nat}{\operatorname{Nat}}
\newcommand{\Lan}{\operatorname{Lan}}
\newcommand{\Ran}{\operatorname{Ran}}
\newcommand{\sk}{\operatorname{sk}}
\newcommand{\cosk}{\operatorname{cosk}}
\DeclareMathOperator*{\colim}{colim}
\newif\ifshowsupplement
\showsupplementtrue
% Set \showsupplementfalse to hide all blue material.
\newif\ifshowfineprint
\showfineprinttrue
% Keep \showsupplementtrue and set \showfineprintfalse to display only the darker blue passages.
\ifshowsupplement\else
\showfineprintfalse
\fi
\definecolor{suppblue}{RGB}{25,85,170}
\definecolor{fineblue}{RGB}{110,145,210}
\ifshowsupplement
\newenvironment{supplementary}{\par\smallskip\begingroup\color{suppblue}}{\endgroup\par\smallskip}
\else
\excludecomment{supplementary}
\fi
\ifshowfineprint
\newenvironment{fineprint}{\par\smallskip\begingroup\small\color{fineblue}}{\endgroup\par\smallskip}
\else
\excludecomment{fineprint}
\fi
\title{Levels and Natural Transformations of the Functor \texorpdfstring{$F_A$}{FA}}
\author{Ryuya Hora}
\address{ZEN University, Tokyo, Japan}
\email{ryuya\_hora@zen.ac.jp}
\date{\today}
\subjclass[2020]{18A40, 18B25}
\keywords{commutative monoid, finitary functor, coskeleton, natural transformation}
\begin{document}
\begin{abstract}
Let $A$ be a commutative monoid, written additively. For a finite set $S$, define
\[
F_A(S)=A^S
\]
and let a map $u:S\to T$ act by summation along the fibers:
\[
(F_A(u)(f))(t)=\sum_{u(s)=t} f(s).
\]
This is the restriction to $\FinSet$ of the usual functor on $\Set$ of finitely supported $A$-valued functions. In this note we compute the level of $F_A$ with respect to the cardinality filtration of $\FinSet$, and we classify all natural transformations $F_A\Rightarrow F_B$. The central point is that $F_A$ is $3$-coskeletal. As a consequence, natural transformations into $F_B$ are forced by arities $1$, $2$, and $3$, and are classified by functions
\[
p:A\times A\to B
\]
satisfying
\[
p(0_A,c)=0_B,
\qquad
p(a+b,c)=p(a,b+c)+p(b,a+c).
\]
We also explain how this description recovers the concrete examples in Kori--Watanabe and yields new examples outside the singly generated case.
\end{abstract}
\maketitle
\noindent\textbf{Reading guide.} Black text contains the main narrative: definitions, statements, and proof sketches. Dark blue passages are worth reading at least once: they contain conceptual examples, proof structure, and comparisons with the literature. Light blue passages are the safest to skip on a first pass: they contain longer coordinate computations, routine verifications, and bibliographic side remarks. To display only black text, replace \verb|\showsupplementtrue| by \verb|\showsupplementfalse| in the preamble. To display black text together with the darker blue passages but hide the lighter blue calculations, keep \verb|\showsupplementtrue| and replace \verb|\showfineprinttrue| by \verb|\showfineprintfalse|.
\tableofcontents
\section{Introduction}
Let $A$ be a commutative monoid. On the category of sets, one has the finitary functor
\[
\widetilde{F}_A(X)=\{f:X\to A\mid \supp(f)\text{ is finite}\},
\qquad
\supp(f)=\{x\in X\mid f(x)\neq 0_A\}.
\]
Since $\widetilde{F}_A$ is finitary, it is recovered from its restriction to $\FinSet$; see for example \cite{adamek-milius-moss-urbat2015}. Accordingly, throughout the paper we work with the restricted functor
\[
F_A:\FinSet\to\Set.
\]
There are two themes in this note. The first is the cardinality filtration
\[
\FinSet_{\le n}\hookrightarrow \FinSet,
\]
and the associated notions of $n$-skeletal and $n$-coskeletal objects in $\Func{\FinSet}{\Set}$. The second is the explicit description of natural transformations
\[
F_A\Rightarrow F_B.
\]
The link between the two is that $F_B$ turns out to be $3$-coskeletal, so every natural transformation into $F_B$ is controlled by what happens on sets of size at most three.
This viewpoint is particularly convenient when compared with the recent preprint of Kori--Watanabe \cite{kori-watanabe2025}. Their Definition~5 introduces the same family of functors $F_A$, Example~6 identifies the multiset and finite powerset functors inside this family, Proposition~2 shows that any natural transformation $F_A\Rightarrow F_B$ is determined by its component at the $2$-point set, Theorem~1 in \S4.1 computes several singly generated cases explicitly, and Examples~7--8 work out the multiset and finite-powerset cases in detail. We shall recover those examples from a single formula for $p(a,c)$ and then use the same formula to produce examples beyond the singly generated setting.
\section{\texorpdfstring{The functor $F_A$}{The functor FA}}
\subsection{Definition and the filtration}
\begin{definition}
Let $A$ be a commutative monoid.
Define a functor
\[
F_A:\FinSet\to\Set
\]
by
\[
F_A(S)=A^S
\]
on objects, and for a map $u:S\to T$ define
\[
(F_A(u)(f))(t)=\sum_{u(s)=t}f(s)
\]
for $f\in A^S$ and $t\in T$.
\end{definition}
\begin{notation}
For $n\ge 0$, let
\[
j_n:\FinSet_{\le n}\hookrightarrow \FinSet
\]
be the full inclusion.
For a functor $H:\FinSet\to\Set$, define
\[
\sk_n H:=\Lan_{j_n}(j_n^*H),
\qquad
\cosk_n H:=\Ran_{j_n}(j_n^*H).
\]
Pointwise, one has
\[
(\sk_n H)(X)\cong \colim_{(u:S\to X)\in (j_n\downarrow X)} H(S),
\]
and
\[
(\cosk_n H)(X)\cong \lim_{(u:X\to S)\in (X\downarrow j_n)} H(S).
\]
\end{notation}
\begin{supplementary}
\begin{remark}
If $X$ is a finite set, an element of $(\cosk_3 F_A)(X)$ is concretely a compatible family
\[
(\lambda_u)_{u:X\to S,\ \abs{S}\le 3},
\qquad
\lambda_u\in A^S,
\]
compatible under postcomposition. Intuitively, this means that for every way of cutting $X$ into at most three pieces, we are given the sums on those pieces, and these sums agree whenever one partition is obtained from another by merging pieces.
\end{remark}
\end{supplementary}
\subsection{\texorpdfstring{The level of $F_A$}{The level of FA}}
We now spell out the previous remark in concrete pictures.
\begin{supplementary}
\begin{example}[Three basic incarnations]\label{ex:three-basic-incarnations}
The same formula produces several familiar functors.
\begin{enumerate}
\item If $A=(\N,+,0)$, then $F_A(X)$ is the set of finite multisets on $X$.
\item If $A=(\B,\vee,0)$, then $F_A(X)$ is the set of finite subsets of $X$.
\item If $A=(\R_{\ge 0},+,0)$, then $F_A(X)$ is the set of finitely supported nonnegative weights on $X$.
\end{enumerate}
In each case, a map $u:X\to Y$ pushes a finitely supported function forward by summing along the fibers.
\end{example}
\begin{example}\label{ex:partition-2}
Let $X=\{1,2,3,4\}$ and let $T=\{1,4\}$.
The map
\[
\chi_T:X\to 2
\]
remembers only the decomposition of $X$ into the two parts $T$ and $X\setminus T$. If $f\in F_A(X)=A^X$ corresponds to values $a_1,a_2,a_3,a_4\in A$, then
\[
F_A(\chi_T)(f)=(a_1+a_4,\ a_2+a_3).
\]
Thus a $2$-partition only records subset sums.
\end{example}
\begin{figure}[ht]
\centering
\begin{tikzpicture}[x=1cm,y=1cm, every node/.style={font=\small}]
\node[draw, rounded corners, fill=blue!7, minimum width=4.2cm, minimum height=1cm] (T) at (0,0) {$T$};
\node[draw, rounded corners, fill=green!7, minimum width=4.8cm, minimum height=1cm] (C) at (5.4,0) {$X\setminus T$};
\foreach \x in {-1.55,-1.05,1.05,1.55} {\fill (\x,0) circle (1.6pt);}
\foreach \x in {3.65,4.15,6.65,7.15} {\fill (\x,0) circle (1.6pt);}
\draw[->,thick] (0,-0.72) -- (0,-2.02);
\draw[->,thick] (5.4,-0.72) -- (5.4,-2.02);
\node at (0,-2.36) {$1$};
\node at (5.4,-2.36) {$2$};
\node at (2.7,-2.36) {$\chi_T:X\to 2$};
\end{tikzpicture}
\caption{A map $X\to 2$ remembers a subset and its complement.}
\end{figure}
\begin{example}\label{ex:partition-3}
Fix $x\in T\subseteq X$.
The map
\[
u:X\to 3
\]
with fibers
\[
\{x\},\qquad T\setminus\{x\},\qquad X\setminus T
\]
refines the previous $2$-partition by separating one point from the rest of $T$.
If $f\in A^X$ corresponds to $(a_y)_{y\in X}$, then
\[
F_A(u)(f)=\left(a_x,\ \sum_{y\in T\setminus\{x\}} a_y,\ \sum_{y\in X\setminus T} a_y\right).
\]
This is exactly the configuration used in the proof of $3$-coskeletality.
\end{example}
\begin{figure}[ht]
\centering
\begin{tikzpicture}[x=1cm,y=1cm, every node/.style={font=\small}]
\node[draw, rounded corners, fill=red!8, minimum width=1.5cm, minimum height=1cm] (x) at (0,0) {$\{x\}$};
\node[draw, rounded corners, fill=blue!8, minimum width=4.0cm, minimum height=1cm] (tx) at (3.9,0) {$T\setminus\{x\}$};
\node[draw, rounded corners, fill=green!8, minimum width=4.8cm, minimum height=1cm] (c) at (9.0,0) {$X\setminus T$};
\fill (-0.25,0) circle (1.6pt);
\foreach \x in {2.25,2.75,5.05,5.55} {\fill (\x,0) circle (1.6pt);}
\foreach \x in {7.0,7.5,10.5,11.0} {\fill (\x,0) circle (1.6pt);}
\draw[->,thick] (0,-0.72) -- (0,-2.02);
\draw[->,thick] (3.9,-0.72) -- (3.9,-2.02);
\draw[->,thick] (9.0,-0.72) -- (9.0,-2.02);
\node at (0,-2.36) {$1$};
\node at (3.9,-2.36) {$2$};
\node at (9.0,-2.36) {$3$};
\node at (4.5,-2.36) {$u:X\to 3$};
\end{tikzpicture}
\caption{A $3$-partition isolates one point and forces additivity on subsets.}
\end{figure}
\begin{figure}[ht]
\centering
\[
\begin{tikzcd}[column sep=5.8em,row sep=3.0em]
& X \arrow[dl, "\chi_{\{x\}}"'] \arrow[d, "u"] \arrow[dr, "\chi_T"] & \\
2 & 3 \arrow[l, "r_1"'] \arrow[r, "m"] & 2
\end{tikzcd}
\]
\caption{A single $3$-partition simultaneously controls the singleton value $\mu(\{x\})$ and the subset value $\mu(T)$.}
\end{figure}
\begin{example}[A fully worked $4$-point family]\label{ex:worked-four-point}
Let $X=\{1,2,3,4\}$ and choose values
\[
a_1,a_2,a_3,a_4\in A.
\]
If a compatible family in $(\cosk_3F_A)(X)$ comes from these singleton values, then its values on the following maps are forced:
\[
\lambda_{\chi_{\{1,4\}}}=(a_1+a_4,\ a_2+a_3),
\]
\[
\lambda_{\chi_{\{1,2,4\}}}=(a_1+a_2+a_4,\ a_3),
\]
and for the map $u:X\to 3$ with fibers $\{1,4\},\{2\},\{3\}$ one must have
\[
\lambda_u=(a_1+a_4,\ a_2,\ a_3).
\]
Thus the compatible family is not extra data: it is exactly the family of all finite fiber-sums determined by $(a_x)_{x\in X}$.
\end{example}
\begin{figure}[ht]
\centering
\begin{tikzpicture}[
node distance=8mm and 7mm,
box/.style={draw, rounded corners, inner sep=4pt, minimum height=7mm, font=\small},
>=Latex
]
\node[box, fill=red!8] (s1) {$\{1\}:a_1$};
\node[box, fill=blue!8, right=of s1] (s2) {$\{2\}:a_2$};
\node[box, fill=green!8, right=of s2] (s3) {$\{3\}:a_3$};
\node[box, fill=orange!8, right=of s3] (s4) {$\{4\}:a_4$};
\node[box, fill=purple!8, below=18mm of $(s1)!0.5!(s4)$, minimum width=34mm] (t14) {$\{1,4\}:a_1+a_4$};
\node[box, fill=blue!5, right=12mm of t14, minimum width=20mm] (t2) {$\{2\}:a_2$};
\node[box, fill=green!5, right=12mm of t2, minimum width=20mm] (t3) {$\{3\}:a_3$};
\node[box, fill=cyan!8, below=18mm of $(t14)!0.5!(t3)$, minimum width=42mm] (t124) {$\{1,2,4\}:a_1+a_2+a_4$};
\node[box, fill=green!5, right=16mm of t124, minimum width=20mm] (t3b) {$\{3\}:a_3$};
\node[box, fill=gray!12, below=18mm of $(t124)!0.5!(t3b)$, minimum width=60mm] (all) {$X:a_1+a_2+a_3+a_4$};
\draw[->] (s1) -- (t14);
\draw[->] (s4) -- (t14);
\draw[->] (s2) -- (t2);
\draw[->] (s3) -- (t3);
\draw[->] (t14) -- (t124);
\draw[->] (t2) -- (t124);
\draw[->] (t3) -- (t3b);
\draw[->] (t124) -- (all);
\draw[->] (t3b) -- (all);
\end{tikzpicture}
\caption{A compatible family is obtained by repeatedly merging pieces and summing their labels.}
\end{figure}
\end{supplementary}
\begin{proposition}\label{prop:3cosk}
For every commutative monoid $A$, the functor $F_A$ is $3$-coskeletal.
\end{proposition}
\begin{proof}
The proof has two conceptual steps.
First, a compatible family over all maps $X\to S$ with $\abs{S}\le 3$ determines singleton labels
\[
a_x\in A
\qquad (x\in X),
\]
and a $3$-partition
\[
\{x\}\sqcup (T\setminus\{x\})\sqcup (X\setminus T)
\]
forces every subset value $\mu(T)$ to be the sum of the corresponding singleton labels.
Second, once these subset sums are known, the value on every map $u:X\to S$ with $\abs{S}\le 3$ is forced, so the family is exactly the image of the function $x\mapsto a_x$.
\begin{supplementary}
Let $X$ be a finite set and let $(\lambda_u)$ be a compatible family defining an element of $(\cosk_3F_A)(X)$.
For each subset $T\subseteq X$, let
\[
\chi_T:X\to 2
\]
be the characteristic map and let $\mu(T)$ be the first coordinate of $\lambda_{\chi_T}$.
For each $x\in X$, set
\[
a_x:=\mu(\{x\}).
\]
The key point is that a $3$-partition
\[
\{x\}\sqcup (T\setminus\{x\})\sqcup (X\setminus T)
\]
forces the recursion
\[
\mu(T)=a_x+\mu(T\setminus\{x\}).
\]
Hence one obtains
\[
\mu(T)=\sum_{x\in T} a_x
\]
for every subset $T\subseteq X$.
Now define $f\in A^X$ by $f(x)=a_x$.
If $u:X\to 3$ has fibers $T_1,T_2,T_3$, then compatibility with the three maps $3\to 2$ isolating one fiber at a time forces
\[
\lambda_u=
\left(
\sum_{x\in T_1}a_x,
\sum_{x\in T_2}a_x,
\sum_{x\in T_3}a_x
\right)=F_A(u)(f).
\]
The same argument works for maps $X\to 2$ and $X\to 1$, so the whole compatible family is induced by $f$.
Singleton characteristic maps recover each $a_x$, so the induced $f$ is unique.
\end{supplementary}
\begin{fineprint}
If $\abs{X}\le 3$, then the identity $X\to X$ is an initial object of $(X\downarrow j_3)$, so the canonical map
\[
F_A(X)\to (\cosk_3 F_A)(X)
\]
is automatically a bijection.
Thus we may assume $\abs{X}>3$.
Let $(\lambda_u)$ be an element of $(\cosk_3 F_A)(X)$.
Thus for each map
\[
u:X\to S,
\qquad \abs{S}\le 3,
\]
we are given an element $\lambda_u\in A^S$, and these are compatible under postcomposition.
For each subset $T\subseteq X$, let
\[
\chi_T:X\to 2
\]
be the characteristic map with $\chi_T^{-1}(1)=T$.
Write
\[
\mu(T)=\text{the first coordinate of }\lambda_{\chi_T}\in A^2.
\]
For each $x\in X$, define
\[
a_x:=\mu(\{x\}).
\]
We claim that for every subset $T\subseteq X$,
\[
\mu(T)=\sum_{x\in T} a_x.
\]
We prove this by induction on $\abs{T}$.
If $T=\varnothing$, then $\chi_\varnothing$ factors as
\[
X\to 1 \xrightarrow{i_2} 2,
\]
where $i_2$ lands in the second point. In other words,
\[
\begin{tikzcd}[column sep=5.2em,row sep=3.0em]
X \arrow[r] \arrow[dr, "\chi_\varnothing"'] & 1 \arrow[d, "i_2"] \\
& 2
\end{tikzcd}
\]
Hence
\[
\lambda_{\chi_\varnothing}=F_A(i_2)(\lambda_{X\to 1}),
\]
so its first coordinate is $0_A$. Therefore $\mu(\varnothing)=0_A$.
If $\abs{T}=1$, this is the definition of $a_x$.
Assume now that $\abs{T}\ge 2$, and choose $x\in T$.
Let
\[
u:X\to 3
\]
be the map whose fibers are
\[
\{x\},\qquad T\setminus\{x\},\qquad X\setminus T.
\]
Write
\[
\lambda_u=(b_1,b_2,b_3)\in A^3.
\]
Let $r_1,r_2,m:3\to 2$ be defined by
\[
r_1^{-1}(1)=\{1\},
\qquad
r_2^{-1}(1)=\{2\},
\qquad
m^{-1}(1)=\{1,2\}.
\]
Then
\[
r_1\circ u=\chi_{\{x\}},
\qquad
r_2\circ u=\chi_{T\setminus\{x\}},
\qquad
m\circ u=\chi_T.
\]
By compatibility, the three triangles
\[
\begin{tikzcd}[column sep=4.6em,row sep=3.0em]
& X \arrow[dl, "\chi_{\{x\}}"'] \arrow[d, "u"] \arrow[dr, "\chi_T"] & \\
2 & 3 \arrow[l, "r_1"'] \arrow[r, "m"] & 2
\end{tikzcd}
\qquad
\begin{tikzcd}[column sep=4.6em,row sep=3.0em]
& X \arrow[dl, "\chi_{T\setminus\{x\}}"'] \arrow[d, "u"] \arrow[dr, "\chi_T"] & \\
2 & 3 \arrow[l, "r_2"'] \arrow[r, "m"] & 2
\end{tikzcd}
\]
yield
\[
F_A(r_1)(b_1,b_2,b_3)=\lambda_{\chi_{\{x\}}},
\qquad
F_A(r_2)(b_1,b_2,b_3)=\lambda_{\chi_{T\setminus\{x\}}},
\qquad
F_A(m)(b_1,b_2,b_3)=\lambda_{\chi_T}.
\]
Taking first coordinates gives
\[
b_1=\mu(\{x\})=a_x,
\qquad
b_2=\mu(T\setminus\{x\}),
\qquad
b_1+b_2=\mu(T).
\]
Therefore
\[
\mu(T)=a_x+\mu(T\setminus\{x\}).
\]
By the induction hypothesis,
\[
\mu(T)=a_x+\sum_{y\in T\setminus\{x\}}a_y=
\sum_{y\in T}a_y.
\]
This proves the claim.
Now let $f\in A^X$ be the function defined by
\[
f(x)=a_x.
\]
We show that the compatible family $(\lambda_u)$ is exactly the image of $f$ under the canonical map
\[
F_A(X)\to (\cosk_3F_A)(X).
\]
If $u:X\to 3$ has fibers
\[
T_1=u^{-1}(1),
\qquad
T_2=u^{-1}(2),
\qquad
T_3=u^{-1}(3),
\]
and if
\[
\lambda_u=(c_1,c_2,c_3),
\]
then for each $i=1,2,3$ let $r_i:3\to 2$ be the map sending $i$ to $1$ and the other two points to $2$.
Since $r_i\circ u=\chi_{T_i}$, each $i$ fits into a triangle
\[
\begin{tikzcd}[column sep=5.0em,row sep=3.0em]
& X \arrow[dl, "\chi_{T_i}"'] \arrow[d, "u"] \\
2 & 3 \arrow[l, "r_i"']
\end{tikzcd}
\]
and compatibility gives
\[
F_A(r_i)(c_1,c_2,c_3)=\lambda_{\chi_{T_i}}.
\]
Taking first coordinates yields
\[
c_i=\mu(T_i)=\sum_{x\in T_i} a_x.
\]
Hence
\[
\lambda_u=
\left(
\sum_{x\in T_1}a_x,
\sum_{x\in T_2}a_x,
\sum_{x\in T_3}a_x
\right)
=F_A(u)(f).
\]
The same argument works for maps $X\to 2$ and for the unique map $X\to 1$.
Therefore $(\lambda_u)$ is induced by $f$.
Uniqueness is immediate because the characteristic maps of singletons recover each $a_x$.
Thus the canonical map
\[
F_A(X)\to (\cosk_3F_A)(X)
\]
is a bijection for every finite set $X$.
\end{fineprint}
\end{proof}
\begin{corollary}\label{cor:restriction}
Let $B$ be a commutative monoid and let $H:\FinSet\to\Set$ be any functor.
Then restriction along $j_3$ induces a bijection
\[
\Nat(H,F_B)\cong \Nat(j_3^*H,j_3^*F_B).
\]
In particular, every natural transformation into $F_B$ is determined by its components on sets of size at most $3$.
\end{corollary}
\begin{proof}
By \cref{prop:3cosk}, the functor $F_B$ is $3$-coskeletal, so
\[
F_B\cong \cosk_3(j_3^*F_B).
\]
Since $j_3^*$ has right adjoint $\cosk_3$, we obtain
\[
\Nat(H,F_B)
\cong
\Nat(H,\cosk_3(j_3^*F_B))
\cong
\Nat(j_3^*H,j_3^*F_B).
\qedhere
\]
\end{proof}
\begin{supplementary}
\begin{remark}\label{rem:lower-levels}
If $A$ is nontrivial, then $F_A$ is not $n$-skeletal for any finite $n$, and it is not $2$-coskeletal. These two statements are useful for orientation, but they are not needed for the classification of natural transformations. We therefore move their proofs to \Cref{sec:appendix-lower}.
\end{remark}
\end{supplementary}
\subsection{A finite-codensity viewpoint}
This subsection is supplementary. It records a codensity-style way of reading the construction.
\begin{supplementary}
There is a useful way to read the construction of the coskeleton itself.
The truncation functor
\[
j_3^*:\Func{\FinSet}{\Set}\to \Func{\FinSet_{\le 3}}{\Set}
\]
has right adjoint $\cosk_3=\Ran_{j_3}j_3^*$, so $\cosk_3$ is the right-Kan-extension monad generated by restricting to arities $\le 3$.
In this sense, the proof above is a finite-arity analogue of the codensity philosophy: instead of completing sets by all finite tests, we complete finitary functors by all tests of arity at most $3$.
Compare this with the theorem of Kennison--Gildenhuys, emphasized by Leinster, that the codensity monad of the inclusion
\[
J:\FinSet\hookrightarrow \Set
\]
is the ultrafilter monad \cite{leinster2013}.
\begin{figure}[ht]
\centering
\[
\begin{tikzcd}[column sep=6.4em,row sep=3.2em]
\Func{\FinSet}{\Set}
\arrow[r, shift left=1.1ex, "j_3^*"]
\arrow[r, phantom, "\dashv"]
& \Func{\FinSet_{\le 3}}{\Set}
\arrow[l, shift left=1.1ex, "\cosk_3=\Ran_{j_3}j_3^*"']
\end{tikzcd}
\]
\caption{The $3$-coskeleton as a right Kan extension from small arities.}
\end{figure}
\begin{remark}
The analogy with the ultrafilter monad should not be overstated: Leinster's theorem concerns the codensity monad $\Ran_JJ$ on $\Set$, whereas here we are working with the induced monad $\Ran_{j_3}j_3^*$ on the object-classifier topos $\Func{\FinSet}{\Set}$. Still, both are instances of the same general principle: sufficiently many finite tests can force global structure.
\end{remark}
\end{supplementary}
\section{Natural transformations}
\subsection{An additive identity}
\begin{lemma}\label{lem:main-identity}
Let $A$ and $B$ be commutative monoids, and let
\[
p:A\times A\to B
\]
be a function satisfying
\[
p(0_A,c)=0_B,
\qquad
p(a+b,c)=p(a,b+c)+p(b,a+c)
\]
for all $a,b,c\in A$.
Then for every finite family $a_1,\dots,a_n\in A$ and every $c\in A$,
\[
p(a_1+\cdots+a_n,c)
=
\sum_{i=1}^n p\!\left(a_i,\ c+\sum_{j\neq i}a_j\right).
\]
\end{lemma}
\begin{proof}
We argue by induction on $n$.
If $n=0$, the statement is $p(0_A,c)=0_B$.
Assume the statement holds for $n$.
Then
\[
p(a_1+\cdots+a_n+a_{n+1},c)
=
p(a_1+\cdots+a_n,c+a_{n+1})+p(a_{n+1},c+a_1+\cdots+a_n).
\]
Applying the induction hypothesis to the first term gives the desired formula for $n+1$.
\end{proof}
\subsection{Classification theorem}
\begin{theorem}\label{thm:classification}
Let $A$ and $B$ be commutative monoids.
Then natural transformations
\[
\eta:F_A\Rightarrow F_B
\]
are in bijection with functions
\[
p:A\times A\to B
\]
satisfying
\[
p(0_A,c)=0_B,
\qquad
p(a+b,c)=p(a,b+c)+p(b,a+c)
\]
for all $a,b,c\in A$.
The correspondence is given as follows.
\begin{enumerate}
\item Given a natural transformation $\eta$, define
\[
p_\eta(a,b)=\bigl(\eta_2(a,b)\bigr)(1).
\]
\item Given a function $p$ satisfying the two identities above, define
\[
\eta^p_X:A^X\to B^X
\]
by
\[
(\eta^p_X(f))(x)=p\!\left(f(x),\sum_{y\neq x}f(y)\right).
\]
\end{enumerate}
These two constructions are inverse to each other.
\end{theorem}
\begin{proof}
The proof follows the same low-arity pattern as the preceding section.
The component on the $2$-point set produces the binary datum $p(a,b)$.
The component on the $3$-point set forces exactly the cocycle identity
\[
p(a+b,c)=p(a,b+c)+p(b,a+c).
\]
Conversely, this cocycle identity is precisely what is needed to prove naturality via \cref{lem:main-identity}.
\begin{supplementary}
The low-arity part can be summarized explicitly.
If
\[
p(a,b):=\bigl(\eta_2(a,b)\bigr)(1),
\]
then naturality with respect to the transposition of $2$ gives
\[
\eta_2(a,b)=\bigl(p(a,b),p(b,a)\bigr).
\]
\begin{figure}[ht]
\centering
\[
\begin{tikzcd}[column sep=5.4em,row sep=3.0em]
A^2 \arrow[r, "\eta_2"] \arrow[d, "F_A(\tau)"'] & B^2 \arrow[d, "F_B(\tau)"] \\
A^2 \arrow[r, "\eta_2"'] & B^2
\end{tikzcd}
\]
\caption{The transposition of $2$ exchanges the two coordinates, hence forces symmetry of the two outputs of $\eta_2$.}
\end{figure}
Next, if
\[
\eta_3(a,b,c)=(u,v,w),
\]
then the three maps $3\to 2$ isolating one point at a time force
\[
\eta_3(a,b,c)=\bigl(p(a,b+c),p(b,a+c),p(c,a+b)\bigr).
\]
\begin{figure}[ht]
\centering
\[
\begin{tikzcd}[column sep=5.6em,row sep=3.0em]
A^3 \arrow[r, "\eta_3"] \arrow[d, "F_A(r_i)"'] & B^3 \arrow[d, "F_B(r_i)"] \\
A^2 \arrow[r, "\eta_2"'] & B^2
\end{tikzcd}
\]
\caption{For $i=1,2,3$, the map $r_i:3\to 2$ isolates one fiber of a $3$-partition. These three naturality squares determine the three coordinates of $\eta_3(a,b,c)$.}
\end{figure}
Finally, composing with the fold $m:3\to 2$ that merges the first two points yields the cocycle identity
\[
p(a+b,c)=p(a,b+c)+p(b,a+c).
\]
\begin{figure}[ht]
\centering
\[
\begin{tikzcd}[column sep=5.6em,row sep=3.0em]
A^3 \arrow[r, "\eta_3"] \arrow[d, "F_A(m)"'] & B^3 \arrow[d, "F_B(m)"] \\
A^2 \arrow[r, "\eta_2"'] & B^2
\end{tikzcd}
\]
\caption{Merging the first two points of $3$ into one point of $2$ produces exactly the relation on $p(a,c)$.}
\end{figure}
Conversely, if a function $p$ satisfies this identity, then naturality of the formula
\[
(\eta^p_X(f))(x)=p\!\left(f(x),\sum_{y\neq x}f(y)\right)
\]
is reduced by \cref{lem:main-identity} to summing the contributions from a single fiber $u^{-1}(y)$.
\end{supplementary}
\begin{fineprint}
Let $\eta:F_A\Rightarrow F_B$ be a natural transformation, and define
\[
p(a,b):=p_\eta(a,b)=\bigl(\eta_2(a,b)\bigr)(1).
\]
\para{Step 1: the component on $2$}
Let $\tau:2\to 2$ be the transposition.
Naturality with respect to $\tau$ gives the commutative square
\[
\begin{tikzcd}[column sep=5.4em,row sep=3.0em]
A^2 \arrow[r, "\eta_2"] \arrow[d, "F_A(\tau)"'] & B^2 \arrow[d, "F_B(\tau)"] \\
A^2 \arrow[r, "\eta_2"'] & B^2
\end{tikzcd}
\]
and hence
\[
\eta_2(a,b)=\bigl(p(a,b),p(b,a)\bigr).
\]
Now let $i_2:1\to 2$ be the injection landing in the second point.
Since
\[
F_A(i_2)(c)=(0_A,c),
\qquad
F_B(i_2)(d)=(0_B,d),
\]
naturality gives the square
\[
\begin{tikzcd}[column sep=5.4em,row sep=3.0em]
A \arrow[r, "\eta_1"] \arrow[d, "F_A(i_2)"'] & B \arrow[d, "F_B(i_2)"] \\
A^2 \arrow[r, "\eta_2"'] & B^2
\end{tikzcd}
\]
and therefore
\[
\eta_2(0_A,c)=F_B(i_2)(\eta_1(c))=(0_B,\eta_1(c)).
\]
Comparing the first coordinates, we obtain
\[
p(0_A,c)=0_B.
\]
Comparing the second coordinates, we obtain
\[
\eta_1(c)=p(c,0_A).
\]
\para{Step 2: the component on $3$}
Write
\[
\eta_3(a,b,c)=(u,v,w)\in B^3.
\]
Let $r_1,r_2,r_3:3\to 2$ be the maps isolating the first, second, and third points:
\[
r_1^{-1}(1)=\{1\},
\qquad
r_2^{-1}(1)=\{2\},
\qquad
r_3^{-1}(1)=\{3\}.
\]
Then
\[
F_A(r_1)(a,b,c)=(a,b+c),
\qquad
F_A(r_2)(a,b,c)=(b,a+c),
\qquad
F_A(r_3)(a,b,c)=(c,a+b).
\]
For each $i=1,2,3$ there is a naturality square
\[
\begin{tikzcd}[column sep=5.2em,row sep=3.0em]
A^3 \arrow[r, "\eta_3"] \arrow[d, "F_A(r_i)"'] & B^3 \arrow[d, "F_B(r_i)"] \\
A^2 \arrow[r, "\eta_2"'] & B^2
\end{tikzcd}
\]
so in particular
\[
F_B(r_1)(u,v,w)=\eta_2(a,b+c),
\qquad
F_B(r_2)(u,v,w)=\eta_2(b,a+c),
\qquad
F_B(r_3)(u,v,w)=\eta_2(c,a+b).
\]
Taking first coordinates gives
\[
u=p(a,b+c),
\qquad
v=p(b,a+c),
\qquad
w=p(c,a+b).
\]
Therefore
\[
\eta_3(a,b,c)=\bigl(p(a,b+c),p(b,a+c),p(c,a+b)\bigr).
\]
\para{Step 3: the relation on $p$}
Let $m:3\to 2$ be the map with fibers
\[
m^{-1}(1)=\{1,2\},
\qquad
m^{-1}(2)=\{3\}.
\]
Then
\[
F_A(m)(a,b,c)=(a+b,c),
\qquad
F_B(m)(u,v,w)=(u+v,w).
\]
Naturality gives the square
\[
\begin{tikzcd}[column sep=5.2em,row sep=3.0em]
A^3 \arrow[r, "\eta_3"] \arrow[d, "F_A(m)"'] & B^3 \arrow[d, "F_B(m)"] \\
A^2 \arrow[r, "\eta_2"'] & B^2
\end{tikzcd}
\]
and therefore
\[
\eta_2(a+b,c)=F_B(m)(\eta_3(a,b,c)).
\]
Comparing the first coordinates yields
\[
p(a+b,c)=p(a,b+c)+p(b,a+c).
\]
Thus every natural transformation yields a function $p$ satisfying the required identities.
\para{Step 4: construction from $p$}
Conversely, suppose that
\[
p:A\times A\to B
\]
satisfies
\[
p(0_A,c)=0_B,
\qquad
p(a+b,c)=p(a,b+c)+p(b,a+c).
\]
Define
\[
\eta^p_X(f)(x):=p\!\left(f(x),\sum_{y\neq x}f(y)\right).
\]
We prove that $\eta^p$ is natural.
For a map $u:X\to Y$ the target statement is the commutativity of
\[
\begin{tikzcd}[column sep=5.4em,row sep=3.0em]
A^X \arrow[r, "\eta_X^p"] \arrow[d, "F_A(u)"'] & B^X \arrow[d, "F_B(u)"] \\
A^Y \arrow[r, "\eta_Y^p"'] & B^Y
\end{tikzcd}
\]
Let $f\in A^X$, and let $y\in Y$.
Write
\[
S=u^{-1}(y),
\qquad
c=\sum_{z\notin S} f(z).
\]
Then
\[
(F_B(u)(\eta^p_X(f)))(y)
=
\sum_{x\in S} p\!\left(f(x),\ c+\sum_{\substack{x'\in S\\ x'\neq x}} f(x')\right).
\]
By \cref{lem:main-identity}, this is equal to
\[
p\!\left(\sum_{x\in S}f(x),c\right).
\]
On the other hand,
\[
(F_A(u)(f))(y)=\sum_{x\in S}f(x),
\qquad
\sum_{y'\neq y}(F_A(u)(f))(y')=\sum_{z\notin S}f(z)=c.
\]
Hence
\[
(F_B(u)(\eta^p_X(f)))(y)=(\eta^p_Y(F_A(u)(f)))(y).
\]
So $\eta^p$ is natural.
\para{Step 5: the two constructions are inverse}
If we start with $p$, then
\[
\eta^p_2(a,b)=\bigl(p(a,b),p(b,a)\bigr),
\]
so $p_{\eta^p}(a,b)=p(a,b)$.
Conversely, if we start with $\eta$, then for any finite $X$, any $f\in A^X$, and any $x\in X$, the characteristic map
\[
\chi_{\{x\}}:X\to 2
\]
gives
\[
F_A(\chi_{\{x\}})(f)=\left(f(x),\sum_{y\neq x}f(y)\right).
\]
Naturality is the commutative square
\[
\begin{tikzcd}[column sep=5.4em,row sep=3.0em]
A^X \arrow[r, "\eta_X"] \arrow[d, "F_A(\chi_{\{x\}})"'] & B^X \arrow[d, "F_B(\chi_{\{x\}})"] \\
A^2 \arrow[r, "\eta_2"'] & B^2
\end{tikzcd}
\]
hence
\[
F_B(\chi_{\{x\}})(\eta_X(f))=
\eta_2\!\left(f(x),\sum_{y\neq x}f(y)\right).
\]
Taking the first coordinate, we obtain
\[
(\eta_X(f))(x)=p_\eta\!\left(f(x),\sum_{y\neq x}f(y)\right)=
(\eta^{p_\eta}_X(f))(x).
\]
Hence $\eta=\eta^{p_\eta}$.
\end{fineprint}
\end{proof}
\begin{supplementary}
\begin{remark}
The theorem shows that the $2$-point set contributes the binary datum $p(a,c)$, while the $3$-point set contributes exactly the cocycle identity
\[
p(a+b,c)=p(a,b+c)+p(b,a+c).
\]
By \cref{cor:restriction}, nothing new appears in higher arity.
\end{remark}
\end{supplementary}
\subsection{Cocycles, fibres of addition, and a coKleisli category}
This subsection is supplementary. It explains why the relation on $p(a,c)$ deserves to be called a cocycle identity and packages the resulting morphisms into an explicit coKleisli category.
\begin{supplementary}
The second variable $c$ should be read as \emph{context} or \emph{complementary summand}. The more geometric parameter is the total
\[
t=a+c.
\]
Thus $p(a,c)$ assigns a value to a decomposition of a total element $t$ into two pieces. The identity
\[
p(a+b,c)=p(a,b+c)+p(b,a+c)
\]
says that if one refines the first piece $a+b$ into two summands $a$ and $b$, then the value on the coarse decomposition is the sum of the two values on the refined decompositions.
\begin{figure}[ht]
\centering
\begin{tikzpicture}[
>=Latex,
every node/.style={font=\small},
box/.style={draw, rounded corners, minimum height=8mm, inner sep=5pt}
]
\node[box, fill=orange!8] (top) at (0,1.6) {$(a+b,c)$};
\node[box, fill=blue!8] (left) at (-2.4,0) {$(a,b+c)$};
\node[box, fill=green!8] (right) at (2.4,0) {$(b,a+c)$};
\draw[->, thick] (top.south west) -- node[left, xshift=-1mm] {refine} (left.north);
\draw[->, thick] (top.south east) -- node[right, xshift=1mm] {refine} (right.north);
\node at (0,0.85) {$\text{same total }a+b+c$};
\end{tikzpicture}
\caption{One total element $a+b+c$ can be decomposed either coarsely as $(a+b,c)$ or finely as $(a,b+c)$ and $(b,a+c)$. The cocycle identity says that the value on the coarse decomposition is the sum of the values on the refinement.}
\end{figure}
So the relation is best viewed as a \emph{fibrewise additivity law} over the addition map
\[
+:A\times A\to A.
\]
On the fibre over a total element $t$, the cocycle records how values behave under refinement of a decomposition of $t$.
\begin{remark}[Why \dq{cocycle}?]\label{rem:group-cocycle}
If $A$ and $B$ are abelian groups and $p$ extends to the group completions, then one can reparameterize by the total:
\[
z_t(a):=p(a,t-a).
\]
The cocycle identity becomes
\[
z_t(a+b)=z_t(a)+z_t(b).
\]
So for each fixed total $t$, the function $z_t:A\to B$ is a normalized $1$-cocycle for the trivial action, equivalently a group homomorphism. In this sense, the identity on $p(a,c)$ really is a family of ordinary cocycle equations, one on each fibre of the addition map.
\end{remark}
\begin{definition}
For a commutative monoid $A$, let $Q(A)$ be the commutative monoid presented by generators
\[
\ctx{a}{c}
\qquad
(a,c\in A)
\]
subject to the relations
\[
\ctx{0_A}{c}=0,
\qquad
\ctx{a+b}{c}=\ctx{a}{b+c}+\ctx{b}{a+c}.
\]
For a homomorphism $f:A\to A'$, define
\[
Q(f)\bigl(\ctx{a}{c}\bigr):=\ctx{f(a)}{f(c)}.
\]
\end{definition}
\begin{proposition}\label{prop:Q-rep}
For commutative monoids $A$ and $B$, there is a natural bijection
\[
\CMon(Q(A),B)\cong \Nat(F_A,F_B).
\]
Equivalently, a homomorphism $Q(A)\to B$ is the same thing as a function
\[
p:A\times A\to B
\]
satisfying
\[
p(0_A,c)=0_B,
\qquad
p(a+b,c)=p(a,b+c)+p(b,a+c).
\]
\end{proposition}
\begin{proof}
A homomorphism $Q(A)\to B$ is uniquely determined by the images of the generators $\ctx{a}{c}$, and the defining relations of $Q(A)$ are exactly the two identities required in \cref{thm:classification}. So the universal property of the presented monoid $Q(A)$ and \cref{thm:classification} give the stated bijection.
\end{proof}
\begin{proposition}\label{prop:Q-comonad}
The endofunctor $Q$ on $\CMon$ carries a natural comonad structure with counit
\[
\varepsilon_A:Q(A)\to A,
\qquad
\varepsilon_A\bigl(\ctx{a}{c}\bigr)=a,
\]
and comultiplication
\[
\delta_A:Q(A)\to Q(Q(A)),
\qquad
\delta_A\bigl(\ctx{a}{c}\bigr)=\ctx{\ctx{a}{c}}{\ctx{c}{a}}.
\]
Hence the category whose objects are commutative monoids and whose morphisms
\[
A\rightsquigarrow B
\]
are natural transformations
\[
F_A\Rightarrow F_B
\]
is the coKleisli category of the comonad $Q$.
\end{proposition}
\begin{proof}
The formulas for $\varepsilon_A$ and $\delta_A$ preserve the defining relations of $Q(A)$, so they define homomorphisms.
The counit identities are immediate on generators:
\[
Q(\varepsilon_A)\delta_A\bigl(\ctx{a}{c}\bigr)=\ctx{a}{c},
\qquad
\varepsilon_{Q(A)}\delta_A\bigl(\ctx{a}{c}\bigr)=\ctx{a}{c}.
\]
Likewise, coassociativity is immediate on generators:
\[
Q(\delta_A)\delta_A\bigl(\ctx{a}{c}\bigr)
=
\ctx{\ctx{\ctx{a}{c}}{\ctx{c}{a}}}{\ctx{\ctx{c}{a}}{\ctx{a}{c}}}
=
\delta_{Q(A)}\delta_A\bigl(\ctx{a}{c}\bigr).
\]
Now \cref{prop:Q-rep} identifies coKleisli morphisms
\[
A\rightsquigarrow B
\qquad\text{with}\qquad
\CMon(Q(A),B)
\]
and hence with $\Nat(F_A,F_B)$.
If $p:A\rightsquigarrow B$ and $q:B\rightsquigarrow C$ correspond to homomorphisms
\[
\bar p:Q(A)\to B,
\qquad
\bar q:Q(B)\to C,
\]
their coKleisli composite is
\[
\bar q\circ Q(\bar p)\circ \delta_A.
\]
On a generator $\ctx{a}{c}$ this becomes
\[
\ctx{a}{c}\longmapsto \ctx{p(a,c)}{p(c,a)}\longmapsto q\bigl(p(a,c),p(c,a)\bigr),
\]
which is exactly the composite natural transformation evaluated on the $2$-point set.
\end{proof}
\begin{figure}[ht]
\centering
\[
\begin{tikzcd}[column sep=5.8em,row sep=3.2em]
A \arrow[r,"p"] & B \arrow[r,"q"] & C
\end{tikzcd}
\]
\[
\begin{tikzcd}[column sep=4.8em,row sep=3.2em]
(a,c)\in A^2 \arrow[r,mapsto,"\eta_2^p"] &
\bigl(p(a,c),p(c,a)\bigr)\in B^2 \arrow[r,mapsto,"\eta_2^q"] &
\bigl(q(p(a,c),p(c,a)),\ q(p(c,a),p(a,c))\bigr)\in C^2
\end{tikzcd}
\]
\caption{CoKleisli composition is read off from the image of the $2$-point set.}
\end{figure}
\begin{corollary}\label{cor:middle-category}
There is a factorization
\[
\CMon \longrightarrow \operatorname{CoKl}(Q) \longrightarrow \Func{\FinSet}{\Set}
\]
which is the identity on objects, whose first functor sends a homomorphism $f:A\to B$ to the context-independent cocycle
\[
p_f(a,c):=f(a),
\]
and whose second functor is fully faithful.
\end{corollary}
\begin{proof}
The first functor is the canonical inclusion of $\CMon$ into the coKleisli category of $Q$ via the counit. The second functor sends $A$ to $F_A$ and a coKleisli morphism represented by $p$ to the natural transformation $\eta^p$. Full faithfulness is exactly \cref{thm:classification}.
\end{proof}
\begin{remark}
This explains conceptually why the original functor
\[
\CMon\to \Func{\FinSet}{\Set},
\qquad
A\mapsto F_A,
\]
is not fully faithful. An ordinary homomorphism remembers only the \emph{local} contribution $a\mapsto f(a)$, whereas a general natural transformation is allowed to depend on the \emph{ambient context} $c$ as well. The missing information is precisely encoded by the comonad $Q$.
\end{remark}
\end{supplementary}
\subsection[The Eilenberg--Moore category of Q]{The Eilenberg--Moore category of \texorpdfstring{$Q$}{Q}}
It is also natural to ask what the Eilenberg--Moore category $\CMon^Q$ of the comonad $Q$ looks like.
At present we do not know a simple intrinsic description for arbitrary commutative monoids.
Nevertheless, the coalgebra structure admits a clear interpretation: a $Q$-coalgebra is a commutative monoid equipped with a coherent \emph{contextual decomposition} map.
For general background on coKleisli and Eilenberg--Moore categories of comonads, see Barr--Wells \cite{barr-wells2005}; for computer-science uses of coKleisli maps as context-dependent computations, see Uustalu--Vene \cite{uustalu-vene2008,uustalu-vene2006}; for an interpretation of coalgebras of a comonad as decomposition or basis data, compare Jacobs \cite{jacobs-bases2013}; and for a recent use of coalgebras of indexed comonads as combinatorial invariants, compare Abramsky--Shah \cite{abramsky-shah2021}.
\begin{supplementary}
In the present case, a $Q$-coalgebra is a homomorphism
\[
\gamma:A\to Q(A)
\]
satisfying
\[
\varepsilon_A\gamma=\id_A,
\qquad
\delta_A\gamma=Q(\gamma)\gamma.
\]
The counit says that the first entries of the contextual pieces reconstruct the original element. The coassociativity says that decomposing once and then decomposing the pieces again yields the same result as viewing the first decomposition itself as a contextual element.
In this sense, $\CMon^Q$ is a category of commutative monoids with coherent contextual decomposition data.
\end{supplementary}
\begin{figure}[ht]
\centering
\[
\begin{tikzcd}[column sep=5.8em,row sep=3.2em]
A \arrow[r,"\gamma"] \arrow[d,"\gamma"'] & Q(A) \arrow[d,"\delta_A"] \\
Q(A) \arrow[r,"Q(\gamma)"'] & Q(Q(A))
\end{tikzcd}
\]
\caption{A $Q$-coalgebra is a coherent contextual decomposition: the coassociativity square says that decomposing an element and then decomposing the pieces agrees with the one-step contextual decomposition in $Q(Q(A))$.}
\end{figure}
\begin{notation}
For a set $X$, let
\[
A_X:=\N^{(X)}
\]
be the free commutative monoid on $X$, and let $e_x\in A_X$ denote the characteristic multiset of $x\in X$.
Define
\[
\Sigma_X:=\{(x,T)\mid x\in X,\ T\in A_X,\ T(x)\ge 1\}.
\]
We write $\N^{(\Sigma_X)}$ for the free commutative monoid on the set $\Sigma_X$.
\end{notation}
\begin{proposition}\label{prop:Q-free}
For every set $X$, there is a natural isomorphism of commutative monoids
\[
Q(A_X)\cong \N^{(\Sigma_X)}.
\]
It sends a generator
\[
\ctx{a}{c}\in Q(A_X)
\]
to
\[
\sum_{x\in X} a(x)\cdot (x,a+c),
\]
and its inverse sends the generator $(x,T)\in \Sigma_X$ to
\[
\ctx{e_x}{T-e_x}.
\]
\end{proposition}
\begin{proof}
The point is that over a free commutative monoid, the relation
\[
\ctx{a+b}{c}=\ctx{a}{b+c}+\ctx{b}{a+c}
\]
allows one to split the first coordinate all the way down to atomic generators.
Thus every contextual generator is a sum of atomic contributions indexed by a point $x$ together with the total multiset $T=a+c$.
The displayed formulas make this precise and are inverse to each other.
\end{proof}
\begin{supplementary}
\begin{figure}[ht]
\centering
\[
\begin{tikzcd}[column sep=5.8em,row sep=3.2em]
Q(A_X) \arrow[r,shift left=.7ex,"\Phi_X"] & \N^{(\Sigma_X)} \arrow[l,shift left=.7ex,"\Psi_X"]
\end{tikzcd}
\]
\caption{The free description of $Q(A_X)$. The map $\Phi_X$ records, for each atomic summand $e_x$ of the first coordinate, the total multiset $T=a+c$ in which it sits.}
\end{figure}
\end{supplementary}
\begin{fineprint}
To see that $\Phi_X$ is well defined, note that
\[
\Phi_X\bigl(\ctx{a+b}{c}\bigr)
=
\sum_x (a(x)+b(x))\cdot (x,a+b+c)
=
\Phi_X\bigl(\ctx{a}{b+c}\bigr)+\Phi_X\bigl(\ctx{b}{a+c}\bigr).
\]
Conversely, define $\Psi_X(x,T)=\ctx{e_x}{T-e_x}$ and extend additively. Then
\[
\Psi_X\Phi_X\bigl(\ctx{a}{c}\bigr)
=
\sum_{x\in X} a(x)\cdot \ctx{e_x}{a+c-e_x}.
\]
An induction on the total size of $a$ shows that this is equal to $\ctx{a}{c}$.
Indeed, if $a=0$ there is nothing to prove; if $a=e_x+a'$ with $a'\neq 0$, then
\[
\ctx{a}{c}=\ctx{e_x}{a'+c}+\ctx{a'}{e_x+c},
\]
and the induction hypothesis applies to the second term.
The identity $\Phi_X\Psi_X=\id$ is immediate on generators $(x,T)$.
\end{fineprint}
\begin{theorem}\label{thm:Q-coalgebras-free}
Let $X$ be a set. To give a $Q$-coalgebra structure on the free commutative monoid
\[
A_X=\N^{(X)}
\]
is equivalent to giving a family of finite multisets
\[
(T_x)_{x\in X},
\qquad
T_x\in A_X,
\]
such that
\begin{enumerate}
\item $T_x(x)\ge 1$ for every $x\in X$;
\item whenever $T_x(y)\ge 1$, one has $T_y=T_x$.
\end{enumerate}
Under this correspondence, the coalgebra map is given on generators by
\[
\gamma(e_x)=\ctx{e_x}{T_x-e_x}.
\]
Equivalently, the support of each $T_x$ is a finite block, and all points in the same block carry the same total multiset.
\end{theorem}
\begin{proof}
By \cref{prop:Q-free}, the monoid $Q(A_X)$ is free on generators $(x,T)$ with $T(x)\ge 1$.
Hence the counit condition
\[
\varepsilon\gamma(e_x)=e_x
\]
forces
\[
\gamma(e_x)=(x,T_x)
\]
for a uniquely determined finite multiset $T_x$ with $T_x(x)\ge 1$.
The coassociativity square above then shows that the second layer of decomposition is determined by the same total multiset, which is exactly condition~(2).
Conversely, if a family $(T_x)$ satisfies (1) and (2), then the assignment
\[
\gamma(e_x)=\ctx{e_x}{T_x-e_x}
\]
extends uniquely to a $Q$-coalgebra.
\end{proof}
\begin{supplementary}
The theorem says that a free $Q$-coalgebra is essentially the same thing as a finite \emph{hyperedge system with multiplicities}: each generator $x$ lies in a finite multiset $T_x$, and every other point appearing in that same multiset belongs to exactly the same contextual total.
This is the free commutative-monoid analogue of a decomposition basis.
\end{supplementary}
\begin{fineprint}
To verify condition~(2), apply the coassociativity square to the generator $e_x$.
On the one hand,
\[
\delta\gamma(e_x)=\delta\bigl(\ctx{e_x}{T_x-e_x}\bigr)=\ctx{\ctx{e_x}{T_x-e_x}}{\ctx{T_x-e_x}{e_x}}.
\]
On the other hand,
\[
Q(\gamma)\gamma(e_x)=Q(\gamma)\bigl(\ctx{e_x}{T_x-e_x}\bigr)=\ctx{\ctx{e_x}{T_x-e_x}}{\gamma(T_x-e_x)}.
\]
By \cref{prop:Q-free}, the element $\ctx{T_x-e_x}{e_x}$ decomposes as
\[
\sum_{y\in X} (T_x(y)-e_x(y))\cdot \ctx{e_y}{T_x-e_y},
\]
whereas
\[
\gamma(T_x-e_x)=\sum_{y\in X} (T_x(y)-e_x(y))\cdot \ctx{e_y}{T_y-e_y}.
\]
Since $Q(A_X)$ is free on the atomic generators $\ctx{e_y}{T-e_y}$, equality of these two contextual complements implies
\[
T_y=T_x
\qquad
\text{whenever }T_x(y)-e_x(y)>0.
\]
If $y=x$ and $T_x(x)>1$, the same conclusion holds. This proves condition~(2).
Conversely, assume that the family $(T_x)$ satisfies (1) and (2). Then
\[
\gamma(e_x)=\ctx{e_x}{T_x-e_x}
\]
defines a homomorphism $\gamma:A_X\to Q(A_X)$. The counit identity is immediate:
\[
\varepsilon\gamma(e_x)=e_x.
\]
For coassociativity, compute as above:
\[
\delta\gamma(e_x)=\ctx{\ctx{e_x}{T_x-e_x}}{\sum_{y}(T_x(y)-e_x(y))\cdot \ctx{e_y}{T_x-e_y}},
\]
while
\[
Q(\gamma)\gamma(e_x)=\ctx{\ctx{e_x}{T_x-e_x}}{\sum_{y}(T_x(y)-e_x(y))\cdot \ctx{e_y}{T_y-e_y}}.
\]
Because $T_y=T_x$ whenever $T_x(y)-e_x(y)>0$, the two expressions agree.
\end{fineprint}
\begin{corollary}\label{cor:Q-coalg-N}
Coalgebra structures on the free commutative monoid $\N$ are classified by positive integers.
More precisely, for each $n\ge 1$ there is a unique $Q$-coalgebra structure $\gamma_n$ on $\N$ such that
\[
\gamma_n(1)=\ctx{1}{n-1},
\]
and every $Q$-coalgebra on $\N$ is of this form.
\end{corollary}
\begin{proof}
Apply \cref{thm:Q-coalgebras-free} with $X=\{*\}$.
A finite multiset on a one-point set is exactly a positive integer $n$, and the condition $T_*=T_*$ is automatic.
\end{proof}
\begin{remark}
The discussion above strongly suggests that $\CMon^Q$ should be thought of as a category of \emph{contextual decomposition monoids}. We do not presently know a simpler intrinsic description for arbitrary commutative monoids, but the free case already shows that the Eilenberg--Moore side is very concrete and combinatorial.
\end{remark}
\subsection{Examples and comparison with Kori--Watanabe}
This subsection is supplementary. It records worked examples and comparisons with \cite{kori-watanabe2025}.
\begin{supplementary}
We now explain how the concrete examples in Kori--Watanabe are recovered from \cref{thm:classification}. The most relevant references are their Definition~5, Example~6, Proposition~2, Theorem~1 in \S4.1, Examples~7--8, Lemma~3, and Proposition~4 \cite{kori-watanabe2025}.
\begin{proposition}[A uniform construction from a counting homomorphism]\label{prop:counting-hom}
Let $A$ and $B$ be commutative monoids, let
\[
\ell:A\to \N
\]
be a monoid homomorphism, and let
\[
b:\N\to B
\]
be a function with $b(0)=0_B$. Define
\[
p_{\ell,b}(a,c):=\ell(a)\cdot b\bigl(\ell(a+c)\bigr).
\]
Then $p_{\ell,b}$ satisfies the identities of \cref{thm:classification}, hence defines a natural transformation
\[
\eta^{\ell,b}:F_A\Rightarrow F_B.
\]
Explicitly,
\[
(\eta_X^{\ell,b}(f))(x)=\ell\bigl(f(x)\bigr)\cdot b\left(\sum_{y\in X}\ell\bigl(f(y)\bigr)\right).
\]
\end{proposition}
\begin{proof}
Since $\ell$ is additive,
\[
p_{\ell,b}(0_A,c)=0\cdot b(\ell(c))=0_B.
\]
Also,
\[
p_{\ell,b}(a+a',c)
=
(\ell(a)+\ell(a'))\cdot b\bigl(\ell(a+a'+c)\bigr)
\]
which is exactly
\[
\ell(a)\cdot b\bigl(\ell(a+a'+c)\bigr)+\ell(a')\cdot b\bigl(\ell(a+a'+c)\bigr)
=
p_{\ell,b}(a,a'+c)+p_{\ell,b}(a',a+c).
\]
Now apply \cref{thm:classification}.
\end{proof}
\begin{example}[Multisets to powersets and additive weights]\label{ex:KW-M-to-Pf}
Let $M=F_{\N}$, and let $B$ be any commutative monoid. Given a natural transformation
\[
\eta:F_{\N}\Rightarrow F_B,
\]
let $p:\N\times \N\to B$ be its associated function.
Define
\[
b(0)=0_B,
\qquad
b(s)=p(1,s-1)
\quad (s\ge 1).
\]
Then an induction on $n$ using \cref{thm:classification} shows that
\[
p(n,m)=n\cdot b(n+m)
\]
for all $n,m\in\N$.
Therefore
\[
(\eta_X(f))(x)=f(x)\cdot b\!\left(\sum_{y\in X} f(y)\right).
\]
\begin{enumerate}
\item If $B=\B$ with idempotent addition, then $n\cdot b=b$ for $n>0$, so
\[
(\eta_X(f))(x)=
\begin{cases}
b\!\left(\sum_{y\in X} f(y)\right),& f(x)>0,\\
0,& f(x)=0.
\end{cases}
\]
Equivalently,
\[
\eta_X(f)=\{x\in X\mid f(x)>0\ \text{and}\ b(\sum_{y\in X}f(y))=1\}.
\]
This is exactly the shape of Kori--Watanabe, Example~7(1).
\item If $B=\R_{\ge 0}$ under addition, then
\[
(\eta_X(f))(x)=f(x)\,b\!\left(\sum_{y\in X}f(y)\right),
\]
which is exactly their Example~7(2).
\end{enumerate}
\end{example}
\begin{example}[Finite powersets to additive targets]\label{ex:KW-Pf-to-additive}
Let $P_f=F_{\B}$, where $\B=\{0,1\}$ is viewed as the idempotent commutative monoid with $1+1=1$.
Let
\[
\eta:F_{\B}\Rightarrow F_B
\]
be a natural transformation, and let $q(c)=p(1,c)$.
Since $1+1=1$ in the source monoid, the identity in \cref{thm:classification} gives
\[
q(c)=p(1,c)=p(1,1+c)+p(1,1+c)=2\cdot q(1+c).
\]
\begin{enumerate}
\item If $B=\N$ or $B=\R_{\ge 0}$, then the only solution is $q(c)=0$ for all $c$.
Hence the only natural transformation
\[
P_f\Rightarrow M
\qquad\text{or}\qquad
P_f\Rightarrow F_{\R_{\ge 0}}
\]
is the zero transformation. This is Kori--Watanabe, Example~8(1).
\item Kori--Watanabe also compute the case
\[
P_f\Rightarrow F_{(\R_{\ge 0},\cdot,1)}
\]
in their Example~8(2). Since that target is naturally multiplicative rather than additive, it sits slightly outside the notation of the present note; nevertheless it is the same calculation after rewriting the target monoid multiplicatively.
\end{enumerate}
\end{example}
\begin{example}[A quick derivation of Kori--Watanabe, Proposition~3(4)]\label{ex:KW-subdistribution}
Kori--Watanabe, Proposition~3(4), describes natural transformations
\[
M\Rightarrow D_{\le 1},
\]
where $D_{\le 1}$ is the finite subdistribution functor.
Since $D_{\le 1}$ is a subfunctor of $F_{\R_{\ge 0}}$, \cref{ex:KW-M-to-Pf} says that any natural transformation into $F_{\R_{\ge 0}}$ has the form
\[
(\eta_X(f))(x)=f(x)\,b\!\left(\sum_{y\in X} f(y)\right).
\]
To land in $D_{\le 1}(X)$, we must have
\[
\sum_{x\in X}(\eta_X(f))(x)
=
\left(\sum_{x\in X}f(x)\right)b\!\left(\sum_{x\in X}f(x)\right)
\le 1.
\]
Thus if $s>0$ and we set
\[
c_s:=s\,b(s)\in [0,1],
\]
then
\[
(\eta_X(f))(x)=
\begin{cases}
\dfrac{f(x)}{\sum_{y\in X}f(y)}\,c_{\sum_{y\in X}f(y)},& \sum_{y\in X}f(y)>0,\\
0,& \sum_{y\in X}f(y)=0.
\end{cases}
\]
This is exactly the formula stated in Proposition~3(4), equivalently Corollary~1, of \cite{kori-watanabe2025}.
\end{example}
\begin{example}[A new example beyond the singly generated case]\label{ex:new-N2-to-N}
Let
\[
A=\N^2,
\qquad
B=\N,
\qquad
\ell(a_1,a_2)=a_1+2a_2.
\]
Applying \cref{prop:counting-hom} to this additive homomorphism $\ell$ and to any function
\[
b:\N\to\N,
\qquad
b(0)=0,
\]
we obtain a natural transformation
\[
F_{\N^2}\Rightarrow F_{\N}
\]
given by
\[
(\eta_X(f))(x)
=
\bigl(f_1(x)+2f_2(x)\bigr)
\,b\!\left(\sum_{y\in X}f_1(y)+2\sum_{y\in X}f_2(y)\right).
\]
This example is genuinely outside the singly generated framework of Kori--Watanabe, Theorem~1 in \S4.1, because the source monoid $\N^2$ is not singly generated.
\end{example}
\begin{example}[A new support-threshold example]\label{ex:new-N2-to-bool}
Let $A=\N^2$, let $B=\B=(\{0,1\},\vee,0)$, and keep the additive homomorphism
\[
\ell(a_1,a_2)=a_1+2a_2.
\]
For any subset $R\subseteq \N$ with $0\notin R$, define
\[
b_R(n)=
\begin{cases}
1,& n\in R,\\
0,& n\notin R.
\end{cases}
\]
Then \cref{prop:counting-hom} yields a natural transformation
\[
F_{\N^2}\Rightarrow P_f
\]
whose value on $f=(f_1,f_2):X\to \N^2$ is
\[
\eta_X(f)=
\left\{x\in X\ \middle|\ \ell\bigl(f(x)\bigr)>0
\ \text{and}\ \sum_{y\in X}\ell\bigl(f(y)\bigr)\in R\right\}.
\]
Equivalently,
\[
\eta_X(f)=
\left\{x\in X\ \middle|\ f(x)\neq (0,0)
\ \text{and}\ \sum_{y\in X}(f_1(y)+2f_2(y))\in R\right\}.
\]
This gives a large family of support-selection operations controlled by a weighted total mass.
\end{example}
\end{supplementary}
\section{Further discussion: toward Arrow-type no-go theorems}
This section is exploratory and may be skipped on a first reading.
\begin{supplementary}
We close with a speculative comparison with Abramsky's categorical account of Arrow's theorem \cite{abramsky2014}.
Let $\FinInj$ denote the category of finite sets and injections, and consider the presheaf topos
\[
\PSh(\FinInj)=\Func{\FinInj^{\op}}{\Set}.
\]
Define a presheaf $\mathcal R$ by
\[
\mathcal R(X)=\Pow(X\times X),
\]
with restriction along injections given by pullback of relations.
\begin{proposition}\label{prop:rel-2cosk}
The presheaf $\mathcal R\in\PSh(\FinInj)$ is $2$-coskeletal with respect to the cardinality filtration of $\FinInj$.
\end{proposition}
\begin{proof}
A binary relation is already determined by its values on singletons and pairs, so compatibility on all subsets of size at most $2$ glues uniquely to a global relation.
\begin{fineprint}
Indeed, for each pair $(x,x')\in X\times X$, the truth value of $xRx'$ is detected on the subset $\{x,x'\}$ if $x\neq x'$, and on the singleton $\{x\}$ if $x=x'$.
Conversely, any compatible family of relations on all subsets of size at most $2$ glues uniquely to a relation on $X$.
This is exactly the statement that the canonical map
\[
\mathcal R(X)\to (\cosk_2\mathcal R)(X)
\]
is bijective.
\end{fineprint}
\end{proof}
\begin{remark}\label{rem:linear-orders-3ary}
Let $\mathcal L\subseteq \mathcal R$ be the subpresheaf of linear orders.
The extra axioms cutting out $\mathcal L$ from $\mathcal R$ are local in arity at most $3$: totality and antisymmetry are detected on $2$-element subsets, while transitivity is detected on $3$-element subsets.
This strongly suggests that $\mathcal L$ should be governed by a $2{+}1$-coskeletal pattern analogous to the one proved above for $F_A$.
We do not formulate a sharp theorem here, but this is precisely the kind of low-arity control that appears in Abramsky's treatment of Arrow's theorem.
\end{remark}
Abramsky considers a category $\C$ of subsets of a universe of alternatives with injective maps, together with its inclusion subcategory, and shows that the Independence of Irrelevant Alternatives is equivalent to the naturality of a social welfare transformation
\[
\sigma:D_{\mathrm{inc}}\Rightarrow P_{\mathrm{inc}}
\]
(see \cite[\S3.2, especially Proposition~3.1]{abramsky2014}).
He then proves the Factorization Theorem \cite[Theorem~4.3]{abramsky2014}: every such social choice function factors through a Boolean-algebra homomorphism
\[
h:2^I\to 2.
\]
For finite $I$, Proposition~4.2 in the same paper says that such homomorphisms are just the projections, so dictatorship follows.
\begin{figure}[ht]
\centering
\[
\begin{tikzcd}[column sep=5.2em,row sep=3.2em]
F_A \arrow[r, "\eta"] \arrow[d, dashed, "\text{low arity}"'] & F_B \\
A\times A \arrow[r, dashed, "p"] & B
\end{tikzcd}
\qquad\qquad
\begin{tikzcd}[column sep=5.2em,row sep=3.2em]
D_{\mathrm{inc}} \arrow[r, "\sigma"] \arrow[d, dashed, "\text{pairs}"'] & P_{\mathrm{inc}} \\
2^I \arrow[r, dashed, "h"] & 2
\end{tikzcd}
\]
\caption{Two low-arity factorizations: the cocycle datum $p$ for branching functors, and Abramsky's Boolean-algebra map $h$ for Arrow theory.}
\end{figure}
\begin{remark}[A tentative unifying schema]
The present note and Abramsky's Arrow-theoretic factorization suggest a common topos-theoretic pattern for no-go theorems.
\begin{enumerate}
\item Choose a category of arities and a topos of generalized objects on it.
\item Identify a structure object whose global behavior is forced by low-arity tests.
\item Express the admissible transformations as natural transformations subject to a small amount of extra algebraic data.
\item Show that this low-arity algebraic datum has only trivial or projection-like solutions.
\end{enumerate}
On the Kori--Watanabe side the low-arity datum is the cocycle function
\[
p:A\times A\to B,
\]
while on the Arrow side it is the Boolean-algebra homomorphism
\[
h:2^I\to 2.
\]
One may hope that a sufficiently systematic study of coskeleta in toposes built from finite arities and injections will put these two no-go phenomena into a single framework.
\end{remark}
\end{supplementary}
\appendix
\section{An extended bibliographic survey}
\begin{supplementary}
This appendix is intentionally long.
Its purpose is not to mimic a general bibliography on coalgebra, category theory, topos theory, or social choice,
but to organise the literature into concentric circles around the present note.
A useful reading order is the following.
\begin{enumerate}
\item Read \cref{subsec:survey-direct} for the literature most directly adjacent to the theorem
\[
\Nat(F_A,F_B)\cong \{\,p:A\times A\to B\mid p(0,c)=0,\ p(a+b,c)=p(a,b+c)+p(b,a+c)\,\}.
\]
\item Read \cref{subsec:survey-finitary,subsec:survey-levels,subsec:survey-codensity,subsec:survey-comonads} for the structural background behind the phrases
\dq{finitary endofunctor}, \dq{arity}, \dq{coskeleton}, and \dq{finite tests}.
\item Read \cref{subsec:survey-distributive,subsec:survey-arrow,subsec:survey-global-sections} for nearby no-go literatures in theoretical computer science, social choice, and topos-theoretic physics.
\item Read \cref{subsec:survey-synthesis} for a more opinionated synthesis of what seems genuinely new here and what still remains speculative.
\end{enumerate}
\end{supplementary}
\begin{fineprint}
The references below are grouped by mathematical function rather than by chronology.
Some are direct predecessors of the present paper; some are structural background without which the present viewpoint would be unnatural; and some are neighboring no-go literatures that suggest a broader common pattern.
Whenever possible, we indicate exactly which theorem, example, or construction in a cited paper is closest to the current note.
\end{fineprint}
\subsection{Direct predecessors: monoid-valued branching and coalgebraic products}\label{subsec:survey-direct}
\begin{supplementary}
The single closest predecessor is Kori--Watanabe \cite{kori-watanabe2025}.
For the present note, the key points are their Definition~5, Example~6, Proposition~2, Theorem~1 in \S4.1, Examples~7--8, Lemma~3, Proposition~4, and Theorem~2.
Definition~5 introduces the same family of commutative-monoid-valued branching functors $F_A$.
Example~6 identifies, inside this family, the multiset functor, the covariant finite powerset functor, and two real-valued branching functors.
Proposition~2 proves that a natural transformation $F_A\Rightarrow F_B$ is already determined by its component at the $2$-point set.
Theorem~1 in \S4.1 treats the singly generated case explicitly.
Examples~7--8 spell out concrete cases for multisets and finite powersets.
Proposition~4 isolates the case
\[
F_{(\R_{\ge 0},+,0)}\Rightarrow P_f.
\]
Finally, Theorem~2 is their central no-go theorem for coalgebraic product constructions of Markov chains and NFAs.
\end{supplementary}
\begin{fineprint}
The paper \cite{kori-watanabe2025} itself sits on top of the coalgebraic product-construction framework of Watanabe--Junges--Rot--Hasuo \cite{watanabe-junges-rot-hasuo2025}, where product constructions are expressed by distributive laws and their correctness is formulated by a clean coalgebraic criterion.
In that sense, the present note should be read as a contribution to the \emph{algebra of branching functors} that underlies that framework.
A second direct predecessor is Gumm--Schr\"oder \cite{gumm-schroeder2001}, where monoid-labelled transition systems already make the functor of finitely supported monoid-valued maps appear naturally.
Historically, this is one of the cleanest places where the shape of $F_A$ is already present.
A third nearby source is Dahlqvist--Neves \cite{dahlqvist-neves2018}.
Their emphasis is different: they classify operations of the form
\[
T^n\Rightarrow T
\]
for several branching monads and semantic paradigms.
Still, their results cover powerset- and multiset-type phenomena and therefore form an important special-case predecessor for the present classification of
\[
\Nat(F_A,F_B)
\]
when source and target branching types are allowed to differ.
Finally, Jacobs' distributive law from multisets over distributions to distributions over multisets \cite{jacobs2021} is a crucial positive comparison point.
One of the morals of Kori--Watanabe and of the present note is that multisets interact much better with probability than powersets do; Jacobs' paper is a precise algebraic witness of that phenomenon.
\end{fineprint}
\subsection{Finitary functors, Lawvere theories, and arity-based descriptions}\label{subsec:survey-finitary}
\begin{supplementary}
The present note repeatedly uses the slogan that a finitary endofunctor on $\Set$ is controlled by its values on finite sets.
This is standard, and one modern reference is Ad\'amek--Milius--Moss--Urbat \cite{adamek-milius-moss-urbat2015}, which studies presentations of finitary functors.
For our purposes, the point is not the most general presentation theorem, but the habit of treating finite arities as primary data.
\end{supplementary}
\begin{fineprint}
The surrounding categorical algebra belongs to the same ecosystem as Lawvere theories and finitary monads.
Lack--Rosick\'y \cite{lack-rosicky2011} explain how the classical equivalence between Lawvere theories and finitary monads on $\Set$ extends in several directions, while Garner \cite{garner2014} revisits the ordinary equivalence from the perspective of Cauchy completion.
These references are useful because the present note is, in spirit, about reading a finitary structure from a small arity-restricted piece.
There are also neighboring combinatorial literatures that work over finite sets but emphasise slightly different classes of morphisms.
Joyal's theory of species \cite{joyal1981} focuses on finite sets and bijections, while Gambino--Kock's theory of polynomial functors \cite{gambino-kock2013} studies functors assembled from sums and powers in locally cartesian closed settings.
Neither literature is a direct precursor of the theorem proved here, because our functor uses \emph{all} maps in $\FinSet$ and a specific fiber-summation operation.
Nonetheless, both are part of the broader background in which finite-arity combinatorics becomes an organising principle for functorial algebra.
\end{fineprint}
\subsection{Topos-theoretic background: presheaves, classifying ideas, and Lawvere's problems}\label{subsec:survey-levels}
\begin{supplementary}
From a topos-theoretic viewpoint, the ambient category of the note is a presheaf category on finite arities.
General background on presheaf toposes and classifying toposes can be found in Mac Lane--Moerdijk \cite{maclane-moerdijk1992}, Johnstone \cite{johnstone2002}, and Caramello \cite{caramello2010}.
These works are not specific to $F_A$, but they explain why one should expect a small site of arities to encode a large semantic world.
\end{supplementary}
\begin{fineprint}
The specific level/coskeleton viewpoint belongs to the literature around essential localisations and Aufhebung relations.
Kelly--Lawvere \cite{kelly-lawvere1989} is the foundational reference for the lattice of essential localisations.
Kennett--Riehl--Roy--Zaks \cite{kennett-riehl-roy-zaks2011} provide explicit calculations in simplicial and cubical settings.
Menni \cite{menni2019,menni2024} develops a broader theory of monic skeleta, boundaries, and successive dimensions in toposes.
This is also the point where the present note touches the circle of ideas around Lawvere's open problems in topos theory.
On one side, Kamio--Hora \cite{kamio-hora2024} solve Lawvere's first problem by exploiting combinatorics of classifying toposes and rigid structures.
On another side, Hora--Kamio--Maehara \cite{hora-kamio-maehara2025} compute an Aufhebung relation in the topos of symmetric simplicial sets, thus contributing to Lawvere's fourth problem.
The current note is much more elementary in technique, but it lives in the same broad landscape:
take a topos or presheaf category generated by finite combinatorics, study how much of an object is forced by low-dimensional data, and extract structural consequences.
\end{fineprint}
\subsection{Codensity, finite testing, and the ultrafilter analogy}\label{subsec:survey-codensity}
\begin{supplementary}
The remark in the main text comparing
\[
\cosk_3=\Ran_{j_3}j_3^*
\]
to codensity phenomena is not merely poetic.
Leinster \cite{leinster2013} shows that the codensity monad of the inclusion
\[
\FinSet\hookrightarrow \Set
\]
is the ultrafilter monad.
Thus a right Kan extension from finite tests can recover a very global structure.
\end{supplementary}
\begin{fineprint}
Of course, the present situation is not literally the same.
The ultrafilter monad is the codensity monad of the entire inclusion of finite sets, whereas our coskeleton is the right Kan extension from the truncation
\[
j_3:\FinSet_{\le 3}\hookrightarrow \FinSet.
\]
Still, the formal similarity is meaningful.
In both cases, one reconstructs a global object from the values of a functor on a finite-test subcategory.
The slogan \dq{global structure is forced by how it responds to small probes} is common to both situations.
This is one reason the codensity analogy is helpful conceptually, even though the resulting monads are quite different.
\end{fineprint}
\subsection{Comonads, coKleisli categories, and coalgebras as decomposition data}\label{subsec:survey-comonads}
\begin{supplementary}
The new comonad $Q$ introduced in the main text places the present note in a second circle of literature, this time around coKleisli categories, Eilenberg--Moore coalgebras, and context-dependent semantics.
For general categorical background on comonads, coKleisli categories, and Eilenberg--Moore categories, one can consult Barr--Wells \cite{barr-wells2005}.
The specific theme that coKleisli arrows model context-dependent computation is central in Uustalu--Vene \cite{uustalu-vene2008,uustalu-vene2006}.
The complementary theme that coalgebras for a comonad encode decomposition or basis data is developed by Jacobs \cite{jacobs-bases2013}.
A more recent structural use of coalgebras of comonads appears in Abramsky--Shah \cite{abramsky-shah2021}, where coalgebras of resource-indexed comonads define combinatorial invariants of relational structures.
\end{supplementary}
\begin{fineprint}
These references are relevant to the present note for different reasons.
\begin{enumerate}
\item Uustalu--Vene \cite{uustalu-vene2008,uustalu-vene2006} explain a general principle:
coKleisli morphisms are maps that are allowed to depend on an ambient context.
This is exactly how the present comonad $Q$ should be read.
An ordinary homomorphism $A\to B$ depends only on the local input $a$, whereas a coKleisli morphism
\[
A\rightsquigarrow B
\]
may depend on the complementary context $c$ as well; the datum $p(a,c)$ is the explicit form of that dependence.
\item Jacobs \cite{jacobs-bases2013} studies coalgebras of a comonad induced on an algebraic category and interprets them as decomposition or basis structures.
This is a close conceptual neighbour of the present Eilenberg--Moore category $\CMon^Q$.
Our coalgebras are not the same as Jacobs' bases, but they fit the same general pattern: a coalgebra equips each element with a coherent way of being decomposed into simpler or more primitive contextual pieces.
\item Abramsky--Shah \cite{abramsky-shah2021} show that coalgebras of certain indexed comonads control combinatorial invariants such as tree-depth- and pebbling-like resource parameters.
From the present viewpoint, this is suggestive because it shows that coalgebra structures themselves can carry sharp and unexpectedly concrete combinatorial content.
The free-monoid classification in \cref{thm:Q-coalgebras-free} fits that general philosophy.
\end{enumerate}
So, while we do not know a standard pre-existing name for $\CMon^Q$, the literature does give a clear conceptual niche for it:
it is an Eilenberg--Moore category of contextual decomposition structures, sitting on one side of the coKleisli category that classifies the natural transformations $F_A\Rightarrow F_B$.
\end{fineprint}
\subsection{No-go theorems for distributive laws and combinations of effects}\label{subsec:survey-distributive}
\begin{supplementary}
A large body of theoretical computer science studies the impossibility of combining computational effects by distributive laws.
For the present note, this is one of the most important neighboring no-go literatures.
Varacca--Winskel \cite{varacca-winskel2006} is a classical landmark: it explains why the powerset and distribution monads do not combine directly in the naive way and introduces indexed valuations as a workaround.
Zwart--Marsden \cite{zwart-marsden2022} later develop a general toolbox of no-go theorems for distributive laws of monads.
\end{supplementary}
\begin{fineprint}
Several papers illustrate how rich this neighboring literature has become.
\begin{enumerate}
\item Klin--Salamanca \cite{klin-salamanca2018} prove that the iterated covariant powerset functor cannot be made into a monad.
This is not a distributive-law statement in the narrow sense, but it is very much in the same \dq{you cannot force a desired algebraic structure to exist} family.
\item Salamanca \cite{salamanca2020} proves that lattices do not distribute over powerset.
Again, this is a structural impossibility result about combining algebraic behaviour with powerset branching.
\item Goy--Petri\c{s}an--Aiguier \cite{goy-petrisan-aiguier2021} show that while the ordinary powerset monad does not distribute over itself, one can recover a weaker form of distributivity in suitable settings, including toposes and compact Hausdorff spaces.
This is especially relevant for the present paper because it shows that the right replacement for a failed distributive law may be a \emph{weaker} or \emph{relativised} structure rather than a total collapse.
\item Karamlou--Shah \cite{karamlou-shah2024} provide new no-go theorems showing that certain directed containers do not distribute over distribution monads.
This indicates that the no-go phenomenon is not restricted to the classic powerset/probability clash.
\item Keimel--Plotkin \cite{keimel-plotkin2017} and Affeldt--Garrigue--Nowak--Saikawa's line of work on combined probabilistic and nondeterministic semantics build positive alternatives to these failures.
In a related but more recent direction, Ong--Ma--Kozen \cite{ong-ma-kozen2025} explicitly implement semantics through distributions over multisets to get around the absence of a good distributive law between powerset-like and probabilistic behaviour.
\item Jacobs \cite{jacobs2021} is especially striking in the present context because it gives a positive distributive-law story for multisets and distributions.
This sits very close to Kori--Watanabe's positive multiset examples and strongly suggests that \dq{multiset branching behaves better than powerset branching} is not an accident but a recurring structural theme.
\end{enumerate}
From the viewpoint of the present note, the real interest of this literature is methodological.
It shows that impossibility results about algebraic combination are often as structural and informative as existence theorems.
Kori--Watanabe's no-go theorem for coalgebraic products \cite{kori-watanabe2025} is therefore not an isolated curiosity but part of a broader pattern in semantics.
\end{fineprint}
\subsection{Arrow, categorical social choice, and topological social choice}\label{subsec:survey-arrow}
\begin{supplementary}
The foundational source is Arrow's original impossibility theorem \cite{arrow1950} and its book-length development \cite{arrow1963}.
For the present note, however, the most important modern reference is Abramsky's categorical reformulation \cite{abramsky2014}.
That paper shows that Independence of Irrelevant Alternatives can be read as naturality, and that the whole social welfare function factors through a Boolean algebra homomorphism
\[
h:2^I\to 2.
\]
This is the closest existing literature to the idea that a no-go theorem may be encoded by a small categorical classifier.
\end{supplementary}
\begin{fineprint}
Abramsky's paper is especially important for three reasons.
First, it replaces the usual elementwise formulation of IIA by a functorial/naturality formulation.
This is precisely the sort of move that makes comparison with the present note plausible.
Second, the factorisation theorem in \cite{abramsky2014} shows that the entire social choice rule is controlled by a very small algebraic datum, namely a Boolean algebra homomorphism from $2^I$ to $2$.
This is strongly reminiscent of the way the present note compresses a natural transformation $F_A\Rightarrow F_B$ into the binary datum $p(a,c)$ satisfying one cocycle identity.
Third, Abramsky explicitly places Arrow's theorem beside no-go theorems from quantum foundations, suggesting a common structure beyond economics.
There is also a substantial topological social-choice literature that is relevant to the present note because it studies impossibility via low-dimensional combinatorics and homological obstructions.
Baryshnikov \cite{baryshnikov1993} gives a topological approach unifying impossibility theorems.
Tanaka \cite{tanaka2006} develops an explicit topological proof of Arrow's theorem for weak orders.
More recently, Rajsbaum--Ravent{\'o}s-Pujol \cite{rajsbaum-raventos2026} provide a combinatorial-topology approach to Arrow's theorem, with explicit simplicial-complex methods and a strong interface with distributed computing.
Finally, Kimelfeld--Kolaitis--Stoyanovich \cite{kimelfeld-kolaitis-stoyanovich2018} show that computational social choice also interacts fruitfully with database theory.
This is not a direct precursor of the present note, but it is another sign that social choice, logic, semantics, and finite combinatorics now meet in several places rather than in a single isolated tradition.
\end{fineprint}
\subsection{Topos- and sheaf-theoretic no-go theorems beyond social choice}\label{subsec:survey-global-sections}
\begin{supplementary}
Another neighboring family of no-go theorems comes from quantum contextuality and the Kochen--Specker theorem.
In Isham--Butterfield \cite{isham-butterfield1998} and Isham \cite{isham2010}, a central point is that a certain presheaf has no global elements.
In Abramsky--Brandenburger \cite{abramsky-brandenburger2011}, non-locality and contextuality are formulated as obstructions to the existence of global sections of a sheaf.
This is one of the cleanest places where a no-go theorem becomes a statement about presheaf or topos semantics.
\end{supplementary}
\begin{fineprint}
The comparison with the present note is not identity but analogy.
In the sheaf-theoretic contextuality literature, the obstruction is usually a \emph{failure of globality}:
there exist compatible local pieces, but they do not glue to a global section.
Abramsky--Brandenburger \cite{abramsky-brandenburger2011} make this precise, and Abramsky \cite{abramsky2014contextual} argues that the same mathematical structures reappear well beyond quantum mechanics, for example in logic, constraints, and databases.
Abramsky--Barbosa--Kishida--Lal--Mansfield \cite{abramsky-etal2015} then connect the obstruction to cohomological phenomena and paradoxes.
The present note has a different flavour.
Here one proves that a specific family of functors is already \emph{determined} by sufficiently small arity tests, and then classifies maps into it by an explicit low-arity formula.
So the mechanism is not \dq{failure to glue} but rather \dq{low arity already forces everything}.
Nonetheless, both stories are organised around the same topos-theoretic picture:
small local data, compatibility constraints, and a sharp statement about what global structure can or cannot exist.
\end{fineprint}
\subsection{Topos theory as bridge technology}\label{subsec:survey-topos-bridges}
\begin{supplementary}
If one wants a broad conceptual umbrella for why all these analogies might be worth taking seriously, Caramello's \dq{toposes as bridges} viewpoint \cite{caramello2010} is perhaps the most natural one.
In that philosophy, a topos is not only a semantic universe but also a transfer device between different mathematical theories.
\end{supplementary}
\begin{fineprint}
This perspective does not itself prove any of the theorems in the present note.
However, it gives a principled reason to look for common structure between:
\begin{itemize}
\item coalgebraic branching and product constructions,
\item presheaf-theoretic levels and coskeleta,
\item social-choice no-go theorems,
\item contextuality and global-section obstructions,
\item and distributive-law impossibility results in semantics.
\end{itemize}
The point is not that these subjects are already known to be equivalent.
Rather, the point is that a topos-theoretic or arity-theoretic reformulation often reveals a smaller classifier or obstruction than the original elementwise presentation suggests.
That principle is visible in Abramsky's Arrow paper, in contextuality-by-global-sections, and in the current note.
\end{fineprint}
\subsection{What seems genuinely new here, and what remains speculative}\label{subsec:survey-synthesis}
\begin{supplementary}
The closest direct prior work is still Kori--Watanabe \cite{kori-watanabe2025}.
What appears genuinely new in the present note is not the definition of $F_A$ itself, but the combination of two ideas:
\begin{enumerate}
\item the observation that $F_A$ is $3$-coskeletal, and
\item the resulting uniform classification of all natural transformations
\[
F_A\Rightarrow F_B
\]
for arbitrary commutative monoids $A$ and $B$ by a single function
\[
p:A\times A\to B
\]
satisfying one normalisation condition and one cocycle identity.
\end{enumerate}
To the best of our knowledge, this exact package is not already written down in the literature.
\end{supplementary}
\begin{fineprint}
There are also more speculative directions.
One is the possibility of placing the present note and Abramsky's Arrow theorem into a single framework based on low-arity coskeletality in presheaf toposes over injections.
The rough dream is that, in a category such as
\[
[\FinSet_{\mathrm{inj}}^{\op},\Set],
\]
the presheaf of binary relations is $2$-coskeletal, while the presheaf of linear orders is cut out inside it by $2$-ary and $3$-ary conditions.
If such a picture is developed cleanly, then Arrow-style impossibility could become another instance of a \dq{small-arity classifier + global no-go consequence} principle, parallel to the present paper's treatment of $F_A$.
A second direction is to connect the current $3$-coskeletal story more tightly with codensity and right Kan extension phenomena.
Leinster's account of ultrafilters \cite{leinster2013} suggests that this is not merely a superficial analogy.
A third direction is to compare the present note more systematically with the no-go theorems for distributive laws of monads.
Kori--Watanabe themselves already point toward this comparison in their related-work section \cite{kori-watanabe2025}.
The present paper suggests that low-arity classification of natural transformations may be one useful bridge between the two no-go literatures.
At the time of writing, we do not know a published theorem that already unifies all these threads.
So this part of the survey should be read as a research programme rather than as a report of established consensus.
\end{fineprint}
\section{Auxiliary proofs on lower levels}\label{sec:appendix-lower}
\begin{fineprint}
\begin{proposition}
If $A$ is nontrivial, then $F_A$ is not $n$-skeletal for any finite $n$.
\end{proposition}
\begin{proof}
Fix $n\ge 0$, and choose $a\in A$ with $a\neq 0_A$.
Let $X=n+1$, and consider the constant function
\[
f:X\to A,
\qquad
f(x)=a.
\]
Every element of $(\sk_nF_A)(X)$ is represented by some pair $(u,g)$ with $u:S\to X$, $\abs{S}\le n$, and $g\in A^S$.
Its image in $F_A(X)=A^X$ is $F_A(u)(g)$, and this function vanishes outside $u(S)$.
Hence it can be nonzero at at most $n$ points of $X$.
But $f$ is nonzero at all $n+1$ points.
Therefore $f$ does not lie in the image of
\[
(\sk_nF_A)(X)\to F_A(X),
\]
so $F_A$ is not $n$-skeletal.
\end{proof}
\begin{proposition}
If $A$ is nontrivial, then $F_A$ is not $2$-coskeletal.
\end{proposition}
\begin{proof}
Choose $a\in A$ with $a\neq 0_A$, and let $X=\{1,2,3\}$.
Define
\[
\mu:\Pow(X)\to A
\]
by
\[
\mu(T)=
\begin{cases}
0_A,& \abs{T}=0 \text{ or }1,\\
a,& \abs{T}=2 \text{ or }3.
\end{cases}
\]
For each map $u:X\to S$ with $\abs{S}\le 2$, define $\lambda_u\in A^S$ as follows.
If $S=1$, put $\lambda_u=(a)$.
If $S=2$, let $T=u^{-1}(1)$ and put
\[
\lambda_u=(\mu(T),\mu(X\setminus T)).
\]
Exactly as in the proof of \cref{prop:3cosk}, one checks that $(\lambda_u)$ is compatible.
Hence it defines an element of $(\cosk_2F_A)(X)$.
Suppose that it comes from some $f=(f_1,f_2,f_3)\in A^3$.
For each $i\in X$, let $\chi_{\{i\}}:X\to 2$ be the characteristic map of the singleton $\{i\}$.
Then
\[
F_A(\chi_{\{i\}})(f)=\lambda_{\chi_{\{i\}}}=(0_A,a).
\]
Therefore $f_i=0_A$ for all $i$.
But then the image of $f$ under the unique map $X\to 1$ is $(0_A)$, whereas by construction $\lambda_{X\to 1}=(a)$.
This is a contradiction.
Therefore $F_A$ is not $2$-coskeletal.
\end{proof}
\end{fineprint}
\subsection*{Acknowledgement}
The author would like to thank his supervisor Ryu Hasegawa for helpful discussions and suggestions.
He was supported by JSPS KAKENHI Grant Number JP24KJ0837 and FoPM, WINGS Program, the University of Tokyo.
\printbibliography
\end{document}