Take the 2-minute tour ×

Given a set $X$, write $\mathrm{heaps}(X)$ for the set of all finite heaps (or 'multisets', if you prefer) on $X$.

Under this definition, it is well-known that if a binary operation $*$ on a set $X$ is

  1. commutative
  2. associative
  3. and has an identity

then this operation gives rise to a function $\Phi : \mathrm{heaps}(X) \rightarrow X$ in a natural way.

For example, the operation $+$ on the real numbers gives rise to the function $\sum,$ defined on finite heaps of real numbers. Similarly, $\times$ gives rise to $\prod,$ etc.

In particular, if we write $\uplus$ for the heapic sum, then $\Phi$ can be characterized as the unique function satisfying $$\Phi(H \uplus I) = \Phi(H) * \Phi(I)$$ for all $H,I \in \mathrm{heaps}(X).$

Now let $X =$ the Boolean domain, which we will denote $\mathbb{B}.$

It is a surprising fact that the operators IFF (denoted $\leftrightarrow$) and XOR (denoted $\not\leftrightarrow$) satisfy conditions 1,2 and 3, at least in classical logic. In particular, they're associative, which I don't find at all intuitive.

Anyway, it follows that $\leftrightarrow$ and $\not \leftrightarrow$ each yield a function $\mathrm{heaps}(\mathbb{B}) \rightarrow \mathbb{B}.$

I'm interested in these functions from both a logical, and an algebraic point of view.

Where can I learn more?

Discussion. Lets denote them as follows.

  1. The function obtained from $\leftrightarrow,$ lets denote $\mathrm{ef}.$
  2. The function obtained from $\not\leftrightarrow,$ lets denote $\mathrm{ot}.$

These names are motivated as follows. For $H \in \mathrm{heaps}(\mathbb{B}),$ we have that $\mathrm{ef}(H)$ is true iff an even number of elements of $H$ are false; similarly, $\mathrm{ot}(H)$ is true iff an odd number of elements of $H$ are true.

Anyway, the functions $\mathrm{ef}$ and $\mathrm{ot}$ have some seriously neat properties.

Here's what I've got so far.

Firstly, we can negate pairs without changing anything. $$\mathrm{ef}(H \uplus \{x,y\}) = \mathrm{ef}(H \uplus \{\neg x, \neg y\}),\;\; \mathrm{ot}(H \uplus \{x,y\}) = \mathrm{ot}(H \uplus \{\neg x, \neg y\})$$

Secondly, negation passes straight through uninhibited.

$$\mathrm{ef}(H \uplus \{\neg x\}) = \neg\mathrm{ef}(H \uplus \{ x\}),\;\; \mathrm{ot}(H \uplus \{\neg x\}) = \neg\mathrm{ot}(H \uplus \{ x\})$$

Thirdly, repeated variables annihilate as follows.

$$\mathrm{ef}(H \uplus \{x,x\}) = \mathrm{ef}(H),\;\; \mathrm{ot}(H \uplus \{x,x\}) = \mathrm{ot}(H)$$

Fourthly, $$\mathrm{ef}(\emptyset) = \top,\;\; \mathrm{ot}(\emptyset) = \bot$$

Fifthly, they're equal precisely when the cardinality of $H$ is odd.

$$|H| \;\mathrm{odd} \implies \mathrm{ef}(H) = \mathrm{ot}(H)$$ $$|H| \;\mathrm{even} \implies \mathrm{ef}(H) \neq \mathrm{ot}(H)$$

Sixthly, they interact nicely.

$$\mathrm{ef}(H \uplus \mathrm{ot}(I)) = \mathrm{ot}(\mathrm{ef}(H) \uplus I)$$

Seventhly, we can split into cases as follows.

$$\mathrm{ef}(H \uplus I) = [\mathrm{ef}(H) \wedge \mathrm{ef}(I)] \vee [\neg\mathrm{ot}(H) \wedge \neg\mathrm{ot}(I)]$$

$$\mathrm{ot}(H \uplus I) = [\mathrm{ot}(H) \wedge \neg\mathrm{ef}(I)] \vee [\neg\mathrm{ef}(H) \wedge \mathrm{ot}(I)]$$

Dualising the above expressions:

