# Calculus of Binary Relations

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?

-
You can "project" things down to the two element Boolean algebra and pretend you have invented it from a given relational structure. I imagine Pratt has chosen his perspective for some purpose in his exposition. After you have gone through it all and have a clear argument for why it might be better (for his exposition) to define the logical component in terms of the relational component, you can email him about it, or post it here. I am unlikely to read enough of it soon to support such a stance, so you will have to do it. Gerhard "Busy With Other Digital Documents" Paseman, 2011.10.24 – Gerhard Paseman Oct 24 '11 at 22:32
Or, Gerhard, someone else can answer it. :-) – Todd Trimble Oct 24 '11 at 23:38

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)\}$.

-
Sorry way out of my depth here! but I was assuming 1 = delta, intersection = composition and negation is complement with respect to 1. So n restricted to 1 is {(0,0)}. – William Pearson Oct 25 '11 at 13:31
To be clear, I was reading off the second column of the first page of the .pdf document. Yes, $\delta$ is what Pratt denotes as $1'$, to be clearly distinguished from $1$, the top element of $P(X^2)$ (viz., $X^2$ as a subset of itself). The dynamic analogue of intersection (multiplication) is relational composition, which Peirce well understood to be exactly analogous to matrix multiplication. The relative or dynamic analogue of negation was declared to be relational converse (which is not particularly apt IMO). There is much more to be said when we move from binary relations on a (cont.) – Todd Trimble Oct 25 '11 at 14:51
(cont.) fixed set or "universe of discourse" $X$ to binary relations between sets, where the relations between the so-called "static" and "dynamic" can be made much tighter. – Todd Trimble Oct 25 '11 at 14:52
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.

-
Welcome to MathOverflow, Vaughan. – Andreas Blass Mar 9 '12 at 2:17