Algèbre de Boole (structure)

Si 0 = 1 l'algèbre de Boole possède un seul élément, elle est dite dégénérée[6], ou triviale.

Étant donné une expression booléenne écrite avec les seules constantes et opérations de treillis algébrique (0, 1, ∧, ∨, ( )'), le dual de cette expression est celle obtenue en échangeant la borne supérieure ∨ et la borne inférieure ∧ d'une part, 0 et 1 d'autre part. Par exemple, voici l'expression de l'addition des anneaux de Boole (différence symétrique) et son expression duale :

le dual de ( a ∧ b' ) ∨ ( a' ∧ b ) est ( a ∨ b' ) ∧ ( a' ∨ b )

Cette définition se généralise aux énoncés, par substitution. Pour la seconde définition comme treillis algébrique, les axiomes d'algèbre de Boole sont présentés par paire, l'un des axiomes étant l'énoncé dual de l'autre. Par conséquent, à tout théorème des algèbres de Boole énoncé dans ce langage correspond un théorème dual : c'est le principe de dualité pour les algèbres de Boole.

Par exemple, les lois d'absorption sont duales l'une de l'autre : il suffit donc d'en démontrer une, et on déduit que l'autre est un théorème par dualité.

La dualité transforme l'ordre en son ordre réciproque : la forme duale de a ≤ b (a ∧ b = a) est a ≥ b (a ∨ b = a).

On vérifie que la duale d'une expression booléenne f(p₁, ... , p_n) est (f(p’₁, ... , p’_n))'.

Une sous-algèbre de Boole est un sous-anneau de l'algèbre de Boole en tant qu'anneau unitaire, c'est-à-dire (dans ce cas particulier) un sous-ensemble stable par addition, multiplication et ayant même élément neutre multiplicatif. On montre que les sous-algèbres de Boole sont les sous-ensembles des algèbres de Boole contenant 0 et 1, stables par borne supérieure, borne inférieure et complémentaire (le fait que la sous-algèbre possède, en tant que sous-anneau, le même neutre multiplicatif est indispensable pour que la stabilité par passage au complément soit assurée). Pour vérifier qu'un sous-ensemble d'une algèbre de Boole est une sous-algèbre, il suffit de vérifier la stabilité par complément, par l'une des deux opérations ∧, ∨ et que 0 ou 1 appartient au sous-ensemble.

Un exemple de sous-algèbre de Boole de l'ensemble des parties d'un ensemble infini est l'ensemble des parties finies et cofinies (c'est-à-dire de complémentaire fini) de ce même ensemble.

Si F est un sous-ensemble strict de E, l'ensemble des parties de F est une algèbre de Boole qui est un sous-ensemble de l'ensemble des parties de E, mais qui n'est pas une sous-algèbre de Boole car les éléments maximaux (E et F) ne sont pas les mêmes, de même que les compléments.

Les morphismes d'algèbres de Boole sont les morphismes d'anneaux (unitaires) usuels pour la structure d'anneau de Boole.

De façon équivalente, ce sont les morphismes de treillis qui passent au complément (il suffit alors de vérifier que soit les bornes supérieures soit les bornes inférieures sont conservées par les lois de De Morgan).

Tout sous-ensemble fini d'une algèbre de Boole possède une borne supérieure et une borne inférieure.

