Álgebra cilíndrica

En matemáticas , la noción de álgebra cilíndrica , inventada por Alfred Tarski , surge naturalmente en la algebraización de la lógica de primer orden con igualdad . Esto es comparable al papel que juegan las álgebras de Boole para la lógica proposicional . De hecho, las álgebras cilíndricas son álgebras booleanas equipadas con 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 un álgebra cilíndrica

Un álgebra cilíndrica de dimensión (donde está cualquier número ordinal ) es una estructura algebraica tal que es un álgebra booleana , un operador unario activado para cada (llamado cilindrificación ) y un elemento distinguido de para cada y (llamado diagonal ), tal que lo siguiente tiene:${\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 . De ahora en adelante, reformulados usando 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 diferente de ambos y , 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 dimensión de conjuntos cilíndricos es una estructura algebraica tal que es un campo 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 , conjunto de complemento para 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 ese álgebra a un álgebra de conjuntos cilíndricos. No todo álgebra cilíndrica tiene una representación como álgebra de conjuntos cilíndricos. ^{[2] [Se necesita un ejemplo ]} 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 obtener más detalles, consulte el § Lectura adicional ).

Generalizaciones

Las álgebras cilíndricas se han generalizado al caso de la lógica de muchos ordenamientos (Caleiro y Gonçalves 2006), lo que permite un mejor modelado 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 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) desaparece. Así, el álgebra booleana monádica puede verse como una restricción del álgebra cilíndrica al caso de una variable.

Ver 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 álgebras cilíndricas.
• Álgebras de relaciones (RA)
• Álgebra poliadica
• Descomposición algebraica cilíndrica

Notas

1. Hirsch y Hodkinson p167, Definición 5.16
2. Hirsch y Hodkinson p168

Referencias

• Charles Pinter (1973). "Un álgebra simple de lógica de primer orden" . Diario de Notre Dame de lógica formal . XIV : 361–366.
• Leon Henkin , Monk, JD, y Alfred Tarski (1971) cilíndrico Álgebras, Parte I . Holanda Septentrional. ISBN 978-0-7204-2043-2 . 
• Leon Henkin, Monk, JD y Alfred Tarski (1985) Cylindric Algebras, Part II . Holanda Septentrional.
• Robin Hirsch e Ian Hodkinson (2002) Álgebras de relaciones por juegos Estudios en lógica y fundamentos de las matemáticas, Holanda del Norte
• Carlos Caleiro, Ricardo Gonçalves (2006). "Sobre la algebraización de lógicas muchas ordenadas" (PDF) . En J. Fiadeiro y P.-Y. Schobbens (ed.). Proc. XVIII int. conf. sobre Tendencias recientes en técnicas de desarrollo algebraico (WADT) . LNCS. 4409 . Saltador. págs. 21–36. ISBN 978-3-540-71997-7.

Otras lecturas

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

enlaces externos

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