8
$\begingroup$

In the context of a research project in applied computer science I've come across an algebraic structure that I would informally describe as a "module over a boolean algebra," although it is not actually a module. This structure consists of a boolean algebra $B$ together with a set $V$ and two operations $\odot$ and $\oplus$ with the following signatures:

$$ \odot : B \times V \to V \\ \oplus : V \times V \to V $$

Additionally, I believe the structure should satisfy the following laws:

  • $(V, \oplus)$ is a commutative monoid. We denote its identity by $\textbf{0} \in V$.
  • For any $v \in V$ we have $0 \odot v = \textbf{0}$
  • For any $v \in V$ we have $1 \odot v = v$
  • For any $a, b \in B$ and $v \in V$ we have $a \odot (b \odot v) = (a \land b) \odot v$
  • For any $a, b \in B$ and $v \in V$ we have $(a \lor b) \odot v = (a \odot v) \oplus (b \odot v)$
  • For any $a \in B$ and $u, v \in V$ we have $a \odot (u \oplus v) = (a \odot u) \oplus (a \odot v)$

In my project I am working with particular concrete examples of this structure, and the laws above are largely reverse-engineered from those particular examples. I am therefore interested in any similar structures you know of; the laws do not need to be an exact match.

Does anyone know of a standard name for an algebraic structure like this?


Edit: The example as it arises in my project is essentially the following. Fix some $n \in \mathbb{N}$ and let $B$ be the boolean algebra of functions $\{0, \ldots, n\} \to \{0, 1\}$. I then have some set $S$ such that $V$ is given by the set of functions $S \to B$. The operations $\odot$ and $\oplus$ are then defined by pointwise $\land$ and pointwise $\lor$, respectively:

$$(a \odot f)(s) = (a \land f(s)) \\ (f \oplus g)(s) = (f(s) \lor g(s)) $$

I understand that this example as formulated above is essentially just the boolean algebra of functions $\{0, \ldots, n\} \times S \to \{0, 1\}$. However, in my actual application I do not directly manipulate explicit representations of these functions, but instead work with compact implicit representations. I became interested in this structure as a way to keep track of the properties that these implicit representations are supposed to satisfy.


Edit: Using the notation of a semimodule, with $\oplus$ represented by $+$ and $\odot$ represented by juxtaposition, the axioms above are basically just the axioms of a semimodule over $B$:

  • $(V, +)$ is a commutative monoid. We denote its identity by $0_V \in V$.
  • For any $v \in V$ we have $0 v = 0_V$
  • For any $v \in V$ we have $1 v = v$
  • For any $a, b \in B$ and $v \in V$ we have $a (b v) = (a \land b) v$
  • For any $a, b \in B$ and $v \in V$ we have $(a \lor b) v = a v + b v$
  • For any $a \in B$ and $u, v \in V$ we have $a (u + v) = a u + a v$

I am keeping the $\land$ and $\lor$ notation because $+$ on a boolean algebra can be ambiguous between "or" and "xor."

$\endgroup$
  • $\begingroup$ It would be clearer if you'd show your example (what is that addition lacking an inverse ?) and the main question for monoids is if they have the cancellation property (in which case they embed in their Grotendieck group) $\endgroup$ – reuns Sep 19 '19 at 5:49
  • $\begingroup$ Sure, I added (a simplification of) my example. In this case the monoid $(V, \oplus)$ will definitely not have the cancellation property, as I believe it is actually required to be idempotent by the fact that $\oplus$ distributes over $\lor$. $\endgroup$ – exists-forall Sep 19 '19 at 6:02
  • $\begingroup$ While the XOR operation could be defined easily for this structure, it has no relevance to my use case and wouldn't be particularly meaningful. My project is concerned with "symbolic execution," which essentially involves representing sets of possible program states symbolically as functions parameterized by unknown input from the environment. XORing two of these state representations would consist of taking all the states that could occur in exactly one of two possible executions of the program, which isn't meaningful. $\endgroup$ – exists-forall Sep 19 '19 at 6:15
  • $\begingroup$ Why not introduce the xor to obtain a true ring and $B$-module ? $a \lor b = (a \land \lnot b) \ xor\ (\lnot a \land b)\ xor \ (a \land b)$ $\endgroup$ – reuns Sep 19 '19 at 6:15
4
$\begingroup$

A module over a Boolean algebra is a special case of a semimodule over a semiring. For this reason, I strongly encourage you to drop your symbols $\odot$, $\oplus$, $\vee$ and $\wedge$, and rewrite your axioms as given in a much simpler way in the linked page.

EDIT (answer to the comments). There is a large literature on idempotent semirings, also called dioids (see for instance Gunawardena, An introduction to Idempotency ), with plenty of applications in various domains. However, apart from the two-element Boolean algebra, these idempotent semirings are rarely Boolean algebras and I am not aware of a specific term for a semimodule over a Boolean algebra.

(2) Stone's representation theorem for Boolean algebras states that every Boolean algebra is isomorphic to a certain field of sets, so I tried to look at semimodules over $\mathcal{P}(S)$ for some set $S$. However, since the negation operation is not used in the definition of a semimodule, exploiting the fact that the set of "scalars" is a Boolean algebra is not clear to me. That being said, there are plenty of ways to extend the structure of a field of sets, in particular relational structures, and this might be a source of inspiration.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, it looks like this is in fact a semimodule over a semiring where the semiring happens to be a boolean algebra. In that case I have only two remaining questions: (1) is there a special term for the case of a semimodule over a boolean algebra? and (2) are there any structures of interest formed by starting with a semimodule over a boolean algebra and strengthening it with additional axioms, exploiting the fact that the set of "scalars" is a boolean algebra and not just an arbitrary semiring? $\endgroup$ – exists-forall Sep 19 '19 at 6:13
  • $\begingroup$ @exists-forall You should probably edit your question to include (2). That way other users see it before posting an answer. $\endgroup$ – Theoretical Economist Sep 19 '19 at 8:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.