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

The alternative power-set monad

Introduction

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

$0 \notin X$;
$1 \in X$;
if $\alpha : I \to \mathbb{N}$ is any function from a finite set $I$ to the natural numbers, then $\sum_i \alpha (i) \in X$ if and only if $\lvert \alpha^{-1}(X) \rvert \in X$.

Proposition. Property F is enjoyed by:

$X_0 = \{1,2,3,4,\ldots\}$ (the set of all positive numbers);
$X_1 = \{1,3,5,7,\ldots\}$ (the set of all odd numbers).

Proof. A sum of natural numbers is:

positive if and only if a positive number of them are positive;
odd if and only if an odd number of them are odd.

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

Proof. Suppose $X$ has property F.

If $2 \in X$, then $n \in X \Rightarrow n+1 \in X$. So $X = X_0$.
On the other hand, if $2 \notin X$, then $n \in X \Rightarrow n+2 \in X$ and $n \notin X \Rightarrow n+2 \notin X$. So $X = X_1$.

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

If $A$ is a finite set, then $\Phi_X(A) = 2^A$.
If $f : A \to B$ is a function between finite sets $A$ and $B$, then $\Phi_X(f) : 2^A \to 2^B$ is defined by: \[ \Phi_X(f)(S) = \{b \in B: \lvert S \cap f^{-1}(\{b\}) \rvert \in X\} \ee{.} \]

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:

$\mu \circ \mathcal{Q}\mu = \mu \circ \mu\mathcal{Q}$ (as natural transformations $\mathcal{Q}^3 \to \mathcal{Q}$); and
$\mu \circ \mathcal{Q}\eta = \mu \circ \eta\mathcal{Q} = 1_\mathcal{Q}$ (as natural transformations $\mathcal{Q} \to \mathcal{Q}$).

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.

The Eilenberg–Moore category of $\mathcal{Q}$ is the category of finite-dimensional vector spaces over $\mathbb{F}_2$ (the field with two elements).
The Kleisli category of $\mathcal{Q}$ is the category of finite sets and binary relations between them, where composition of relations is defined by: $a \sim c$ if and only if there is an odd number of $b$ such that $a \sim b \sim c$.

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.

Generalization

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.