P0-Preface.tex

% !TeX root = P0-Intro.tex
\documentclass[Book-Poly]{subfiles}
\begin{document}


%------------ Chapter ------------%
\chapter*{Preface}\label{chapter.0}

\begin{quote}
	The proposal is also intended to [serve] equally as a foundation for the academic, intellectual, and technological, on the one hand, and for the curious, the moral, the erotic, the political, the artistic, and the sheerly obstreperous, on the other.\\
\mbox{}\hfill ---Brian Cantwell Smith\\
\mbox{}\hfill \emph{On the Origin of Objects}
\end{quote}

%\begin{quote}
%For me, though, it is difficult to resist the idea that space-time is not essentially different from matter, which we understand more deeply. If so, it will consist of vast numbers of identical units---``particles of space''---each in contact with a few neighbors, exchanging messages, joining and breaking apart, giving birth and passing away.\\
%\mbox{}\hfill ---Frank Wilczek\\
%\mbox{}\hfill \emph{Fundamentals}
%\end{quote}

\begin{quote}
And that is the way to get the greatest possible variety, but with all the order there could be; i.e. it is the way to get as much perfection as there could be.\\
\mbox{}\hfill ---Gottfried Wilhelm Leibniz\\
\mbox{}\hfill \emph{Monadology}, 58.
\end{quote}

\noindent During the Fifth International Conference on Applied Category Theory in 2022, at least twelve of the fifty-nine presentations and two of the ten posters referenced the category of polynomial functors and dependent lenses or its close cousins (categories of optics and Dialectica categories) and the way they model diverse forms of interactive behavior.
At the same time, all that is needed to grasp the construction of this category---called $\poly$ for short---is an understanding of mathematical sets and functions.
There is no need for the theory and applications of polynomial functors to remain the stuff of technical papers; $\poly$ is far too versatile, too full of potential, to be kept out of reach.

\index{applied category theory}\index{lens}\index{dialectica category}

Informally, a polynomial functor is a collection of elements we call \emph{positions} and, for each position, a collection of elements we call \emph{directions}.
There is then a natural notion of a morphism between polynomial functors that sends positions forward and directions backward, modeling two-way communication.
From these basic components, category theory allows us to construct an immense array of mathematical gadgets that model a diverse range of interactive processes.
In this book, we will establish the theory of polynomial functors and categorical constructions on them while exploring how they model interaction.

\section{Purpose and prerequisites}

A categorical theory of general interaction must be interdisciplinary by its very nature.
Already, drafts of this text have been read by everyone from algebraic geometers to neuroscientists and AI developers.
We hope to extend our reach ever further, to bring together thinkers and tinkerers from a diverse array of backgrounds under a common language by which to study interactive systems categorically.
In short---we know about $\poly$; you know about other things; but only our collective knowledge can reveal how $\poly$ could be applied to those other things.

\index{interdisciplinary}

As such, we have strived to write a friendly and accessible expository text that can serve as a stepping stone toward further investigations into polynomial functors.
We include exercises and, crucially, solutions to guide the learning process; we draw extensive analogies to provide motivation and develop intuition; we pose examples whenever necessary.
Proofs may bear far more detail than you would find in a research paper, but not so much detail that it would clutter the key ideas.
A few critical proofs are even argued through pictures, yet we contend that they are no less rigorous than the clouds of notation whose places they take.

On the other hand, there is some deep mathematical substance to the work we will discuss, drawing from the well-established theory of categories.
Although you will find, for example, a complete proof of the Yoneda lemma within these pages, we don't intend to build up everything from scratch.
There are plenty of excellent resources for learning category theory out there, catering to a variety of needs, without adding our own to the mix when our primary goal is to introduce $\poly$.
So for the sake of contributing only what is genuinely helpful, we assume a certain level of mathematical background.
You are ready to read this book if you can define the following fundamental concepts from category theory, and give examples of each:
\begin{itemize}
    \item categories,
    \item functors,
    \item natural transformations,
    \item (co)limits,
    \item adjunctions, and
    \item (symmetric) monoidal categories.
