$ \newcommand{\ee}[1]{\; \textrm{#1}} \newcommand{\eqn}[1]{\qquad \textrm{(#1)}} $

The alternative power-set monad


Definition. Let $X \subseteq \mathbb{N}$. We say that $X$ has property F if:

Proposition. Property F is enjoyed by:

Proof. A sum of natural numbers is:

Proposition. If $X$ has property F then $X = X_0$ or $X = X_1$.

Proof. Suppose $X$ has property F.

Proposition. If $X$ has property F then we can define a functor $\Phi_X$ on the category of finite sets as follows:

Proof. The fact that $0 \notin X$ and $1 \in X$ is enough to guarantee that $\Phi_X(1_A) = 1_{2^A}$. Now suppose $g : A \to B$ and $f : B \to C$. For $S \subseteq A$ and $c \in C$, let $I = f^{-1}(\{c\})$ and apply property F to the function $\alpha : I \to \mathbb{N}$ defined by $\alpha(b) = \lvert S \cap g^{-1}(\{b\}) \rvert$. This tells us that $\sum_{f(b)=c} \lvert S \cap g^{-1}(\{b\}) \rvert \in X$ if and only if $\lvert \{b \in f^{-1}(\{c\}): \lvert S \cap g^{-1}(\{b\}) \rvert \in X \} \rvert \in X$. But the first of these numbers is just $\lvert S \cap (fg)^{-1}(\{c\}) \rvert$, and the second is $\lvert \Phi_X(g)(S) \cap f^{-1}(\{c\}) \rvert$; so we have $c \in \Phi_X(fg)(S)$ if and only if $c \in \Phi_X(f)(\Phi_X(g)(S))$. Therefore $\Phi_X(fg) = \Phi_X(f) \Phi_X(g)$.

The choice $X = X_0$ gives us the standard power-set functor $\mathcal{P}$. Here we wish to investigate the alternative power-set functor $\mathcal{Q} = \Phi_{X_1}$.

Monadic interpretation

The functor $\mathcal{Q}$ gives rise to a monad on the category $C$ of finite sets. The two natural transformations involved are $\eta : 1_C \to \mathcal{Q}$ and $\mu : \mathcal{Q}^2 \to \mathcal{Q}$, where $\eta_X(x) = \{x\}$ and $\mu_X(\mathcal{A})$ (where $\mathcal{A}$ is a set of subsets of $X$) is the symmetric difference $\Delta \mathcal{A}$ of all the sets in $\mathcal{A}$.

It is necessary to show, first, that these are natural transformations, and secondly, that they satisfy the coherence conditions for a monad, namely that:

The second of these two conditions is easy to verify. The first requires some athleticism to see directly, but drops out easily if one writes it in terms of characteristic functions $\chi$. Note that \[ \chi_{\mu_X(\mathcal{A})}(x) = \sum_{S \in 2^X} \chi_\mathcal{A}(S) \chi_S(X) \] where the sum is modulo 2. The proof of monadicity then amounts to rewriting the sum \[ \sum_{\mathcal{A} \in 2^{2^X}, S \in 2^X} \chi_\mathcal{\Xi}(\mathcal{A}) \chi_\mathcal{A}(S) \chi_S(x) \] (where $\Xi \in 2^{2^{2^X}}$ and $x \in X$) in two different ways.

Since we have a monad, we have a corresponding Eilenberg–Moore category and Kleisli category.

These are the same! Indeed, given a finite set $A$ we can form a finite-dimensional vector space over $\mathbb{F}_2$ with $A$ as its basis; and given a relation $\sim$ between $A$ and $B$ we can form the linear map defined by $a \mapsto \sum_{a \sim b} b$. This construction is an isomorphism.

One can also consider this as the category whose objects are natural numbers and where the morphisms from $m$ to $n$ are the $m \times n$ matrices over $\mathbb{F}_2$, with composition defined by matrix multiplication.

Analogy with the power set

Does this give us a useful alternative notion of 'power set'? It seems to provide more structure, or at least a different structure, because it is based on the field with two elements rather than the lattice with two elements, and there are a lot of things one can do with a field that one can't do with a lattice (like solving equations).

Boolean circuits

A boolean circuit with input and output bits indexed by finite sets $A$ and $B$ respectively can be regarded as a function $2^A \to 2^B$. If we are given a function $f : A \to B$, we can form a circuit $\mathcal{P}(f)$ with a connection from each input bit $a \in A$ to the output bit $f(a) \in B$, where several connections entering the same output bit are combined by logical 'or'. Alternatively, we can form a circuit $\mathcal{Q}(f)$, with the same connections as for $\mathcal{P}(f)$, but where several connections entering the same output bit are combined by 'exclusive or'. The functoriality of $\mathcal{Q}$ means that when we compose two such circuits, we can replace the result with a single such circuit (corresponding to functional compostition), without changing its behaviour.


Let $M$ be a commutative monoid. Define a functor $\Phi_M$ on the category $C$ of finite sets by $\Phi_M(X) = M^X$ (the set of functions from $X$ into $M$), and for a function $f : X \to Y$, $\alpha : X \to M$ and $y \in Y$, \[ \Phi_M(f)(\alpha)(y) = \sum_{x \in f^{-1}(\{y\})} \alpha(x) \ee{.} \] The two 'power set' functors $\mathcal{P}$ and $\mathcal{Q}$ considered above correspond to the two commutative monoids with two elements (which in turn correspond to logical 'or' and 'exclusive or').

Alec Edgington, August 2012. Email Alec at emplexis dot com.