$$\mathrm{ot}(H \uplus I) = [\mathrm{ot}(H) \vee \mathrm{ot}(I)] \wedge [\neg\mathrm{ef}(H) \vee \neg\mathrm{ef}(I)]$$

$$\mathrm{ef}(H \uplus I) = [\mathrm{ef}(H) \vee \neg\mathrm{ot}(I)] \wedge [\neg\mathrm{ot}(H) \vee \mathrm{ef}(I)]$$

share|improve this question
Comment: what you call $\text{heaps}$ (which I wouldn't call by this name because it is already taken; see en.wikipedia.org/wiki/Heap_(mathematics) ) is the monad associated to the adjunction between sets and commutative monoids (see en.wikipedia.org/wiki/Monad_(category_theory) ). It is a variation of what is in computer science called the list monad. –  Qiaochu Yuan Aug 31 '13 at 18:10
On what concerns the mentioned 'non-intuitive' classical associativity of $\leftrightarrow$, it might be interesting to notice that the intuitionistic IFF (or its negation) is indeed not associative. –  J Marcos Aug 31 '13 at 18:55
@QiaochuYuan, thanks for the info. Those Monad's in particular look very interesting - closure operators have always been pretty much my favourite concept. Regarding terminology, I use "heap" because I find "bag" vulgar, and because "subheap" is preferable to "submultiset." But if anyone knows of better alternative, I'll gladly change. –  goblin Sep 1 '13 at 1:01

1 Answer 1

up vote 3 down vote accepted

Algebraically, XOR is more usually viewed as the addition in $\mathbb Z_2$ (where 0 corresponds to false and 1 to true), which accounts for many of its nice properties -- in particular for the fact that it's associative. In this role it is often notated $\oplus$, so the multiset extension would be $\bigoplus$.

The multiplication in $\mathbb Z_2$ is just $\land$ under the same identification, so algebra and logic align nicely here. (In fact we can recover the entire logical structure from the ring operations since $A\lor B = A \oplus B \oplus (A\land B)$ and $\neg A=1\oplus B$ -- this provides the correspondence between a Boolean algebra and a Boolean ring, which is any ring in which $x^2=x$ for all $x$).

IFF is simply the De Morgan dual of $\oplus$, so it is associative (etc) as well. Alternatively we can write $(A\leftrightarrow B)=A\oplus B\oplus 1$, so by associativity and commutativity, $$ a_1 \leftrightarrow a_2 \leftrightarrow \cdots \leftrightarrow a_n = a_1 \oplus a_2 \oplus \cdots \oplus a_n \oplus \underbrace{1\oplus\cdots\oplus1}_{n-1\text{ ones}}$$ where the underbraced part is either $0$ or $1$ according to whether $n$ is odd or even.

The fact that negation "passes through" these operators can be explained by the fact that $\neg A = 1\oplus A$, and the "lifting" of negations out of $\oplus$ is then just associativity. Since $1\oplus 1=0$, an even number of negations cancel each other out.

share|improve this answer
Thanks. If there's anywhere good for learning more about $\mathbb{Z}_2$, please indicate tell. The problem is that for $n \geq 3$, the groups in the family $\mathbb{Z}_{n \geq 3}$ lack most of the structure that makes $\mathbb{Z}_2$ interesting; in particular, I don't think there's anything like negation for the groups in $\mathbb{Z}_{n \geq 3}.$ –  goblin Sep 1 '13 at 1:26
Also, I really like the way you explained the connection between $\leftrightarrow$ and $\oplus$. I sort of new it already, but the way its written in your answer is just crystal clear. –  goblin Sep 1 '13 at 5:29
@user18921: I'm not aware offhand of any source dedicated to $\mathbb Z_2$. Most of the "interesting" structure you speak about is probably a feature of the ring having characteristic 2 (which means that addition and subtraction are the same operation), or possibly of being a Boolean ring (which implies characteristic 2). You definitely want to study some ring theory here (the group structure is not enough to express all the interesting facts). Most abstract algebra textbooks should give it (though mixed with lots of other suff). –  Henning Makholm Sep 1 '13 at 9:08
Cryptography and (in particular) coding theory make heavy use of higher algebra with $\mathbb Z_2$ as the base field, so it is possible that a text in one of these areas would contain a succinct overview of it. I don't have any titles to name, though. –  Henning Makholm Sep 1 '13 at 9:10

Your Answer