Une algèbre de Boole est dite complète si c'est un treillis complet, c'est-à-dire si tous ses sous-ensembles (finis ou infinis) ont une borne supérieure et une borne inférieure (en fait l'une des deux hypothèses suffit).

Exemples et contre-exemples :

• toute algèbre de Boole finie est évidemment complète ;
• l'algèbre de Boole des parties d'un ensemble est complète : toute famille de sous-ensembles possède une borne supérieure, qui est la réunion de ces sous-ensembles, et une borne inférieure, qui est l'intersection de ces sous-ensembles ;
• l'algèbre de Boole des parties finies ou cofinies d'un ensemble infini n'est pas complète ;
• l'algèbre de Lindenbaum du calcul propositionnel sur une infinité de variables non plus.
• Toute algèbre de Boole A est la sous-algèbre d'une algèbre de Boole B complète, telle que tout élément de B soit la borne supérieure d'une partie de A. B s'appelle le complété de A. Il est unique à isomorphisme près.

Dans une algèbre de Boole, la notion d'atome est celle qui correspond aux singletons dans l'algèbre de Boole des parties d'un ensemble. Une algèbre de Boole n'a cependant pas nécessairement d'atomes.

Les idéaux d'une algèbre de Boole sont les idéaux de l'algèbre en tant qu'anneau commutatif. La stabilité de l'idéal par multiplication par un élément quelconque de l'algèbre a pour conséquence qu'un idéal est une section initiale de la structure ordonnée. On peut caractériser les idéaux en termes de treillis ; le sous-ensemble I de E est un idéal de l'algèbre de Boole (E, ≤, ∧, ∨, 0, 1) quand il vérifie :

• 0 ∈ I
• ∀ x, y ∈ I x ∨ y ∈ I ;
• ∀ x ∈ I ∀ y∈ E (y ≤ x ⇒ y ∈ I).

Un idéal propre est un idéal différent de l'algèbre tout entière, nécessairement il ne contient pas l'élément maximal 1. Il ne peut donc contenir un élément x et son complément 1 + x.

La notion duale d'idéal propre est celle de filtre : un sous-ensemble de l'algèbre est un filtre si l'ensemble de ses compléments est un idéal. Plus directement le sous-ensemble F de E est un filtre de l'algèbre de Boole (E, ≤, ∧, ∨, 0, 1) quand il vérifie :

• 1 ∈ F et 0 ∉ F ;
• ∀ x, y ∈ F x ∧ y ∈ F ;
• ∀ x ∈ F ∀ y ∈ E (y ≥ x ⇒ y ∈ F).

L'application qui à un élément x associe son complément x' établit une bijection entre les filtres et les idéaux.

Un idéal maximal est un idéal maximal au sens de l'inclusion parmi les idéaux propres. La notion duale est celle d'ultrafiltre : un ultrafiltre est un filtre maximal au sens de l'inclusion, et c'est aussi l'ensemble des compléments d'un idéal maximal.

Le théorème de l'idéal maximal, ou théorème de Krull, énonce que tout idéal est inclus dans un idéal maximal. Dans le cas des algèbres de Boole il donne par dualité le théorème de l'ultrafiltre : tout filtre est inclus dans un ultrafiltre.
Cependant toute la force de l'axiome du choix — équivalent au théorème de Krull modulo ZF — n'est pas nécessaire pour prouver ce résultat ; en effet dans un anneau de Boole les notions d'idéal maximal et d'idéal premier coïncident. (Si ${\displaystyle A}$ est un anneau de Boole et ${\displaystyle I\subset A}$ un idéal non maximal il existe un idéal ${\displaystyle J}$ tel que ${\displaystyle I\subsetneq J\subsetneq A}$. La seconde inclusion implique que ${\displaystyle 1\notin J}$, et la première l'existence d'un élément ${\displaystyle x\in J\smallsetminus I}$. Ni ${\displaystyle x}$ ni ${\displaystyle 1+x}$ n'est élément de ${\displaystyle I}$ mais leur produit est nul : ${\displaystyle I}$ n'est donc pas premier.)
Ainsi le théorème de l'ultrafiltre (tout filtre est inclus dans un ultrafiltre) est-il un théorème de ZF + « tout idéal propre d'une algèbre de Boole est inclus dans un idéal premier » ; or il a été démontré que cette dernière théorie est strictement plus faible que ZFC[8].

Le quotient d'une algèbre de Boole par un idéal maximal (resp. premier) est le corps à deux éléments ${\displaystyle \mathbb {F} _{2}=\{0,1\}}$, seul anneau de Boole qui soit un corps (resp. un anneau intègre), le morphisme canonique associé est donc à valeurs dans {0, 1}.

De façon générale, dans une algèbre de Boole donnée, il est équivalent de se donner un idéal maximal, un ultrafiltre ou un morphisme non nul de cette algèbre de Boole dans {0,1}, le noyau d'un tel morphisme étant un idéal maximal, et l'ensemble des éléments de valeur 1 par ce morphisme un ultrafiltre.

On a vu qu'une algèbre de Boole finie est isomorphe à l'ensemble des parties d'un ensemble, en l'occurrence celui de ses atomes. Le théorème de représentation de Stone permet de généraliser ce résultat à une algèbre de Boole quelconque, au sens où dans le cas général, une algèbre de Boole est isomorphe à une sous-algèbre de l'ensemble des parties d'un ensemble.

Il est bien nécessaire de considérer des sous-algèbres : l'algèbre de Lindebaum du calcul propositionnel sur une infinité de variables propositionnelles, ou de façon isomorphe, l'algèbre de Boole librement engendrée par une infinité d'éléments, n'est pas atomique (voir ci-dessus), donc ne peut être isomorphe à l'ensemble des parties d'un ensemble.

Suivant une démarche commune en théorie des anneaux, l'ensemble en question peut être choisi comme l'ensemble des idéaux maximaux de l'algèbre de Boole A, ou, dans le cas des algèbres de Boole, comme l'ensemble S(A) des homorphismes de cette algèbre dans {0,1}, appelé espace de Stone de A. On vérifie alors que l'application suivante est un morphisme injectif de A dans l'ensemble 𝒫(S(A)) des parties de l'espace de Stone[9] :

Lorsqu'on considère S(A) comme une partie de 2^A, ensemble des fonctions de A dans {0,1} muni de la topologie produit, S(A) est un espace de Stone, c'est-à-dire un espace compact totalement discontinu. Il admet pour base d'ouverts ses parties ouvertes-fermées (clopen). L'image du morphisme ${\displaystyle \varphi }$ est alors exactement l'ensemble des ouverts-fermés de S(A).

Réciproquement, si X est un espace de Stone, alors l'ensemble de ses ouverts-fermés muni des opérations ensemblistes usuelles constitue une algèbre de Boole.

Par cette double correspondance, le théorème de représentation de Stone établit fonctoriellement une équivalence entre la catégorie des algèbres de Boole et celle des espaces de Stone.