Algèbre de Lindenbaum

Dans son ouvrage fondateur[1], George Boole effectue de véritables calculs algébriques sur les propositions, en notant additivement la disjonction logique et multiplicativement la conjonction 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 la distributivité 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 en théorie des probabilités telle qu'elle a été axiomatisée par Kolmogorov, 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

1. lorsque deux évènements sont incompatibles, la probabilité de leur réunion soit la somme de leurs probabilités ;
2. lorsque deux évènements sont indépendants, la probabilité de leur intersection soit le produit de leurs probabilités.

En logique floue en 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 Boole[2] avec une traduction du tiers exclu par le fait que la somme des probabilités de deux évènements contraires vaut 1.

Dans la logique propositionnelle moderne, la notation "∧" pour la conjonction est la même que celle utilisée en arithmétique pour désigner le PGCD. Dans les deux cas, il s'agit d'une borne inférieure pour une relation d'ordre partiel (de même, la notation "∨" est commune à la disjonction et au PPCM). En arithmétique, la relation d'ordre partiel est la divisibilité. En logique propositionnelle, la relation d'ordre partiel entre deux propositions p et q est la relation de déduction, notée p ⊢ q ce qui revient à affirmer que l'implication entre ces deux propositions est vraie, soit ⊢ p ⇒ q.

Il s'agit d'une relation de préordre. En effet :

1. p ⊢ p (réflexivité)
2. Si p ⊢ q et q ⊢ r alors p ⊢ r (transitivité)
3. Mais si p ⊢ q et q ⊢ p, on n'a pas nécessairement p = q (antisymétrie), seulement p ≡ q (soit ⊢ p ⇔ q).

L'idée de l'algèbre de Lindenbaum revient à considérer comme égales deux 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 quotient de l'ensemble des propositions par la relation d'équivalence.

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 est a ≤ b si et seulement si a × b = a[3]. Ce qui revient à dire que p ⇒ q est vrai si et seulement si p ∧ q ⇔ p l'est, ou encore p ⊢ q si et seulement si p ∧ 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 proposition p ⇒ q est 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é de p ⇒ q, on trouve la fonction indicatrice du graphe orienté de la relation d'ordre précédente.

Lorsque C. I. Lewis a inventé la logique modale, c'était pour tenter d'échapper à ce qu'il appelait les paradoxes de l'implication formelle[4] :

1. 2+2=5 implique 2+2=3 (le faux entraîne le faux)
2. 2+2=5 implique 2+2=4 (le faux entraîne le vrai)
3. 2+2=4 implique par deux points distincts passe une droite (le vrai entraîne le vrai, même lorsqu'il n'y a aucun rapport entre les deux propositions)

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 :

1. La classe des antilogies, qui est plus petite que tous les éléments de l'algèbre de Lindenbaum, et en particulier plus petite qu'elle-même;
2. La classe des tautologies, qui est plus grande que tous les éléments de l'algèbre de Lindenbaum, et en particulier plus grande qu'elle-même.

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 un dé à quatre faces, les atomes sont au nombre de 4 :

1. le dé tombe sur 1 ; on notera cette proposition 1 ;
2. le dé tombe sur 2 ; on notera cette proposition 2 ;
3. le dé tombe sur 3 ; on notera cette proposition 3 ;
4. le dé tombe sur 4 ; on notera cette proposition 4.

La première de ces propositions est représentée en théorie des probabilités par l'ensemble {1}. Et l'évènement {2,4} correspondant à un résultat pair s'écrit par la proposition non atomique 2∨4. De même, l'évènement impossible {} (ou ∅) correspond à une antilogie et l'évènement certain {1,2,3,4} correspond à une tautologie.

Fig. 1

Fig. 2

Fig. 3

Une partie du graphe de l'algèbre de Boole correspondante est représentée dans le diagramme de Hasse de 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 :

1. Si le dé est tombé sur 4 alors il est tombé sur un nombre pair ;
2. Or les nombres pairs de ce dé sont supérieurs à 1 ;
3. Donc si le dé est tombé sur 4 alors il est tombé sur plus que 1.

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 un tesseract. 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.

Cet ensemble de Julia est un exemple d'espace de Cantor.

Dans ce cas l'algèbre de Lindenbaum n'a pas d'atomes, et topologiquement c'est un espace de Cantor[5]. Or ce genre d'espaces sont tous homéomorphes entre eux, et une algèbre de Lindenbaum est, topologiquement, identique à l'ensemble de Cantor.

L'algèbre de Lindenbaum d'une théorie du calcul des prédicats est 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'un quantificateur universel et sa borne supérieure, en le précédant d'un quantificateur existentiel :

[∀x, P(x)] ⇒ P(x) ⇒ [∃ x, P(x)]

L'ultrafiltre repré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 Boole est l'ensemble de ses ultrafiltres, et c'est sur cet espace que Marshall Stone a défini sa topologie admettant pour base 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 un espace 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 le théorème de compacité de la logique des prédicats.

Et comme l'algèbre de Lindenbaum est un espace compact, il en résulte que c'est un espace de Baire. Helena Rasiowa et Roman Sikorski en ont déduit une démonstration topologique du thé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

1. de l'arithmétique non standard (Thoralf Skolem, 1922)
2. de l'analyse non standard (Abraham Robinson, 1961)

Type (théorie des modèles)

(en) Peter Johnstone (de), Stone Spaces, CUP, 1982, 370 p. (ISBN 978-0-521-23893-9)