5
$\begingroup$

In brief, does the relation algebra (defined here axiomatically) have a sole sufficient operator?

Given a set $D$, define operators $^{-}$, $\wedge$, $^{c}$, $\bullet $ on the set $\mathcal{P}(D^{2})$ as follows:

$$ \begin{align} R^{-} &= \{ (x,y) \in D^{2} : (x,y) \notin R \} \\ R \wedge S &= \{ (x,y) \in D^{2} : (x,y) \in R \wedge (x,y) \in S \} \\ R^{c} &= \{ (x,y) \in D^{2} : (y,x) \in R \} \\ R \bullet S &= \{ (x,y) \in D^{2} : \exists z \in D ( (x,z) \in S \wedge (z,y) \in R ) \} \end{align} $$

Also define

$$I = \{ (x,y) \in D^{2} : x = y \} $$

Is there a binary operator which (for any set $D$) can be combined with itself to produce $^{-}$, $\wedge$, $^{c}$, $\bullet $ and $I$, analogous to how the Sheffer stroke can produce any Boolean operator?

Alternatively, is there a proof that no such operator exists? If none exists, what is the smallest functionally complete set of operators?

Thoughts so far

  • I'm aware that the modal logics S4 and S5 have sole sufficient operators (I was a little surprised at this), but I'm not so familiar with the intuition behind their construction. Potentially a better understanding of them might help with constructing an SSO for the relation algebra.
  • I don't know whether the modal logic K has a sole sufficient operator, but I suspect it doesn't. If there's a proof out there that K doesn't have a sole sufficient operator, it could be applied to the relation algebra. The relation algebra seems on a crude intuitive level to be a lot more complicated than K.
    • When Post looked at the Boolean operators and how they relate to each other, he looked at properties of the operators preserved under composition (e.g. monotonic operators composed with themselves result in monotonic operators). A strategy for showing no sole sufficient operator exists for the relation algebra would be to find two mutually exclusive properties which are preserved under composition and possessed by at least one of $^{-}$, $\wedge$, $^{c}$, $\bullet$ and $I$.
$\endgroup$

1 Answer 1

2
+50
$\begingroup$

There is a ternary sole sufficient operation but no binary one. Let $$\tau(X,Y)=(X\bullet Y^c)\vee(I \wedge (1\bullet(X \vee Y) \bullet 1)^-)$$ and $$\begin{align} \delta(X,Y,Z) =& ((X\wedge Y)^- \wedge (1\bullet (Y \veebar Z)\bullet 1)^-) \\ &\vee (\tau(X,Y)\wedge(1\bullet(Y \veebar Z)\bullet1)) \end{align} $$

Then $\{\tau, \uparrow \}$ is a functionally complete set of binary operation for the relation algebra and $\delta$ is a sole sufficient operation, as shown in:

Andreka, H.; Comer, S.D.; Nemeti, I., Clones of operations on relations, Universal algebra and lattice theory, Proc. Conf., Charleston/S.C. 1984, Lect. Notes Math. 1149, 17-21 (1985). ZBL0568.08005.

More details are in

Jónsson, Bjarni; Tarski, Alfred, Boolean algebras with operators. II, Am. J. Math. 74, 127-162 (1952). ZBL0045.31601.

$\endgroup$
4
  • $\begingroup$ From what I read in the first paper, it is still an open question whether a sole sufficient binary operator exists. Is this correct, or does the second paper refute this? $\endgroup$
    – Carralpha
    Oct 7, 2017 at 11:17
  • $\begingroup$ The second paper is older... $\endgroup$ Oct 7, 2017 at 17:50
  • $\begingroup$ Just wanted to check - the phrasing of your answer suggested that there definitely isn't a sole sufficient binary operator, so it could have been the case that this had been proven, and the later paper had missed it. $\endgroup$
    – Carralpha
    Oct 7, 2017 at 18:33
  • $\begingroup$ You're right 😅 $\endgroup$ Oct 7, 2017 at 18:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .