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

**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}$.

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}$).

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$.

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.

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).

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`.