Álgebra cilíndrica

Algebrización de la lógica de primer orden con igualdad

En matemáticas , la noción de álgebra cilíndrica , desarrollada por Alfred Tarski , surge de manera natural en la algebrización de la lógica de primer orden con igualdad . Esto es comparable al papel que desempeñan las álgebras de Boole para la lógica proposicional . Las álgebras cilíndricas son álgebras de Boole 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.

Definición de álgebra cilíndrica

Un álgebra cilíndrica de dimensión (donde es cualquier número ordinal ) es una estructura algebraica tal que es un álgebra de Boole , un operador unario en para cada (llamado cilindrificación ), y un elemento distinguido de para cada y (llamado diagonal ), tal que se cumple lo siguiente: ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle (A,+,\cdot ,-,0,1,c_{\kappa },d_{\kappa \lambda })_{\kappa ,\lambda <\alpha }}$ ${\displaystyle (A,+,\cdot ,-,0,1)}$ ${\displaystyle c_{\kappa }}$ ${\displaystyle A}$ ${\displaystyle \kappa }$ ${\displaystyle d_{\kappa \lambda }}$ ${\displaystyle A}$ ${\displaystyle \kappa }$ ${\displaystyle \lambda }$

(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 , entonces ${\displaystyle \kappa \notin \{\lambda ,\mu \}}$ ${\displaystyle d_{\lambda \mu }=c_{\kappa }(d_{\lambda \kappa }\cdot d_{\kappa \mu })}$

(C7) Si , entonces ${\displaystyle \kappa \neq \lambda }$ ${\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 modela la cuantificación existencial sobre la variable en la fórmula mientras que el operador modela la igualdad de las variables y . Por lo tanto, reformulados utilizando notaciones lógicas estándar, los axiomas se leen como ${\displaystyle c_{\kappa }x}$ ${\displaystyle \kappa }$ ${\displaystyle x}$ ${\displaystyle d_{\kappa \lambda }}$ ${\displaystyle \kappa }$ ${\displaystyle \lambda }$

(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 es una variable distinta tanto de como de , entonces ${\displaystyle \kappa }$ ${\displaystyle \lambda }$ ${\displaystyle \mu }$ ${\displaystyle \lambda =\mu \iff \exists \kappa .(\lambda =\kappa \wedge \kappa =\mu )}$

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

Álgebras de conjuntos cilíndricos

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

Una representación de un álgebra cilíndrica es un isomorfismo de esa á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] [ ejemplo necesario ]} Es más fácil conectar la semántica de la lógica de predicados de primer orden con el álgebra de conjuntos cilíndricos. (Para más detalles, consulte § Lecturas adicionales).

Generalizaciones

Las álgebras cilíndricas se han generalizado al caso de la lógica multiordenada (Caleiro y Gonçalves 2006), lo que permite una mejor modelización de la dualidad entre fórmulas y términos de primer orden.

Relación con el álgebra booleana monádica

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

${\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 verse como una restricción del álgebra cilíndrica al caso de una variable.

Véase también

• 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 relación (RA)
• Álgebra poliádica
• Descomposición algebraica cilíndrica

Notas

1. Hirsch y Hodkinson p167, Definición 5.16
2. Hirsch y Hodkinson pág. 168

Referencias

• 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. Holanda Septentrional. ISBN 978-0-7204-2043-2 . 
• Leon Henkin, J. Donald Monk y Alfred Tarski (1985) Álgebras cilíndricas, parte II . Holanda Septentrional.
• Robin Hirsch e Ian Hodkinson (2002) Álgebras de relación por juegos Estudios de lógica y fundamentos de las matemáticas, Holanda Septentrional
• Carlos Caleiro, Ricardo Gonçalves (2006). "Sobre la algebrización de lógicas de orden múltiple" (PDF) . En J. Fiadeiro y P.-Y. Schobbens (ed.). Proc. 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.

Lectura adicional

• Imieliński, T. ; Lipski, W. (1984). "El modelo relacional de datos y álgebras cilíndricas". Revista de Ciencias de la Computación y de Sistemas . 28 : 80–102. doi : 10.1016/0022-0000(84)90077-1 .

Enlaces externos

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