The other day I was just sort of letting my mind wander, and I came up with an interesting monoid, which I’m calling the “monoid of partial knowledge”. So I thought I’d write about it here, partly just because it’s interesting, and partly to see whether anyone has any pointers to any literature (I’m sure I’m not the first to come up with it).
Recall that a monoid is a set with an associative binary operation and a distinguished element which is the identity for the operation.
Now, given a total order on a set with a smallest element , we get a monoid , where denotes the function which determines the larger of two elements, according to the total order on . is clearly associative, and has identity . Taking a list of elements of and summarizing it via this monoid corresponds to finding the maximum element in the list. If you think of receiving the elements of the list one by one, and applying to each new incoming value and the value of an accumulator (storing the result back into the accumulator, which should obviously be initialized to ), at any given time the value of the accumulator represents the ‘current best’, i.e. the largest element among those received so far.
The idea I had was to generalize this from a total order to a preorder. Recall that a preorder is a set equipped with a reflexive, transitive binary relation, often denoted . That is, for any , we have ; and implies . If is also antisymmetric, that is, implies , it is called a partial order, or poset. Then if or for any two elements and , we get a total order, but for a general preorder some pairs of elements may not be comparable — that is, there may be elements and for which neither nor holds.
Let’s think about this. Suppose we are given a preorder with an initial object (an initial object in this context is an element which is all other elements). We’ll initialize an accumulator to , and imagine receiving elements of one at a time. For a concrete example, suppose we are dealing with the preorder (actually also a poset) of positive integers under the divisibility relation, so our accumulator is initialized to 1. Let’s say we receive the integer 4. Clearly, 1 divides 4, so we should replace the 1 in our accumulator with 4. But now suppose we next receive the integer 5. 4 does not divide 5 or vice versa, so what should we do? We would be justified in neither throwing the 5 away nor replacing the 4, since 4 and 5 are not related to each other under the divisibility relation. Somehow we need to keep the 4 and the 5 around.
The solution is that instead of creating a monoid over itself, as we can for sets with a total order, we create a monoid over subsets of . In particular, consider the set of subsets of which do not contain two distinct elements for which . Since we are dealing with subsets of , we can actually drop the restriction that contain an initial object; the empty set will serve as the identity for the monoid.
We then define the monoid operation on two such subsets as
In words, we combine subsets and by forming the set of objects from which are not any others, with the exception of objects where both and ; in this case we keep but not . This introduces a “left bias” to ; there is also an equally valid version with right bias (in particular, ).
Now, let’s show that this really does define a valid monoid. First, we need to show that is closed over . Suppose . Suppose also that are distinct elements of with ; we’ll derive a contradiction. First, we cannot have or by definition of . Now suppose . The fact that together with the definition of imply that we must have , a contradiction. Finally, suppose . Again, by the definition of we must have . But then the fact that , together with the definition of and the facts that and imply that , a contradiction again. Hence contains no such pair of elements.
The fact that the empty set is the identity for is clear. (Incidentally, this is why we require that none of the sets in contain two distinct elements with one the other: if were such a set, we would have .) I leave the associativity of as an exercise for the reader (translation: this post is already getting long, the associativity of seems intuitively obvious to me, and I don’t feel like formalizing it at the moment — perhaps I’ll try writing it up later). I also leave as an interesting exercise the following theorem: if are both finite and nonempty, then is also finite and nonempty.
In our example from before, we could now begin with in our accumulator. After receiving the singleton set , our accumulator would have that singleton set as its new value. Upon receiving , our accumulator would become . Receiving would result in (5 divides 10, so the 5 is discarded); if we later received , we would simply have in our accumulator (both 4 and 10 divide 20).
I like to think of this as the monoid of partial knowledge. If we consider to be a set of facts or beliefs, some better (more reliable, useful, correct, complete, etc.) than others, then elements of correspond to possible sets of beliefs. describes how a set of beliefs changes upon encountering a new set of facts; some of the new facts may supersede and replace old ones, some may not impart any new information, and some may be completely new facts that aren’t related to any currently known.
Now, why can this be thought of as a generalization of the monoid on a totally ordered set? Well, look what happens when we replace in the definitions above with a totally ordered set with relation : first of all, the restriction on (no two elements of a set in should be related by ) means that contains only the empty set and singleton sets, so (ignoring the empty set) is isomorphic to . Now look at the definition of , with replaced by (and replaced by ):
But and are both subsumed by , so we can rewrite this as
An analysis of is similar, and it is clear that .
I note in passing that although it might appear shady that I swept that “ignoring the empty set” bit under the rug, everything really does check out: technically, to see a direct generalization of to , we can require that have an initial object and that contains only finite, nonempty sets. Then it requires a bit more work to prove that is closed, but it still goes through. I used the formulation I did since it seems more general and requires less proving.
Anyway, this ended up being longer than I originally anticipated (why does that always happen!? =), so I’ll stop here for now, but next time I’ll give some actual Haskell code (which I think ends up being pretty neat!), and talk about one relatively common design pattern which is actually a special case of this monoid.