Álgebra cilíndrica

En matemáticas , la noción de álgebra cilíndrica , desarrollada por Alfred Tarski , surge de forma natural en la algebrización de la lógica de primer orden con igualdad . Esto es comparable al papel que desempeñan las álgebras booleanas en la lógica proposicional . Las álgebras cilíndricas son álgebras booleanas dotadas de operaciones de cilindrificación adicionales que modelan la cuantificación y la igualdad . Se diferencian de las álgebras poliádicas en que estas últimas no modelan la igualdad.

El álgebra cilíndrica no debe confundirse con el concepto de teoría de la medida álgebra cilíndrica que surge en el estudio de las medidas de conjuntos de cilindros y el álgebra σ cilíndrica .

Un álgebra cilíndrica de dimensión${\displaystyle \alpha }$(dónde${\displaystyle \alpha }$es cualquier número ordinal ) es una estructura algebraica${\displaystyle (A,+,\cdot ,-,0,1,c_{\kappa },d_{\kappa \lambda })_{\kappa ,\lambda <\alpha }}$de tal manera que${\displaystyle (A,+,\cdot ,-,0,1)}$es un álgebra booleana ,${\displaystyle c_{\kappa }}$un operador unario en${\displaystyle A}$por cada${\displaystyle \kappa }$(llamada cilindrificación ), y${\displaystyle d_{\kappa \lambda }}$un elemento distinguido de${\displaystyle A}$por cada${\displaystyle \kappa }$y${\displaystyle \lambda }$(llamada diagonal ), de modo que se cumplen las siguientes condiciones:

(C1) ${\displaystyle c_{\kappa}0=0}$

(C2) ${\displaystyle x\leq c_{\kappa }x}$

(C3) ${\displaystyle c_{\kappa }(x\cdot c_{\kappa }y)=c_{\kappa }x\cdot c_{\kappa }y}$

(C4) ${\displaystyle c_{\kappa }c_{\lambda }x=c_{\lambda }c_{\kappa }x}$

(C5) ${\displaystyle d_{\kappa \kappa }=1}$

(C6) Si${\displaystyle \kappa \notin \{\lambda ,\mu \}}$, entonces${\displaystyle d_{\lambda \mu }=c_{\kappa }(d_{\lambda \kappa }\cdot d_{\kappa \mu })}$

(C7) Si${\displaystyle \kappa \neq \lambda }$, entonces${\displaystyle c_{\kappa }(d_{\kappa \lambda }\cdot x)\cdot c_{\kappa }(d_{\kappa \lambda }\cdot -x)=0}$

Suponiendo una presentación de lógica de primer orden sin símbolos de función , el operador${\displaystyle c_{\kappa }x}$modelos cuantificación existencial sobre variable${\displaystyle \kappa }$en fórmula${\displaystyle x}$mientras el operador${\displaystyle d_{\kappa \lambda }}$modela la igualdad de variables${\displaystyle \kappa }$y${\displaystyle \lambda }$Por lo tanto, reformulados utilizando notaciones lógicas estándar, los axiomas se leen como:

(C1) ${\displaystyle \exists \kappa .{\mathit {false}}\iff {\mathit {false}}}$

(C2) ${\displaystyle x\implies \exists \kappa .x}$

(C3) ${\displaystyle \exists \kappa .(x\wedge \exists \kappa .y)\iff (\exists \kappa .x)\wedge (\exists \kappa .y)}$

(C4) ${\displaystyle \exists \kappa \exists \lambda .x\iff \exists \lambda \exists \kappa .x}$

(C5) ${\displaystyle \kappa =\kappa \iff {\mathit {true}}}$

(C6) Si${\displaystyle \kappa }$es una variable diferente de ambas${\displaystyle \lambda }$y${\displaystyle \mu }$, entonces${\displaystyle \lambda =\mu \iff \exists \kappa .(\lambda =\kappa \wedge \kappa =\mu )}$

(C7) Si${\displaystyle \kappa }$y${\displaystyle \lambda }$son variables diferentes, entonces${\displaystyle \exists \kappa .(\kappa =\lambda \wedge x)\wedge \exists \kappa .(\kappa =\lambda \wedge \neg x)\iff {\mathit {false}}}$

