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
where
and
.
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.
Pingback: Collecting unstructured information with the monoid of partial knowledge « blog :: Brent -> [String]
If P is a partial order, not just a preorder, then you can think about this in (what I think is) a simpler way: you’re looking at upward-closed subsets, and your monoid operation is union. I suggest that this is in fact the “monoid of partial knowledge”, and your preorder version is the “monoid of partial and possibly inconsistent knowledge” :-).
(You can work with upward-closed subsets in the preorder case too, but it’s not quite the same as your monoid — your monoid is what you get when you insist that there not be two equivalent minimal elements in the subset, and adopt a particular rule for enforcing this. In other words, mine involves a more radical embracing of inconsistency than yours. Your record-accumulating example would switch to using the set monad instead of the Maybe monad if you used the upward-closed-subset version of the monad of partial knowledge.)
Dunno if any of that’s useful…
Not counting the “left bias”, I think this can be thought of as a monoid whose addition is set addition in the Alexandrov topology on the preorder.