The implication operation on partitions

Partitions and equivalence relations

In a 2001 commemorative volume for my mathematical mentor, Gian-Carlo Rota, three of his associates noted that “the only operations on the family of equivalence relations fully studied, understood and deployed are the binary join $\lor$ and meet $\land$ operations.” This note defines the apparently new operation of implication for partitions, an operation that was key to the development of the logic of partitions that is dual to the usual logic of subsets.

A partition $\pi = \{B\}$ on a set U (two or more elements) is a set of disjoint subsets $B,B',\ldots\subseteq U$ , called the blocks of the partition, whose union is U. The notion of a partition on a set is equivalent to the notion of an equivalence relation $R$ on U which is a binary relation on U, i.e., a subset of the product $U \times U$ , that is reflexive ( $uRu$ for all $u \in U$ ), symmetric (if $uRu'$ then $u'Ru$ for all $u,u' \in U$ ), and transitive (if $uRu'$ and $u'Ru''$ then $uRu''$ for any $u,u',u'' \in U$ ). Given a partition $\pi$ , the corresponding equivalence relation has $uR_{\pi}u'$ if $u,u' \in B$ for some block $B \in \pi$ . Given an equivalence relation $R \subseteq U\times U$ , the corresponding partition $\pi_{R}$ has as blocks the equivalence classes $[u]=\{u':uRu'\}$ of the equivalence relation.

Turning the partial ordering right side up

Most of the previous work on partitions has been guided by thinking in terms of equivalence relations. For instance, there is a partial order on the set of partitions $\Pi(U)$ on U. Given two partitions $\pi=\{B\}$ and $\sigma =\{C\}$ , the corresponding equivalence relations $R_{\pi}$ and $R_{\sigma}$ are subsets of $U \times U$ so it might seem natural to order the partitions according to the inclusion ordering of the corresponding equivalence relations: $\pi \leq \sigma$ if $R_{\pi}\subseteq R_{\sigma}$ rather than the opposite ordering.

That is the partial order traditionally used for partitions and it is even called the “refinement ordering.” For instance, this is the ordering used in the Wikipedia article for lattices in the first illustration giving the “lattice of partitions” on a four-element set. But in terms of blocks, it means that for any block $B\in\pi$ , there is a block $C\in\sigma$ such that $B\subseteq C$ so that the partition lower down on the so-called “refinement” ordering is more refined rather than less refined. The late Gian-Carlo Rota used to joke that it should be called the “unrefinement” ordering. Indeed, in a recent book Combinatorics: The Rota Way by two of Rota’s former students, that traditional ordering is aptly called the “reverse refinement” ordering.

For the purposes of seeing the analogies between the usual logic of subsets and the dual logic of partitions, it is important to use the reverse of the “reverse refinement” ordering which would be properly called the refinement ordering on partitions: $\sigma \preceq \pi$ if for any block $B\in\pi$ , there is a block $C\in\sigma$ such that $B\subseteq C$ . With this ordering, the top 1 of the ordering is the discrete partition on U whose blocks are the singletons $\{u\}$ for the elements $u\in U$ . The bottom 0 of the ordering is the indiscrete partition, nicknamed the “blob,” whose only block contains all the elements of U.

The closure space $U \times U$

The complement of an equivalence relation $R_{\pi} \subseteq U\times U$ might be called a partition relation. The ordered pairs $(u,u')\in U\times U$ in an equivalence relation $R_{\pi}$ are the pairs of elements that are indistinct according to that equivalence relation so they may be called the indistinctions or, for short, indits of the relation and symbolized as: $indit(\pi)=R_{\pi}$ . The pairs in the complementary partition relation are the pairs of elements in distinct blocks of the partition so they might be called the distinctions or dits of the partition and symbolized as $dit(\pi)=indit(\pi)^{c}$ which is the complement of the indit set within the product set $U\times U$ .

The product set $U\times U$ has a natural closure operation defined on it, namely the reflexive-symmetric-transitive closure. Thus the closure of any subset of the “closure space” $U\times U$ is the smallest equivalence relation containing the set. The closed sets (the sets equal to their closure) are just the equivalence relations and also the indit sets of partitions on U. The complements of the closed sets are defined as usual as the open subsets which are thus the partition relations and the dit sets of partitions on U. But, nota bene, this is not a topological closure operation; the union of two closed subsets is not necessarily closed, i.e., the union of two equivalence relations is not necessarily an equivalence relation. With a closure operation and complementation, we can also as usual define the interior of a subset as the “complement of the closure of the complement.” Thus the interior of a subset is the largest dit set or open set contained in the subset.

Three methods to define partition operations

With this machinery, we are now ready to define operations on partitions such as the two lattice operations of join and meet, and the operation crucial for logic, the implication operation. There are three principal ways to define partition operations:

the set-of-blocks method,
the closure-space method, and
the graph-theoretic method.

A fourth method using complete subalgebras of powerset Boolean algebras will not be used here.

To illustrate the set-of-blocks method, suppose we are given two partitions $\pi=\{B\}$ and $\sigma =\{C\}$ by their sets of blocks. The blocks of the join $\pi \lor \sigma$ are the non-empty intersections $B\cap C$ of the blocks of the two partitions. In the traditional treatment using the opposite partial ordering, this would be the “meet” of the two partitions. The set-of-blocks definition of the partition meet (i.e., the traditional “join”) is more complicated so we will use the other two methods described below to define it.

A simple illustration of the closure space method is also provided by the join. Given the two dit sets of partitions, the dit set of their join is just the union: $dit(\pi \lor \sigma)=dit(\pi) \cup dit(\sigma)$ . That defines the same partition as the set-of-blocks definition. One might similarly try to define the dit set of the meet $\pi \land \sigma$ as the intersection of the respective dit sets. But we previously noted that union of closed sets is not necessarily closed and thus the intersection of two open sets (i.e., dit sets) is not necessarily open. Hence we have to apply the interior operator, and this yields the correct definition: $dit(\pi \land \sigma) = int(dit(\pi) \cap dit(\sigma))$ .

The third method of defining the “logical” partition operations is the graph-theoretic method which uses the ordinary truth tables from Boolean logic. Consider the complete simple (at most one arc or link between nodes and no loops at nodes) undirected graph on the node set U. Given a partition $\pi$ on U, we label the arc connecting u and u’ with $T\pi$ if u and u’ are in distinct blocks of $\pi$ , and we label the arc $F\pi$ if u and u’ are in the same block of $\pi$ . Given another partition $\sigma$ , we can similarly label all the arcs with $T\sigma$ or $F\sigma$ so that each arc has two “signed” labels.

Then consider the Boolean truth table for whatever logical operation one wants to define such as the meet.

$\pi$	$\sigma$	$\pi \land \sigma$
T	T	T
T	F	F
F	T	F
T	F	F

The truth table can then be summarized by specifying that the Boolean conditions for $T(\pi \land \sigma)$ are “ $T\pi$ and $T\sigma$ ” while the Boolean conditions for $F(\pi \land \sigma)$ are “ $F\pi$ or $F\sigma$ .” Returning now to complete graph, we see that each arc has either the true conditions $T(\pi \land \sigma)$ or the false conditions $F(\pi \land \sigma)$ holding on it. Then we throw away all the arcs where the true conditions $T(\pi \land \sigma)$ hold, and we retain all the other arcs which are the ones where the false conditions $F(\pi \land \sigma)$ hold.

Given any simple undirected graph on the node set U, two nodes are connected if there is a finite chain of links connecting the two nodes. Then connectedness immediately determines a partition on the node set where the blocks are the sets of nodes which are connected to one another. To define the partition $\pi \land \sigma$ , simply use the graph constructed above where the links are the ones where the false conditions $F(\pi \land \sigma)$ hold. The partition determined on U by the connected components is the partition meet $\pi \land \sigma$ . It is the same partition previously by the closure-space method.

The importance of the implication operation

Logic studies valid formulas or tautologies which can be defined as formulas that will always evaluate to the top 1 regardless of what subsets or partitions are substituted for the atomic variables. But if the only operations are the lattice operations of join and meet, then the only tautologies in either the lattice of subsets $\mathcal{P}(U)$ of U or the lattice of partitions $\Pi(U)$ on U are trivialities such as $\pi \lor 1$ . And as three Rota associates noted in a 2001 commemorative volume: “the only operations on the family of equivalence relations fully studied, understood and deployed are the binary join $\lor$ and meet $\land$ operations.”

Instead of studying tautologies, one might try to study identities, e.g., $\pi \land \sigma \preceq \pi$ , which are partial order statements between two formulas that are true for any subsets or partitions substituted for the atomic variables in the formulas. But Philip Whitman showed in 1946 that lattices of partitions are so versatile that any lattice can be embedded in a lattice of partitions. Hence any identity true in all partition lattices would be true in all lattices. It would be a general lattice-theoretic identity saying nothing specific about partitions. In order to get some specific identities involving lattice-theoretic formulas (i.e., only using join and meet), one would have to restrict the class of partition lattices. Indeed, in the closest previous work, Rota and colleagues developed a “logic of commuting equivalence relations” using only the lattice operations but obtaining non-trivial identities by restricting to lattices of commuting equivalence relations [Finberg, David, Matteo Mainetti and Gian-Carlo Rota 1996. The Logic of Commuting Equivalence Relations. In Logic and Algebra. A. Ursini and P. Agliano eds., New York: Marcel Dekker: 69-96].

But the study of identities is quite restrictive in comparison with the study of tautologies. When one has the implication operation, then corresponding to every identity, there is a tautology obtained by replacing the partial ordering relation by the implication. For instance the identity $\pi \preceq \pi \lor \sigma$ transforms into the tautology $\pi \Rightarrow (\pi \lor \sigma)$ . But even rather simple tautologies like modus ponens, $(\sigma \land (\sigma \Rightarrow \pi)) \Rightarrow \pi$ , do not express identities between lattice formulas (due to the appearance of the other implication sign in the premise).

Defining the partition implication operation

Implication is the quintessentially logical operation, and the definition of this operation on partitions was a key step in the development of partition logic. We have three methods to define partition operations, and each one suggests an appropriate definition of implication.

As noted in the remark above, one desideratum in the implication is: $\sigma \preceq \pi$ if and only if $\sigma \Rightarrow \pi = 1$ . In the lattice of partitions $\Pi(U)$ the top 1 is the discrete partition of all singletons. Now $\sigma \preceq \pi$ means that for any $B\in \pi$ there is a $C\in \sigma$ such that $B\subseteq C$ . Hence a suitable candidate definition would be to say that for any $B\in \pi$ such that there is a $C\in \sigma$ with $B \subseteq C$ , then B is discretized (i.e., replaced by singletons) in $\sigma \Rightarrow \pi$ , and otherwise B remains whole in $\sigma \Rightarrow \pi$ . Thus the candidate definition of $\sigma \Rightarrow \pi$ is like $\pi$ except that whenever a block of $\pi$ is contained in a block of $\sigma$ , then that block of $\pi$ is discretized.

Using the closure space method, the analogy with the topological interpretation of intuitionistic propositional logic suggests itself. In the usual subset interpretation, the implication $S\Rightarrow T$ is defined as $S^{c}\cup T$ for subsets $S,T \subseteq U$ . In the intuitionistic topological interpretation, S and T would be open subsets of a topological space U, and the interior operator would have to be added to ensure that the result was open: $S\Rightarrow T = int(S^{c}\cup T)$ . Since we have “open subsets” and an “interior” operator in the closure space treatment of partitions, the obvious suggested definition of the implication would be: $dit(\sigma \Rightarrow \pi)=int(dit(\sigma)^{c}\cup dit(\pi))$ .

And finally there is the graphical method that allows us to generate a partition operation from a Boolean truth table. Hence we take the Boolean truth table for the implication $\sigma \Rightarrow \pi$ , and we note that the Boolean conditions for $F(\sigma \Rightarrow \pi)$ are “ $T\sigma$ and $F\pi$ .” Then we retain the arcs of the complete graph labelled $T\sigma,F\pi$ and throw out the other arcs. The connected components in the resulting graph are the blocks in this candidate definition of $\sigma \Rightarrow \pi$ . In the following example of a graph, the arcs where the false conditions $T\sigma,F\pi$ are thickened.

All three of the definitions are equivalent, and that is the definition used in the development of partition logic. My introductory paper on partition logic in The Review of Symbolic Logic can be downloaded from this site here.