En resumen, ¿el álgebra de relaciones (definida aquí axiomáticamente) tienen un único operador suficiente?
Dado un conjunto $D$ definir los operadores $^{-}$ , $\wedge$ , $^{c}$ , $\bullet $ en el plató $\mathcal{P}(D^{2})$ de la siguiente manera:
$$ \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} $$
Defina también
$$I = \{ (x,y) \in D^{2} : x = y \} $$
¿Existe un operador binario que (para cualquier conjunto $D$ ) puede combinarse consigo mismo para producir $^{-}$ , $\wedge$ , $^{c}$ , $\bullet $ y $I$ ¿análogo a cómo el trazo de Sheffer puede producir cualquier operador booleano?
O bien, ¿hay alguna prueba de que no existe tal operador? Si no existe ninguno, ¿cuál es el menor conjunto funcionalmente completo de operadores?
Pensamientos hasta el momento
- Soy consciente de que las lógicas modales S4 y S5 tienen operadores únicos suficientes (me sorprendió un poco esto), pero no estoy tan familiarizado con la intuición detrás de su construcción. Potencialmente, una mejor comprensión de ellas podría ayudar a construir un SSO para el álgebra de relaciones.
- No sé si la lógica modal K tiene un único operador suficiente, pero sospecho que no. Si hay una prueba de que K no tiene un único operador suficiente, podría aplicarse al álgebra de relaciones. El álgebra de relaciones parece, a nivel intuitivo, mucho más complicada que K.
- Cuando el puesto miró los operadores booleanos y cómo se relacionan entre sí, se fijó en las propiedades de los operadores que se conservan bajo la composición (por ejemplo, los operadores monótonos compuestos consigo mismos dan lugar a operadores monótonos). Una estrategia para demostrar que no existe un único operador suficiente para el álgebra de relaciones sería encontrar dos propiedades mutuamente excluyentes que se conserven bajo composición y que posea al menos uno de $^{-}$ , $\wedge$ , $^{c}$ , $\bullet$ y $I$ .
