Algèbre de Lindenbaum

L'algèbre de Lindenbaum d'une théorie mathématique est l'ensemble des énoncés du langage de celle-ci modulo la relation d'équivalence suivante: deux énoncés A et B sont dans la même classe d'équivalence s'il est possible de démontrer dans la théorie que A a pour conséquence B et que B a pour conséquence A. La relation de conséquence logique sur les énoncés, qui est compatible avec la relation d'équivalence, induit par quotient une relation d'ordre sur l'algèbre de Lindenbaum.

Lorsque la théorie est celle du calcul propositionnel en logique classique, l'algèbre de Lindenbaum, munie des conjonction, disjonction et négation (qui sont compatibles avec l'équivalence) forme une algèbre de Boole. Cette algèbre, parfois appelée également algèbre de Lindenbaum-Tarski, a été introduite par Adolf Lindenbaum et Alfred Tarski en 1935.

Deux façons de voir les algèbres de Boole

Il y a deux manières de définir une algèbre de Boole, la définition algébrique (comme un anneau unitaire où tout élément est idempotent) qui est plutôt sémantique en ce qu'elle met l'accent sur les opérations comme la conjonction et leur effet sur les valeurs de vérité, et la définition topologique (comme un treillis (ensemble ordonné) distributif borné complémenté) qui est plus syntaxique en ce qu'elle met l'accent sur la notion de déduction. On peut voir la construction de l'algèbre de Lindenbaum comme une tentative pour réconcilier ces deux aspects.

Comme un anneau unitaire

Dans son ouvrage fondateur, 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 avec une traduction du tiers exclu par le fait que la somme des probabilités de deux évènements contraires vaut 1.

Comme un treillis (ensemble ordonné)

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.

Implication et relation d'ordre

Le modus ponens peut 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 les axiomes sont vrais, ce qu'on en déduit ne peut alors qu'être vrai aussi.

Relation d'ordre, relation de déduction, et implication

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. 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).

L'implication comme proposition

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.

Les paradoxes de l'implication formelle

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 :

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.

Propriétés de l'algèbre de Lindenbaum

On appelle atome d'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.

Cas fini

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.

Cas infini

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

Théorèmes

Théorème de Stone

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.

Théorème — L'algèbre de Lindenbaum est isomorphe, en tant qu'algèbre de Boole (et comme toute algèbre de Boole), à l'algèbre de Boole des ouverts-fermés de son espace de Stone.

Il en résulte que l'algèbre de Lindenbaum est un espace compact (comme on le voit sur les figures ci-dessus).

Théorème de compacité

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.

Théorème de complétude

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.

Modèles non standard

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)

Voir aussi

Article connexe

Type (théorie des modèles)

Bibliographie

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