What is the polynomial functor for the Bag monad

Ben Sprott 06/12/2018. 2 answers, 398 views
ct.category-theory monads

I may be wrong, but we should be able to write the Bag monad in a polynomial form. The bag monad, is exectly the multiset monad whose category of algebras are the commutative monoids. Another name for the bag monad is a container.

Containers are synonymous with polynomail functors. The data that defines a container are precisely the following morphisms in a locally Cartesian closed category $C$:

$$ 1 \xleftarrow{\text{f}} X \xrightarrow{\text{g}} Y \xrightarrow{\text{h}} 1 $$

Where $1$ is the terminal object in $C$. This defines an endofunctor for which there is a monad. Specifically, the endofunctor is :

$$ C/W \xrightarrow{\text{f^* }} C/X \xrightarrow{\Pi_g} C/Y \xrightarrow{\Sigma_h} C/Z $$

We are interested in endofunctors so $W$ and $Z$ are $1$ in $Set$.

What is the polynomial form of the bag monad?

2 Answers


The bag monad is not polynomial.

Any polynomial endofunctor must preserve pullbacks: $f^*$ and $\Pi_g$ preserve all limits since they’re right adjoints, while $\Sigma_h$, being just the forgetful functor from a slice category, is well known (and easily seen) to preserve all connected limits.

However, the bag monad doesn’t preserve pullbacks. Write $B$ for the bag monad, and consider the sets $X = \{a,b\}$, $Y = \{y,z\}$, and view their product as a pullback, $X \times Y = X \times_1 Y$. Then the canonical map $B(X \times Y) \to B(X) \times_{B(1)} B(Y)$ fails to be injective, since $\{(a,y),(b,z)\}$ and $\{(a,z),(b,y)\}$ are distinct in $B(X \times Y)$ but have the same image in $B(X)$ and $B(Y)$.

This example — and the fact that commutativity forms an obstacle to being polynomial, and similar sorts or representation — has appeared notably before in the literature, in for instance the note 3-computads do not form a presheaf category by Michael Makkai and Marek Zawadowski, and (essentially) in Carlos Simpson’s paper Homotopy types of strict 3-groupoids.


The free multiset functor is not polynomial in the standard sense; it is though in a categorified sense if you somehow keep track of the different ways two expressions are the same thanks to commutativity: for that you need to pass from the category Set to the 2-category of groupoids. See Data Types with Symmetries and Polynomial Functors over Groupoids.


HighResolutionMusic.com - Download Hi-Res Songs

1 BLACKPINK

Kiss And Make Up flac

BLACKPINK. 2018. Writer: Soke;Kny Factory;Billboard;Chelcee Grimes;Teddy Park;Marc Vincent;Dua Lipa.
2 Martin Garrix

Waiting For Tomorrow flac

Martin Garrix. 2018. Writer: Pierce Fulton;Mike Shinoda;Martijn Garritsen;Brad Delson.
3 John Legend

Written In The Stars flac

John Legend. 2018. Writer: Kiana Brown;Santoy;Kevin White;Mike Woods;MZMC;The Heavy Group;Rice N' Peas.
4 Martin Garrix

Access flac

Martin Garrix. 2018. Writer: Martin Garrix.
5 Martin Garrix

Yottabyte flac

Martin Garrix. 2018. Writer: Martin Garrix.
6 Alan Walker

Diamond Heart flac

Alan Walker. 2018. Writer: Alan Walker;Sophia Somajo;Mood Melodies;James Njie;Thomas Troelsen;Kristoffer Haugan;Edvard Normann;Anders Froen;Gunnar Greve;Yann Bargain;Victor Verpillat;Fredrik Borch Olsen.
7 Cardi B

Taki Taki flac

Cardi B. 2018. Writer: Bava;Juan Vasquez;Vicente Saavedra;Jordan Thorpe;DJ Snake;Ozuna;Cardi B;Selena Gomez.
8 Bradley Cooper

Shallow flac

Bradley Cooper. 2018. Writer: Andrew Wyatt;Anthony Rossomando;Mark Ronson;Lady Gaga.
9 Post Malone

Sunflower flac

Post Malone. 2018. Writer: Louis Bell;Billy Walsh;Carter Lang;Swae Lee;Post Malone.
10 Dyro

Latency flac

Dyro. 2018. Writer: Martin Garrix;Dyro.
11 Lady Gaga

I'll Never Love Again flac

Lady Gaga. 2018. Writer: Benjamin Rice;Lady Gaga.
12 Rita Ora

Let You Love Me flac

Rita Ora. 2018. Writer: Rita Ora.
13 Zara Larsson

Ruin My Life flac

Zara Larsson. 2018. Writer: Delacey;Michael Pollack;Stefan Johnson;Jordan Johnson;Sermstyle;Jackson Foote.
14 Halsey

Without Me flac

Halsey. 2018. Writer: Halsey;Delacey;Louis Bell;Amy Allen;Justin Timberlake;Timbaland;Scott Storch.
15 ZAYN

Fingers flac

ZAYN. 2018. Writer: Zayn Malik;Alex Oriet;David Phelan.
16 Dewain Whitmore

Burn Out flac

Dewain Whitmore. 2018. Writer: Dewain Whitmore;Ilsey Juber;Emilio Behr;Martijn Garritsen.
17 Mako

Rise flac

Mako. 2018. Writer: Riot Music Team;Mako;Justin Tranter.
18 Bradley Cooper

Always Remember Us This Way flac

Bradley Cooper. 2018. Writer: Lady Gaga;Dave Cobb.
19 Blinders

Breach (Walk Alone) flac

Blinders. 2018. Writer: Dewain Whitmore;Ilsey Juber;Blinders;Martin Garrix.
20 Julia Michaels

There's No Way flac

Julia Michaels. 2018. Writer: Ian Kirkpatrick;Justin Tranter;Julia Michaels;Lauv.

Language

Popular Tags