Calculus of Binary Relations

Question

I was reading "Origins of the Calculus of Binary Relations" by Vaughan Pratt where he says "it consists of two components, a logical or static component and a relative or dynamic component" but it seems as if it should be possible to define the "static component" purely in terms of the "dynamic component". Is this the case?

Answer 1

As I understand it, and in more modern-day terms, the question asks whether it is possible to define the operations $0, 1, \cap, \cup, \neg$ on $P(X^2)$ (operations belonging to the "static component") in terms of "dynamic" operations $\delta', \delta, \circ, \circ', (-)^{op})$ where $\circ$ is relational composition (as an operator on $P(X^2)$):

$$(R \circ S)(x, z) := \exists_y R(x, y) \wedge S(y, z);$$

$\circ'$ is De Morgan dual to $\circ$:

$$(R \circ' S)(x, z) := \forall_y R(x, y) \vee S(y, z);$$

$\delta \in P(X^2)$ is the diagonal subset (the identity for $\circ$), $\delta'$ is its complement (the identity for $\circ'$), and $(-)^{op}$ is the relational converse:

$$R^{op}(x, y) = R(y, x).$$

The answer is no. For example, take $X$ to be $\mathbb{R}$, and consider the relation $n$ where $n(x, y) \Leftrightarrow (x = -y)$. Let $n'$ be the complement of $n$. I claim that the set $A = \{0, 1, \delta, \delta', n, n'\}$ is closed under the dynamic operations. It's clear that each of these elements is a fixed point under relational converse. It's also easy to check that $n \circ n = \delta$, and that

$$n' \circ n = \delta' = n \circ n',$$

$$\delta' \circ n = n' = n \circ \delta',$$

$$n' \circ n' = 1 = n' \circ \delta' = \delta' \circ n' = \delta' \circ \delta',$$

$$1 \circ x = 1 = x \circ 1 \qquad x \in A, x \neq 0$$

$$0 \circ x = 0 = x \circ 0 \qquad x \in A$$

Since $A$ is closed under complementation and under $\circ$, it is also closed under $\circ'$. Thus $A$ is closed under all the dynamic operations. However, it is clearly not closed under intersection, since $n \cap \delta$ is the singleton $\{(0, 0)\}$.

Answer 2

1. That was an historical paper, and the distinction in question was first drawn by De Morgan and then Peirce under the rubric of logical vs. relative as modifiers of sum and product. In my own papers introducing dynamic logic as a binary version of unary static logic, starting in 1976 (based on class notes from 1974), I used those terms merely as the ones that occurred to me, as I was not familiar with the history and so did not know about "logic" vs. "relative." Had I been aware of that precedent, "dynamic logic" might these days be called "relative logic," except that its modal character (see 2 below) mitigates against that.

2. My "Origins" paper was for the annual evening LICS talk, for LICS'92. (It nearly didn't happen as I'd just had a quintuple bypass six weeks earlier. Fortunately I'd recovered by then, and was able two weeks later to visit St. Petersburg, Moscow, Tver to give a conference talk, and Paris.) An earlier paper,

   Pratt, V.R., ``Dynamic algebras as a well-behaved fragment of relation algebras'', Proc. Algebra and Computer Science, ed. Bergman, Maddux, and Pigozzi, LNCS 425, 77-110, Springer-Verlag, 1990. Also Report No. STAN-CS-90-1309, CS Dept., Stanford, 1990,

   which was originally given as a talk at the workshop "Algebraic Logic and Universal Algebra in Theoretical Computer Science" held in Ames, Iowa in 1988, made the point that the complexity of various logical problems is lower for modules (understood as two-object gadgets) than for monoids as one-object structures. The underlying intuition was that by limiting the operations in the "dynamic" object (where the monoid lived) and moving the Boolean stuff to the "static object" (a sort of cul-de-sac from which there was no return), the complexity was greatly reduced over that of relation algebra where all the operations can interact, creating much harder problems. Even without star, Tarski's RA is undecidable, whereas dynamic algebra is decidable even with star, in fact I was even able to show its equational theory was decidable in deterministic exponential time.

3. Nevertheless the monoid situation greatly interested me, and in 1990, in response to a request by Johan van Benthem to speak at JELIA'90, I came up with Action Logic for my talk there. You can read about this under "Action Algebra" on Wikipedia, whose lead redes as follows:

   In algebraic logic, an action algebra is an algebraic structure which is both a residuated semilattice and a Kleene algebra. It adds the star or reflexive transitive closure operation of the latter to the former, while adding the left and right residuation or implication operations of the former to the latter. Unlike dynamic logic and other modal logics of programs, for which programs and propositions form two distinct sorts, action algebra combines the two into a single sort. It can be thought of as a variant of intuitionistic logic with star and with a noncommutative conjunction whose identity need not be the top element. Unlike Kleene algebras, action algebras form a variety, which furthermore is finitely axiomatizable, the crucial axiom being a•(a → a)* ≤ a. Unlike models of the equational theory of Kleene algebras (the regular expression equations), the star operation of action algebras is reflexive transitive closure in every model of the equations.

   What the lead doesn't say is that it remains an open question after 22 years as to whether Action Logic as an equational theory is decidable. (The word problem of course would be undecidable, the monoid alone should be enough to kill decidablity.) Some people who've solved long-standing open problems, in particular Istvan Nemeti and his colleagues, have been unable to crack this one even after all this time. So if you like this area and have been looking for something easier than the Riemann Hypothesis to hone your problem-solving skills on, just remember that every famously solved problem had its first solver. People thought Andrew Wiles was just another person beating his head against a brick wall until he proved Fermat's Last Theorem. This one seems very unlikely to be anywhere near that hard, it should fall simply to a good insight taking 5-10 pages to explain.