Category Theory
Zulip Server
Archive

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

Stream: learning: questions

Topic: discussing isomorphisms

Daniel Geisler (Dec 19 2023 at 01:49):

I am writing my first proofs on isomorphisms and am looking for the different proper ways to express the following in category theory terms, both notationly and diagramatically.

$${d^n \over dx^n} f(g(x)) = \sum_{\pi \in \mathcal{P} [n]} \epsilon_{n,\pi}=\sum_{\sigma\in \mathcal{S}[n]} \tau_{n,\sigma}$$

The term $\mathcal{P} [n]$ is the integer partitions of $n$ while $\mathcal{S} [n]$ is the set partitions (from Analytics Combinatorics)

I tend to think in terms of there being an isomorphism between the integer partitions and $f(g(x))$, but technically there is an isomorphism between the the enumerations of the integer partitions of $n$ and the additive terms of $D^nf(g(x))$. How would folks express the connection between composite functions, integer and set partitions?

Background

Wikipedia has nice articles on Bell polynomials and Faà di Bruno's formula.

Let

$$\begin{align} &\pi = 1^{m_1}2^{m_2}\cdots n^{m_n} ,\\ &\epsilon_{n,\pi}=\frac{n!} {m_1!\,1!^{m_1}\,m_2!\,2!^{m_2}\,\cdots\,m_n!\,n!^{m_n}}\cdot f^{(m_1+\cdots+m_n)}(g(x))\cdot \prod_{j=1}^n\left(g^{(j)}(x)\right)^{m_j} ,\\ &\tau_{n,\sigma} = f^{(\left|\mathcal{S}\right|)}(g(x))\cdot\prod_{B\in\sigma }g^{(\left|B\right|)}(x) , \end{align}$$

Daniel Geisler (Dec 19 2023 at 01:56):

where $\pi$ denotes a partition of $\mathcal{P}[n]$, usually denoted by $1^{m_1}2^{m_2}\cdots n^{m_n}$ with $m_1+2m_2+ \cdots n \cdot m_n = n$; where $m_i$ is the number of parts of size $i$.

$\pi$ runs through the set $P$ of all integer partitions of the set $\{1,\ldots,n\}$,
$\sigma$ runs through the set $S$ of all set partitions of the set $\{1,\ldots,n\}$,
$B \in \sigma$ means the variable $B$ runs through the list of all of the blocks of the partition $\sigma$.

Daniel Geisler (Dec 19 2023 at 10:42):

The following theorem simply expresses the well known connection between the integer partitions of $n$ and the $n$ th derivatives of the composite functions.

Theorem. $P[n]_\pi \cong \epsilon_{n,\pi}$

Proof.

Let,

$u: P[n]_\pi \to \epsilon_{n,\pi}$

$v: \epsilon_{n,\pi} \to P[n]_\pi$

Daniel Geisler (Dec 19 2023 at 10:43):

Prove $u \circ v = 1_{P_n}$

Select an object $\pi$ from $P_n$. There is a unique expression $\epsilon_{N,\pi}$ associated with $\pi$.
Now select $\epsilon_{N,\pi}$. The values for $\pi$ can be read from the expression ${m_1!\,1!^{m_1}\,m_2!\,2!^{m_2}\,\cdots\,m_n!\,n!^{m_n}}$ giving a unique $\pi$ in $P_n$. Thus the two transforms map $\pi$ to $\pi$ which is equivalent to $1_{P_n}$.
$\blacksquare$

Daniel Geisler (Dec 19 2023 at 10:43):

Prove $1_{\epsilon_n} = v \circ u$

Select an additive term from $\epsilon_{n,\pi}$. The values for $\pi$ can be read from the subexpression ${m_1!\,1!^{m_1}\,m_2!\,2!^{m_2}\,\cdots\,m_n!\,n!^{m_n}}$ giving a unique $\pi$ in $P_n$.
Now select the object $\pi$ from $P_n$. There is a unique expression $\epsilon$ associated with $\pi$.
Thus the two transforms returns $\epsilon_{n,\pi}$ to $\epsilon_{n,\pi}$ which is equivalent to $1_{\epsilon_n}$.
$\blacksquare$

Simon Burton (Dec 19 2023 at 13:48):

Have you considered combinatorial species ? That seems to be the go-to answer whenever we want to categorify combinatorial identities... But there's probably many other answers as well.

Daniel Geisler (Dec 19 2023 at 15:14):

My work in based the book Combinatorial Analytics, which is a wonderful application of species. My use of $\mathcal{P}$ comes from the book as well as the following relevant notations. I'm setting things up to discuss species, but my focus here is on writing using regular category theory. I suspect that there are multiple elegant ways to express and explain my proof. For example, I do know about using the notation $\mathcal{F}[n]$ as a structure type. But I use $\mathcal{P}[n]_\pi$ when there might be preexisting notation I should use to communicate effectively.

$$\mathcal{I}=(1,2,3,\cdots)$$

$$\mathcal{P}=MSET(\mathcal{I})$$

$$\mathcal{S}=SET(SET_{\ge 2}(\mathcal{Z}))$$

Daniel Geisler (Dec 22 2023 at 02:12):

So is the relationship between $\mathcal{P}[n]$, the integer partitions of $n$ and $\mathcal{S}[n]$, the set partitions of $n$, that $\mathcal{S}[n]$ is a left adjoint of $\mathcal{P}[n]$ and that $\mathcal{P}[n]$ is a right adjoint of $\mathcal{S}[n]$?

And label functor in Combinatorial Analytics is a natural transformation?