Un álgebra de conjuntos cilíndricos de dimensión${\displaystyle \alpha }$es una estructura algebraica${\displaystyle (A,\cup ,\cap ,-,\emptyset ,X^{\alpha },c_{\kappa },d_{\kappa \lambda })_{\kappa ,\lambda <\alpha }}$de tal manera que${\displaystyle \langle X^{\alpha },A\rangle }$es un campo de conjuntos ,${\displaystyle c_{\kappa }S}$es dado por${\displaystyle \{y\in X^{\alpha }\mid \exists x\in S\ \forall \beta \neq \kappa \ y(\beta )=x(\beta )\}}$, y${\displaystyle d_{\kappa \lambda }}$es dado por${\displaystyle \{x\in X^{\alpha }\mid x(\kappa )=x(\lambda )\}}$. ^{[ 1 ]} Esto necesariamente valida los axiomas C1–C7 de un álgebra cilíndrica, con${\displaystyle \cup }$en lugar de${\displaystyle +}$,${\displaystyle \cap }$en lugar de${\displaystyle \cdot }$, establecer complemento para complemento, vacío establecer como 0,${\displaystyle X^{\alpha }}$como la unidad, y${\displaystyle \subseteq }$en lugar de${\displaystyle \leq }$El conjunto X se denomina base .

Una representación de un álgebra cilíndrica es un isomorfismo de dicha álgebra a un álgebra de conjuntos cilíndricos. No todas las álgebras cilíndricas tienen una representación como álgebra de conjuntos cilíndricos. ^{[ 2 ]} Es más sencillo conectar la semántica de la lógica de predicados de primer orden con el álgebra de conjuntos cilíndricos. (Para más detalles, véase § Lecturas adicionales ). 

Las álgebras cilíndricas se han generalizado al caso de la lógica de múltiples tipos (Caleiro y Gonçalves 2006), lo que permite un mejor modelado de la dualidad entre fórmulas y términos de primer orden.

Cuando${\displaystyle \alpha =1}$y${\displaystyle \kappa ,\lambda }$están restringidos a ser solo 0, entonces${\displaystyle c_{\kappa }}$se convierte${\displaystyle \exists }$, las diagonales pueden eliminarse, y el siguiente teorema del álgebra cilíndrica (Pinter 1973):

${\displaystyle c_{\kappa }(x+y)=c_{\kappa }x+c_{\kappa }y}$

se convierte en el axioma

${\displaystyle \exists (x+y)=\exists x+\exists y}$

del álgebra booleana monádica . El axioma (C4) se elimina (se convierte en una tautología). Por lo tanto, el álgebra booleana monádica puede considerarse una restricción del álgebra cilíndrica al caso de una variable.

• lógica algebraica abstracta
• Cálculo lambda y lógica combinatoria : otros enfoques para modelar la cuantificación y eliminar variables.
• Las hiperdoctrinas son una formulación categórica de las álgebras cilíndricas.
• Álgebras de relaciones (AR)
• álgebra poliádica
• Descomposición algebraica cilíndrica

• Charles Pinter (1973). "Un álgebra simple de lógica de primer orden" . Notre Dame Journal of Formal Logic . XIV : 361–366 .
• Leon Henkin , J. Donald Monk y Alfred Tarski (1971) Álgebras cilíndricas, Parte I. North-Holland. ISBN 978-0-7204-2043-2.
• Leon Henkin, J. Donald Monk y Alfred Tarski (1985) Álgebras cilíndricas, Parte II . North-Holland.
• Robin Hirsch e Ian Hodkinson (2002) Álgebras de relaciones mediante juegos. Estudios en lógica y fundamentos de las matemáticas, North-Holland.
• Carlos Caleiro, Ricardo Gonçalves (2006). «Sobre la algebrización de lógicas multisortadas» (PDF) . En J. Fiadeiro y P.-Y. Schobbens (eds.). Actas de la 18.ª conferencia internacional sobre tendencias recientes en técnicas de desarrollo algebraico (WADT) . LNCS. Vol.  4409. Springer. pp. 21–36 . ISBN  978-3-540-71997-7.

• Imieliński, T. ; Lipski, W. (1984). "El modelo relacional de datos y álgebras cilíndricas" . Journal of Computer and System Sciences . 28 : 80–102 . doi : 10.1016/0022-0000(84)90077-1 .

• Ejemplo de álgebra cilíndrica por CWoo en planetmath.org