Algèbre cylindrique

En mathématiques, la notion d'algèbre cylindrique, inventée par Alfred Tarski, est survenue naturellement dans l'algébrisation de la logique du premier ordre équationnelle.

Définition d'une algèbre cylindrique

Une algèbre cylindrique de dimension $\alpha$ (où $\alpha$ est un nombre ordinal) est une structure algébrique $(A,+,\cdot ,-,0,1,c_{\kappa },d_{\kappa \lambda })_{\kappa ,\lambda <\alpha }$ tel que $(A,+,\cdot ,-,0,1)$ est une algèbre booléenne, $c_{\kappa }$ un opérateur unaire sur $A$ pour tout $\kappa$, et $d_{\kappa \lambda }$ un élément distingué de $A$ pour tout $\kappa$ et $\lambda$, de telle sorte que:

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

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

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

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

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

(C6) If $\kappa \notin \{\lambda ,\mu \}$, alors $d_{\lambda \mu }=c_{\kappa }(d_{\lambda \kappa }\cdot d_{\kappa \mu })$

(C7) If $\kappa \neq \lambda$, alors $c_{\kappa }(d_{\kappa \lambda }\cdot x)\cdot c_{\kappa }(d_{\kappa \lambda }\cdot -x)=0$

En supposant une présentation de la logique du premier ordre sans symboles de fonction, l'opérateur $c_{\kappa }x$ modélise quantification existentielle sur la variable $\kappa$ dans la formule $x$ tandis que l'opérateur $d_{\kappa \lambda }$ l'égalité des modèles des variables $\kappa$ et $\lambda$. Désormais, reformulé en utilisant les notations logiques standard, les axiomes peuvent se lire ainsi

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

(C2) $x\Rightarrow \exists \kappa .x$

(C3) $\exists \kappa .(x\wedge \exists \kappa .y)\Leftrightarrow (\exists \kappa .x)\wedge (\exists \kappa .y)$

(C4) $\exists \kappa \exists \lambda .x\Leftrightarrow \exists \lambda \exists \kappa .x$

(C5) $\kappa =\kappa \Leftrightarrow {\mathit {true}}$

(C6) Si $\kappa$ est une variable différente de $\lambda$ et $\mu$, alors $\lambda =\mu \Leftrightarrow \exists \kappa .(\lambda =\kappa \wedge \kappa =\mu )$

(C7) Si $\kappa$ et $\lambda$ sont différents entre elles, alors $\exists \kappa .(\kappa =\lambda \wedge x)\wedge \exists \kappa .(\kappa =\lambda \wedge \neg x)\Leftrightarrow {\mathit {false}}$

Voir aussi

• Logique algébrique abstraite
• Lambda calcul et logique combinatoire
• Logique algébrique

Références

• Leon Henkin, Monk, J.D., et Alfred Tarski (1971) Cylindric Algebras, Partie I. North-Holland. ISBN 978-0-7204-2043-2.
• -------- (1985) Cylindric Algebras, Partie II. North-Holland.
• Carlos Caleiro, Ricardo Gonçalves, Proc. 18th int. conf. on Recent trends in algebraic development techniques (WADT), vol. 4409, Springer, coll. « LNCS », 2006, 21-36 p. (ISBN 978-3-540-71997-7), « On the algebraization of many-sorted logics »