Algèbre de Lindenbaum

L'algèbre de Lindenbaumd'une théorie mathématique est l'ensemble des énoncés du langage de celle-ci modulo la relation d'équivalencesuivante: deux énoncésAetBsont dans la même classe d'équivalence s'il est possible de démontrer dans la théorie queAa pour conséquenceBet queBa pour conséquenceA. La relation de conséquence logique sur les énoncés, qui est compatible avec la relation d'équivalence, induit par quotient unerelation d'ordresur l'algèbre de Lindenbaum.
Lorsque la théorie est celle ducalcul propositionnelenlogique classique, l'algèbre de Lindenbaum, munie desconjonction,disjonctionetnégation(qui sont compatibles avec l'équivalence) forme unealgèbre de Boole. Cette algèbre, parfois appelée égalementalgèbre de Lindenbaum-Tarski, a été introduite parAdolf LindenbaumetAlfred Tarskien 1935.
Il y a deux manières de définir unealgèbre de Boole, la définition algébrique (comme unanneau unitaireoù tout élément estidempotent) qui est plutôtsémantiqueen ce qu'elle met l'accent sur les opérations comme la conjonction et leur effet sur lesvaleurs de vérité, et la définitiontopologique(comme untreillis (ensemble ordonné)distributif borné complémenté) qui est plussyntaxiqueen ce qu'elle met l'accent sur la notion dedéduction. On peut voir la construction de l'algèbre de Lindenbaumcomme une tentative pour réconcilier ces deux aspects.
Dans son ouvrage fondateur,George Booleeffectue de véritables calculs algébriques sur les propositions, en notant additivement ladisjonction logiqueet multiplicativement laconjonction logique. De surcroît, il note la négation comme l'opposé : pour lui, l'algèbre des propositions est essentiellement un anneau doté de propriétés particulières (comme ladistributivitéde l'addition par rapport à la multiplication).
Cette façon de voir les algèbres de Boole est fondamentale en théorie des ensembles, et notamment enthéorie des probabilitéstelle qu'elle a été axiomatisée parKolmogorov, l'intersection d'évènements correspondant d'ailleurs à la conjonction des propositions qu'ils représentent (voir plus bas). Il est d'ailleurs significatif que
Enlogique floueen effet, la probabilité est une manière parmi d'autres, pour calculer les valeurs de vérité. Cette interprétation booléenne des probabilités est déjà présente chez Booleavec une traduction dutiers exclupar le fait que la somme des probabilités de deux évènements contraires vaut 1.
Dans lalogique propositionnellemoderne, la notation "∧" pour la conjonction est la même que celle utilisée enarithmétiquepour désigner lePGCD. Dans les deux cas, il s'agit d'uneborne inférieurepour unerelation d'ordrepartiel (de même, la notation "∨" est commune à la disjonction et auPPCM). En arithmétique, la relation d'ordre partiel est ladivisibilité. En logique propositionnelle, la relation d'ordre partiel entre deux propositionspetqest larelation de déduction, notéep⊢qce qui revient à affirmer que l'implicationentre ces deux propositions est vraie, soit ⊢p ⇒ q.
Il s'agit d'une relation depréordre. En effet :
L'idée de l'algèbre de Lindenbaumrevient à considérer commeégalesdeux propositions logiquement équivalentes, ce qui fait que la relation de déduction devient une vraie relation d'ordre, non pas entre propositions, mais entre classes d'équivalences : l'algèbre de Lindenbaum est l'ensemble quotientde l'ensemble des propositions par la relation d'équivalence.
Lemodus ponenspeut alors être interprété comme une interdiction de remonter le courant : en suivant les flèches des implications, on se dirige vers des propositions qui sont au moins aussi vraies que celles dont on part. Si on admet que lesaxiomessont vrais, ce qu'on en déduit ne peut alors qu'être vrai aussi.
Dans une algèbre de Boole (l'algèbre de Lindenbaum en est une), la définition de la relation d'ordre à partir de la borne inférieure esta ≤ bsi et seulement sia×b=a. Ce qui revient à dire quep⇒qest vrai si et seulement sip∧q⇔pl'est, ou encorep⊢qsi et seulement sip∧q≡p. Il s'agit d'une relation entre propositions, donc d'un objet de nature différente des propositions elles-mêmes. Par exemple, dans l'algèbre de Boole des parties d'un ensemble, la relation d'ordre est l'inclusion (voir plus bas), une relation entre deux ensembles (et non un ensemble).
En calcul propositionnel, la propositionp ⇒ qest définie comme étant la proposition¬p ∨ q: il s'agit donc d'une proposition, et pas d'une relation ! Mais si on établit la table de vérité dep ⇒ q, on trouve lafonction indicatricedugraphe orientéde la relation d'ordre précédente.
Lorsque C. I. Lewis a inventé lalogique modale, c'était pour tenter d'échapper à ce qu'il appelait lesparadoxes de l'implication formelle:
L'interprétation de l'implication comme une relation d'ordre permise par l'algèbre de Lindenbaum lève l'apparent "paradoxe", en donnant une signification algébrique à l'implication. En particulier, on peut distinguer :
On appelleatomed'une algèbre de Boole, tout élément de celle-ci tel que seul zéro est plus petit que lui. Dans le cas de l'algèbre de Boole des parties d'un ensemble, les atomes sont les singletons.
Dans une expérience probabiliste sur un univers fini, le nombre de variables propositionnelles est fini, et correspond aux atomes. Par exemple, si on lance undé à quatre faces, les atomes sont au nombre de 4 :
La première de ces propositions est représentée enthéorie des probabilitéspar l'ensemble{1}. Et l'évènement{2,4}correspondant à un résultat pair s'écrit par la proposition non atomique2∨4. De même, l'évènement impossible{}(ou ∅) correspond à une antilogie et l'évènement certain{1,2,3,4}correspond à une tautologie.
Une partie du graphe de l'algèbre de Boole correspondante est représentée dans lediagramme de Hassede la figure 1.
L'algèbre de Boole n'est pas représentée en entier parce que par exemple,4⇒2∨3∨4(si le dé est tombé sur 4 alors il est tombé sur plus que 1) bien qu'aucune flèche n'aille de{4}à{2,3,4}. Cependant il y a une flèche allant de{4}à{2,4}et une autre allant de{2,4}à{2,3,4}. On peut considérer ces deux flèches comme une démonstration de la proposition « si le dé est tombé sur 4 alors il est tombé sur plus que 1 », qui en français peut se rédiger ainsi :
On remarque (figure 2) qu'il y a d'autres parcours fléchés allant de{4}à{2,3,4}, par exemple celui tout à droite, qui se résume à « si le dé est tombé sur 4 il est tombé sur plus que 2, donc a fortiori plus que 1 ». Le fait que le faux implique le vrai est visualisé par la position de l'ensemble vide tout en bas du diagramme (mais aussi par la position de l'univers tout en haut). Dans la figure 2, on a colorié en vert tous les théorèmes qu'on peut déduire de « le dé est tombé sur 1 ».
Le fait que la relation d'ordre n'est pas totale empêche de réduire ce diagramme à des points alignés, mais sur la figure 3 où les ensembles sont représentés par leur fonction indicatrice, on reconnaît untesseract. Plus généralement, une algèbre de Boole finie a toujours un nombre d'éléments qui est une puissance de 2 (ici, 16), et le diagramme de Hasse est un hypercube de dimension finie. Pour le calcul propositionnel classique à une infinité de variables propositionnelles, on peut imaginer l'algèbre de Lindenbaum comme un hypercube de dimension infinie.
Dans ce cas l'algèbre de Lindenbaum n'a pas d'atomes, et topologiquement c'est unespace de Cantor. Or ce genre d'espaces sont toushoméomorphesentre eux, et une algèbre de Lindenbaum est, topologiquement, identique à l'ensemble de Cantor.
L'algèbre de Lindenbaumd'une théorie ducalcul des prédicatsest aussi un espace de Cantor. Dans ce cas la borne inférieure de la famille engendrée par un prédicat ayant une variable libre est obtenue en le précédant d'unquantificateur universelet sa borne supérieure, en le précédant d'unquantificateur existentiel:
[∀x, P(x)] ⇒ P(x) ⇒ [∃ x, P(x)]
L'ultrafiltrereprésenté en vert ci-dessus (engendré par un atome) admet une généralisation dans l'algèbre de Lindenbaum du calcul des prédicats. Cette notion d'ultrafiltres permet de définir une topologie sur l'algèbre de Lindenbaum, dans laquelle tout ouvert est fermé et réciproquement.
Plus précisément, l'espace de Stone d'une algèbre de Booleest l'ensemble de ses ultrafiltres, et c'est sur cet espace queMarshall Stonea défini satopologieadmettant pourbase d'ouverts(qui sont fermés aussi) les ensembles d'ultrafiltres contenant un élément de l'algèbre de Boole. L'ensemble des ouverts-fermés de l'espace de Stone, muni de l'intersection et de la réunion, est une algèbre de Boole.
Il en résulte que l'algèbre de Lindenbaum est unespace compact(comme on le voit sur les figures ci-dessus).
Alors de tout recouvrement de l'algèbre de Lindenbaum par des fermés (c'est-à-dire par des ouverts) on peut extraire un recouvrement fini : c'est lethéorème de compacitéde la logique des prédicats.
Et comme l'algèbre de Lindenbaum est unespace compact, il en résulte que c'est unespace de Baire.Helena RasiowaetRoman Sikorskien ont déduit une démonstration topologique duthéorème de complétude.
Les constructions d'ultraproduits dans les algèbres de Lindenbaum de l'arithmétique et de l'analyse ont respectivement mené à la découverte
Type (théorie des modèles)
(en)Peter Johnstone,Stone Spaces,CUP,1982, 370p.(ISBN978-0-521-23893-9)