Algèbre de Lindenbaum

L'algèbre de Lindenbaum d'une théorie est l'ensemble des classes d'équivalence de ses théorèmes. Munie des conjonction, disjonction et négation (qui sont compatibles avec l'équivalence logique), c'est une algèbre de Boole. Elle a été construite par Adolf Lindenbaum et Alfred Tarski en 1935.

Sommaire 1 Deux façons de voir les algèbres de Boole 1.1 Comme un anneau unitaire 1.2 Comme un treillis (ensemble ordonné) 2 Implication et relation d'ordre 2.1 L'implication comme relation 2.2 L'implication comme proposition 2.3 Les paradoxes de l'implication formelle 3 Propriétés de l'algèbre de Lindenbaum 3.1 Cas fini 3.2 Cas infini 3.3 Théorèmes 3.3.1 Théorème de Stone 3.3.2 Théorème de compacité 3.3.3 Théorème de complétude 3.3.4 Modèles non standard 4 Voir aussi 5 Notes et références 6 Bibliographie

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

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

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

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

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

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

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 Lindebaum, 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 Lindebaum, est 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.

Une partie du graphe de l'algèbre de Boole correspondante est représentée dans ce diagramme de Hasse:

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 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). Ci-dessous 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 cette version 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 (ci-dessus, 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

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.

Ce qui permet de dessiner des algèbres de Lindenbaum.

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

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

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 (ou ouvermés puisqu'ils 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.

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

• Algèbre de Boole
• ensemble de Cantor
• ensemble de Julia
• analyse non standard

Notes et références

Bibliographie

• George Boole, an investigation of the laws of thought, 1854
• (en) G. E. Hugues et M. J. Creswell, An introduction to Modal Logic, Londres, Methuen, 1968 (ISBN 978-0-416-29460-6) .
• (en) J. L. Bell et A. B. Slomson, Models and Ultraproducts, an introduction, Mineola, Dover publications, 2006, poche (ISBN 978-0-486-44979-1) .

• Portail des mathématiques
• Portail de la logique