\end{itemize}
We will additionally assume a passing familiarity with the language of graph-theoretic trees (e.g.\ vertices, roots, leaves, paths).

That said, with a little investment on your part, you could very well use this book as a way to teach yourself some category theory.
If you have ever tried to learn category theory, only to become lost in abstraction or otherwise overwhelmed by seemingly endless lists of examples from foreign fields, perhaps you will benefit from a focused case study of one particularly fruitful category.
If you encounter terms or ideas that you would like to learn more about, we encourage you to look them up elsewhere, and you may find yourself spending a pleasant afternoon doing a deep dive into a new definition or theorem.
Then come back when you're ready---we'll be here.

\section*{Outline}

This book is designed to be read linearly.
\cref{part.poly} introduces the category $\poly$ and illustrates how it models interaction protocols; while \cref{part.comon} highlights a crucial operation on $\poly$, the composition product, which upgrades the theory so that it properly captures the time evolution of a dynamical system.

\bigskip

\cref{part.poly} (The category of polynomial functors) consists of:
\begin{itemize}
  \item \cref{ch.poly.rep-sets} (Representable functors from the category of sets), in which we review category-theoretic constructions on sets and the Yoneda lemma;
  \item \cref{ch.poly.obj} (Polynomial functors), in which we introduce our objects of study and present several perspectives from which to view them;
  \item \cref{ch.poly.cat} (The category of polynomial functors), in which we define $\poly$ by introducing its morphisms and demonstrate many ways to work with them, including how they model interaction protocols;
  \item \cref{ch.poly.dyn_sys} (Dynamical systems as dependent lenses), in which we use a specific class of morphisms in $\poly$ to model discrete-time dynamical systems; and
  \item \cref{ch.poly.bonus} (More categorical properties of polynomials), in which we describe a smorgasbord of additional category-theoretic structures on $\poly$.
\end{itemize}
\bigskip

\cref{part.comon} (A different category of categories) consists of:
\begin{itemize}
  \item \cref{ch.comon.comp} (The composition product), in which we examine a monoidal structure on $\poly$ given by substituting one polynomial into another;
  \item \cref{ch.comon.sharp} (Polynomial comonoids and retrofunctors), in which we show that the category of comonoids in $\poly$ with respect to the composition product is equivalent to a category of small categories we call $\smcat^\sharp$ whose morphisms are not functors;
  \item \cref{ch.comon.cofree} (Categorical properties of polynomial comonoids), in which we study the structure and utility of $\smcat^\sharp$; and
  \item \cref{ch.comon.vistas} (New horizons), in which we list open questions.
\end{itemize}

\section{Choices and conventions}\label{sec.choices}

Throughout this book, we have chosen to focus on polynomial functors of a single variable on the category of sets.
The motivation for this seemingly narrow scope is twofold: to keep matters as concrete and intuitive as possible, with easy access to elements that we can work with directly; and to demonstrate the immense versatility of even this small corner of the theory. Furthermore, the subject of multi-variate polynomials arises by considering what are called comonoids and comodules in $\poly$ \cite{spivak2023functorial}.

\index{polynomial functor!multivariate}\index{multivariate polynomial|see{polynomial functor, multivariate}}

Below is a list of conventions we adopt; while it is not comprehensive, any unusual choices are justified within the text, often as a footnote.

The natural numbers include $0$, so $\nn\coloneqq\{0,1,2,\ldots\}$. Throughout this book, when referring to finite sets, we will adopt the following convention: $\0\coloneqq\{\}=\varnothing,$ $\1\coloneqq\{1\},$ $\2\coloneqq\{1,2\},$ $\3\coloneqq\{1,2,3\}$, and so on, with $\ord{n}\coloneqq\{1,\ldots,n\}$, an $n$-element set, for each natural number $n$.
For example, in standard font, $5$ represents the usual natural number, while in sans serif font, $\5$ represents the $5$-element set $\{1,2,3,4,5\}$.
When the same variable name appears in both italicized and sans serif fonts, the italicized variable denotes a natural number and the sans serif variable denotes the corresponding set; for example, if we state that $m\in\nn$, then we also understand $\ord{m}$ to mean the set $\{1,\ldots,m\}$.
\index{set!finite}

