Álgebra cilíndrica - Cylindric algebra

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 es 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 \ existe \ kappa. {\ mathit {falso}} \ iff {\ mathit {falso}}}$

(C2) ${\ Displaystyle x \ implica \ existe \ kappa .x}$

(C3) ${\ Displaystyle \ existe \ kappa. (x \ cuña \ existe \ kappa .y) \ iff (\ existe \ kappa .x) \ cuña (\ existe \ kappa .y)}$

(C4) ${\ Displaystyle \ existe \ kappa \ existe \ lambda .x \ iff \ existe \ lambda \ existe \ 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 \ existe \ kappa. (\ lambda = \ kappa \ wedge \ kappa = \ mu)}$

(C7) Si y son variables diferentes, entonces${\ Displaystyle \ kappa}$${\ Displaystyle \ lambda}$${\ Displaystyle \ existe \ kappa. (\ kappa = \ lambda \ cuña x) \ cuña \ existe \ kappa. (\ kappa = \ lambda \ cuña \ neg x) \ iff {\ mathit {falso}}}$

Á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 . 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 \ existe 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. 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 \ existe}$

${\ Displaystyle c _ {\ kappa} (x + y) = c _ {\ kappa} x + c _ {\ kappa} y}$

se convierte en el axioma

${\ Displaystyle \ existe (x + y) = \ existe x + \ existe y}$

del álgebra booleana monádica . El axioma (C4) desaparece. Por tanto, 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

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