Algèbre de Lindenbaum

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L'algèbre de Lindenbaum d'une théorie est l'ensemble des énoncés du langage de celle-ci pris à équivalence près démontrée dans cette théorie, et munie des conjonction, disjonction et négation (qui sont compatibles avec l'équivalence). C'est une algèbre de Boole. 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 donc par quotient une relation d'ordre sur l'algèbre de Lindenbaum qui est celle associée à la structure d'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[modifier | modifier le code]

Il y a deux manières de définir une algèbre de Boole, la définition algébrique (comme un anneau unitaire) 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é) 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[modifier | modifier le code]

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

Comme un treillis (ensemble ordonné)[modifier | modifier le code]

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; ce n'est pas un hasard, puisque 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é, mais comment peut-on comparer, même partiellement, des propositions? Par l'implication (logique) !

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

L'idée de l'algèbre de Lindenbaum revient à considérer comme égales deux propositions logiquement équivalentes, ce qui fait que l'implication 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[modifier | modifier le code]

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.

L'implication comme relation[modifier | modifier le code]

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 ⇔ a × b = a[3]. Ce qui revient à dire que p ⇒ q est vrai 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) et n'est pas un ensemble.

L'implication comme proposition[modifier | modifier le code]

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 d'ordre ! 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. On peut comparer ces deux "définitions" de l'implication comme deux points de vue différents, l'un déclaratif (l'implication propositionnelle), l'autre procédural (la relation d'ordre, qui ne dit pas ce qu'est une implication, mais comment on s'en sert).

En logique floue cependant, il y a une différence entre les deux points de vue, l'implication n'étant pas une proposition floue mais une relation floue entre propositions floues. Il n'y a d'ailleurs pas d'algèbre de Lindenbaum en logique floue.

Les paradoxes de l'implication formelle[modifier | modifier le code]

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 enlève leur caractère paradoxal à ces propriétés, en leur enlevant toute signification :

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

Propriétés de l'algèbre de Lindenbaum[modifier | modifier le code]

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[modifier | modifier le code]

4-sided dice 250.jpg

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[modifier | modifier le code]

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.

Théorèmes[modifier | modifier le code]

La topologie de Stone admet pour bases d'ouverts (fermés) l'ensemble des ultrafiltres de l'algèbre de Lindenbaum.

Théorème de Stone[modifier | modifier le code]

Plus précisément, l'espace de Stone d'une algèbre de Boole (en) 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'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, à 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é[modifier | modifier le code]

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[modifier | modifier le code]

Et comme l'algèbre de Lindenbaum est un espace compact, il en résulte que c'est un espace de Baire. Helena Rasiowa (en) et Roman Sikorski (en) en ont déduit une démonstration topologique du théorème de complétude.

Modèles non standard[modifier | modifier le code]

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)

Notes et références[modifier | modifier le code]

  1. (en) George Boole, An Investigation of the Laws of Thought (en),‎ 1854 (lire en ligne)
  2. Boole 1854, chap. 18
  3. (en) G. E. Hughes (en) et M. J. Creswell (de), An introduction to Modal Logic, Londres, Methuen,‎ 1968 (ISBN 978-0-416-29460-6), chap. 17
  4. Hughes et Creswell 1968, Appendix 2
  5. (en) John L. Bell (en) et Alan B. Slomson, Models and Ultraproducts, an Introduction, Mineola, Dover,‎ 2006, poche (ISBN 978-0-486-44979-1), chap. 0

Voir aussi[modifier | modifier le code]

Article connexe[modifier | modifier le code]

Type (théorie des modèles)

Bibliographie[modifier | modifier le code]

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