\index{natural numbers, $\nn$}\index{set!ordinal}

The names of categories will be capitalized.
We will mostly ignore size issues, but roughly speaking small categories will be written in script (e.g.$\ \cat{C}, \cat{D}$), while large categories (usually, but not always, named) will be written in bold (e.g.\ $\poly, \Cat{C}$).
We use $\smset$ to denote the category of (small) sets and functions and $\smcat$ to denote the category of (small) categories and functors.
We use exponential notation $\cat{D}^{\cat{C}}$ to denote the category of functors $\cat{C}\to\cat{D}$ and natural transformations.
\index{set!category of sets}\index{functor!category of functors}

We write either $c\in\Ob\cat{C}$ or $c\in\cat{C}$ to denote an object $c$ of a category $\cat{C}$.
We use $\sum$ rather than $\coprod$ to denote coproducts.
We denote the collection of morphisms $f\colon c\to d$ in a category $\cat{C}$ by using the name of the category itself, followed by the ordered pair of objects: $\cat{C}(c,d)$.
We denote the domain of $f$ by $\dom f$ and the codomain of $f$ by $\cod f$.
We use $\coloneqq$ for definitions and temporary assignments, as opposed to $=$ for identifications that can be observed and proven.
We use $\iso$ to indicate an isomorphism of objects and $=$ to indicate an equality of objects, although the choice of the former does not preclude the possibility of the latter, nor does the latter necessarily imply any significance beyond an arbitrary selection that has been made.
We will freely use the definite article ``the'' to refer to objects that are unique only up to unique isomorphism.

\index{coproduct}\index{product}\index{isomorphism}\index{equality!use of}

We list nullary operations before binary ones: for example, we denote a monoidal category $\cat{C}$ with monoidal unit $I$ and monoidal product $\odot$ by $(\cat{C},I,\odot)$, or say that $(I,\odot)$ is a monoidal structure on $\cat{C}$.

\section{Past, present, and future}

The idea for this book began in 2020, originally as part of a joint work with David Jaz Myers on using categories to model dynamical systems.
It soon became clear, however, that our writing and his---while intimately related---would be better off as separate volumes.
His book is nonetheless an excellent companion to ours: see \cite{jaz}.

In the summer of 2021, we taught a course on a draft of this book that was livestreamed from the Topos Institute.
Lecture recordings are freely available at \url{https://topos.site/poly-course/}.
A follow-up workshop with additional recorded lectures and write-ups was held in early 2024; see \url{https://topos.site/events/poly-at-work/}.

The theory and application of polynomial functors comprise an active area of research.
We have laid the foundations here, but work is still ongoing.
Even while writing this, we discovered new results and uses for polynomial functors, which only goes to show how bountiful $\poly$ can be in its rewards---but of course, we had to cut things off somewhere.
We say this in the hope that you will keep the following in mind: where this book ends, the story will have just begun.

\section*{Acknowledgments}

Special thanks to David Jaz Myers: a brilliant colleague, a wonderful conversation partner, a congenial housemate, a superb chef, and an all-around good guy.

Thanks go to John Baez, Eric Bond, Spencer Breiner, Kris Brown, Matteo Capucci, Valeria de Paiva, Joseph Dorta, Brendan Fong, Richard Garner, Bruno Gavranovi\'c, Neil Ghani, Ben Goertzel, Tim Hosgood, Samantha Jarvis, Max Lieblich, Shaowei Lin, Owen Lynch, Joachim Kock, J\'er\'emie Koenig, Sophie Libkind, Joshua Meyers, Dominic Orchard, Nathaniel Osgood, Evan Patterson, Brandon Shapiro, Juliet Szatko, Tish Tanski, Todd Trimble, Adam Vandervorst, Jonathan Weinberger, and Christian Williams.

This material is based upon work supported by the AFOSR under award numbers FA9550-20-1-0348 and FA9550-23-1-0376.

\end{document}