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

(C7) Si $\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 {faux}}\Leftrightarrow {\mathit {faux}}$

(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 {vrai}}$

(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 {faux}}$

Voir aussi

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

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Cylindric algebra » (voir la liste des auteurs).
• 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.
• (en) Recent trends in algebraic development techniques : 18th International Workshop, WADT 2006, La Roche en Ardenne, Belgium, June 1-3, 2006, Revised Selected Papers, Springer, coll. « Lecture notes in computer science » (n^o 4409), 2007 (ISBN 978-3-540-71997-7, DOI 10.1007/978-3-540-71998-4_2, lire en ligne), « On the algebraization of many-sorted logics », p. 21-36