The Only Distributive Law Over the Powerset Monad Is the One You Know
2026-02-13 • Logic in Computer Science
Logic in Computer Science
AI summaryⓘ
The authors studied how certain mathematical constructions called set functors can interact with the powerset operation in a consistent way, which is known as a distributive law. They found that for a broad class of functors called accessible functors, such a distributive law exists exactly when the functor keeps certain structures called weak pullbacks intact, and in this case the distributive law is unique. However, for other functors that are not accessible, like the powerset functor itself, multiple distributive laws can exist. This shows that uniqueness depends on specific properties of the functor involved.
set functorpowerset monaddistributive lawKleisli lawaccessible functorweak pullbackBarr extensioncategory of relationsfunctor extension
Authors
Sergey Goncharov, Dirk Hofmann, Pedro Nora, Lutz Schröder, Paul Wild
Abstract
Distributive laws of set functors over the powerset monad (also known as Kleisli laws for the powerset monad) are well-known to be in one-to-one correspondence with extensions of set functors to functors on the category of sets and relations. We study the question of existence and uniqueness of such distributive laws. Our main result entails that an accessible set functor admits a distributive law over the powerset monad if and only if it preserves weak pullbacks, in which case the so-called power law (which induces the Barr extension) is the unique one. Furthermore, we show that the powerset functor admits exactly three distributive laws over the powerset monad, revealing that uniqueness may fail for non-accessible functors.