Preuve sympa sur les algèbres de Boole

Maxtimax · July 2018

Il est connu que les algèbres de Boole sont localement finies, i.e. si une algèbre de Boole est finiment générée, alors elle est finie.

Cela découle immédiatement (et est équivalent) du fait que les algèbres de Boole libres sur $n$ éléments sont finies.
Il existe beaucoup de preuves de ce fait mais je ne les ai jamais vraiment trouvées agréables : en voici une que je viens de découvrir et que je partage parce qu'elle est agréable justement. Elle est d'autant plus agréable qu'elle donne automatiquement le cardinal de l'algèbre e Boole libre sur $n$ éléments.

Lemme : Soit $B$ une algèbre de Boole infinie. Alors $B$ a une infinité d'ultrafiltres.
Preuve (j'avoue que je viens de la trouver en écrivant celle-là, je l'aime beaucoup aussi) : $B$ est une algèbre de Boole, donc elle est isomorphe à l'algèbre des ouverts-fermés de son espace de Stone. Cela implique que ledit espace de Stone a une infinité d'ouverts-fermés, donc une infinité de points: ces points sont des ultrafiltres, c'est tout ce qu'il fallait.

Preuve du résultat : Soit $B_n$ l'algèbre de Boole libre sur $n$ éléments. Alors, en notant $\simeq$ la relation "est en bijection avec", et $\mathbf{Bool}(A,B)$ les morphismes de $A$ vers $B$, et finalement $\mathrm{Hom}(A,B)$ les applications de $A$ vers $B$, $\mathbf{2}$ l'algèbre de Boole à $2$ éléments, on a $\{u\subset B_n \mid u$ ultrafiltre sur $B_n\} \simeq \mathbf{Bool}(B_n,\mathbf{2}) \simeq \mathrm{Hom}(n,2) = 2^n$ (le deuxième isomorphisme venant de la liberté de $B_n$)

Donc il n'y a qu'un nombre fini d'ultrafiltres sur $B_n$, qui est donc finie par le lemme.

Corollaire : $|B_n| = 2^{2^n}$.
Preuve: $B_n$ est finie, donc est isomorphe à $\mathcal{P}(A_n)$, où $A_n$ est l'ensemble des atomes de $B_n$. Donc $B_n$ a $|A_n|$ ultrafiltres; donc $|A_n| = 2^n$ donc $|B_n| = 2^{2^n}$.

GaBuZoMeu · July 2018

Curieux. Je ne connais pas les preuves que tu évoques, mais j'en vois une toute bête : utiliser la forme normale disjonctive pour réaliser immédiatement que l'algèbre de Boole libre sur $n$ générateurs $p_1,\ldots,p_n$ est isomorphe à l'algèbre de Boole des parties de l'ensemble à $2^n$ éléments des $q_1\wedge q_2\wedge\cdots \wedge q_n$ où $q_i$ est soit $p_i$ soit $\neg p_i$.

christophe c · July 2018

@max: sur le plan des preuves humaines je partage l'avis de GBZM. J'essaie de comprendre ton goût pour la preuve que tu donnes. Et j'exclus pour le fun que tu veuilles faire de la pub aux notations catégoriques (qui pour moi sont irrémédiablement illisibles mais dont je respecte la capacité d'autres de les lire): cherches-tu tout simplement à produire une preuve qui serait acceptée par un logiciel arbitre? :-S

Dans ce cas oui les trois petits points etc doivent être remplacés par des outils notationnels froids.

C'est ça ton paradigme? (Attention de ne pas te transformer en Terminator :-D )

christophe c · July 2018

Sinon le "vrai truc" derrière ces finitudes c'est le fait que dans un anneau noetherien il existe une suite finie d'idéaux premiers dont le produit est nul. Or un anneau de Boole à des idéaux premiers très contraints , et d'ailleurs pas besoin d'être de Boole , suffit que chaque élément soit multiple de don carré (pas besoin de lui être égal).

Maxtimax · July 2018

@GBZM : en fait je n'aime pas (mais c'est psychologique) la forme normale disjonctive, ni la preuve de son existence : peu importe la raison mais je trouve ma preuve plus agréable que celle que tu proposes (même si la tienne a l'avantage d'être purement finitiste)

@christophe : il y a vraiment très peu de notations catégoriques : seulement Bool et Hom (pour lesquelles je ferais bien de la pub mais ce n'est pas l'objet ici)
Si vous ne partagez pas mon attrait pour cette preuve, c'est qu'il doit être entièrement psychologique, esthétique (je ne m'intéresse pas -encore- aux logiciels arbitres; si tu penses que ma preuve serait mieux avalée par un tel logiciel, tant mieux, mais ce n'était pas le but)

christophe c · July 2018

Bon méfie toi tu deviens trop fort!!! Tz preuve est bien trop difficile pour le Pékin lambda. :-D

Je la.critique plus précisément si tu veix:

1) tu parles d'ultrzfiltred et d'espaces de Stone
2) tu considères évide T qu'un ultrafiltres est un morphisme
3) le coup de la liberté finale je n'ai que peu compris.

Si tu veux une preuve sans forme normale rappelle toi que "fini" n'est pas un notion absolue et dépend de l'univers. Il y a pas de vrai IN.

DONC récurrence obligatoire!!!!!!

Et pour les algèbres de Boole ça a la chance de marcher directement via , prenant un generzteur à la fonction x|

> (a et x) qui te donne une algèbre de Boole AVEC UN GENERZTEUR DE MOINS do t le 1 est l'ancien à. tu devienes la suite

Maxtimax · July 2018

@christophe: non pas trop fort du tout; peut-être que la preuve utilise des bazookas pour une mouche :-D
Je suis d'accord pour 1), pour 2) bah c'est la base des ultrafiltres, et pour 3) c'est tout bête : $B_n$ est librement générée par $n$ éléments , donc un morphisme $B_n \to \mathbf{2}$ est entièrement déterminé par les images de ces générateurs, et toute fonction de ces générateurs dans $2$ donne un morphisme : c'est la définition d'algèbre libre !

La seule récurrence de ma preuve c'est pour dire "$n$ fini implique $2^n$ fini" (et je l'utilise ! à deux endroits !)
Mais comme je te le dis, je sais qu'il y a plein d'autres preuves, et beaucoup utilisent sans doute d'autres formes de récurrence (celle par la forme normale disjonctive par exemple )

christophe c · July 2018

Je critiquais pour le plaisir de te donner à moudre du grain je pense que tu l'avais compris. J'en profite pour signaler une faute que j'ai faite (je modifieraisi plus tard): les anneaux noetheriens dont tout élément est multiple de don carré n'ont bien évidemment* qu'un nombre fini d'idéaux voulais je dire. Ce sont les produits finis de corps. Cas particulier: Boole (produit fini du corps F2 :-D )

* Adverbe à accorder avec voulais je

Foys · August 2018

$\newcommand{\F}{\mathbf F}$ Une autre idée (qui est peu ou prou l'idée de christophe c plus haut: c'est basé sur des résultats d'algèbre commutative; concrètement il suffit de prendre la preuve de ce qu'une algèbre de Boole se plonge dans $\F_2^I$ pour un certain $I$ et faire les aménagements nécessaires).
Une algèbre de Boole est un anneau $A$ tel que pour tout $x\in A$, $x^2=x$ (il y a d'autres définitions équivalentes). Il est connu qu'alors $A$ est commutatif et de caractéristique $2$ (c'est donc une $\F_2$-algèbre).
Supposons que $A$ est engendrée par $x_1,...,x_n$. Alors (vu que $a\wedge b=ab$ et $a\vee b = a+b-ab $) $A=\F_2 [x_1,...,x_n]$. De plus $A$ est un anneau réduit (l'égalité $x^2=x$ pour tout $x$) et donc l'intersection des idéaux premiers de $A$ est égale à $\{0\}$. Mais un idéal premier d'une algèbre de Boole est toujours maximal (son quotient est une algèbre de Boole intègre: $\F_2$ est la seule possibilité). Bref on se retrouve avec un morphisme injectif $A \to \F_2^{spec(A)}$, $spec(A)$ étant l'ensemble des idéaux premiers (i.e. maximaux en l'espèce) de $A$. Mais cet ensemble est en bijection naturelle avec les morphismes d'anneaux non triviaux de $A$ vers $\F_2$ et leur ensemble est fini (puisque un tel morphisme ne dépend que des images des $x_1,..,x_n$).

Bref $A$ se plonge dans $\F_2^k$ pour un certain $k \in \N$.

Foys · August 2018

Le seul truc non trivial à connaître est que dans un anneau commutatif, l'ensemble des éléments nilpotents est l'intersection des idéaux premiers de l'anneau en question.

Foys · August 2018

Les ultrafiltres et les idéaux maximaux de ce genre d'anneau c'est un peu la même chose au fond.

La preuve par forme normale disjonctive à l'avantage de ne pas utiliser l'axiome du choix.
(c'est fastidieux mais sans difficulté: il suffit de transformer un terme en utiisant la distributivité de chacun des opérateurs $\wedge,\vee$ par rapport à l'autre).

Maxtimax · August 2018

@Foys : j'aime bien aussi. D'autant qu'en faisant attention aux détails, je pense que tu retrouves aussi le cardinal exact de $A$

Je suis d'accord pour l'avantage de la preuve par forme normale disjonctive, comme je l'ai dit c'est plutôt psychologique

christophe c · August 2018

De mon téléphone: je crois que j'ai compris ton aversion (légère). Je vais essayer de décrire un max fictif qui objecte:

1/ la noetherianite d'un AB n'est pas admise donc exit
2/ formes normales disjonctives: utilisation de "dots" donc exit
3/ les récurrences diverses et variées laissent souvent caché qu'il faut justifier qu'on peut exprimer (u et a) sous la forme de (v et a) avec v n'utilisant pas le generzteur a

4/ etc etc

Mais, sans te vexer, je crois que tu es choqué parce que tu commets l'erreur de vouloir courir deux lièvres à la fois avec polarités opposées.

La liberté et meme l'existence d'AB libre N'A AUCUN ROLE À JOUER dans la finitude des AB finiment générées. Et cette finitude se prouve de façon très simple. Et sans morphisme ultraftres ou koi ou kess .

Le cardinal de l'EVENTUELLE libre est UNE TOUTE ZUTRE affaire et on voit bien que tu as une addiction à viser le "2 en 1" car chaque fois tu mentionnes ton bonheur quand il est "obtenu"

Si F est un ensemble fini engendrant B (j'utilise les notations anneau de BOOLE ) et t va de F dans 2, je note t* la conjonction des x+t(x) quand x parcourt F. L'ensemble des disjonctions d'éléments de la forme t* EST UNE SOUS ALGÈBRE Boole contenant F et ça n'a rien ni de fastidieux ni de long ni de prerequis. Sa finitude résulte du fait que chaque t* n'a besoin d'apparaître qu'une fois. (Rien à prouver si d'zilleurs tu evoques des disjonctions D'ENDEMBLED et non de familles. Et c'est donc B tout entier

christophe c · August 2018

@max: je n'enai pas l'air comme ça, mais je suis un grand anxieux ! Tu n'es pas fâché ? Ça ne t'a pas dissuadé de poster des preuves que tu aimes bien nos réactions ? Sinon pardon si j'ai été indélicat c'était TOTALEMENT involontaire. C'est pour pimenter que nous avons commenté surtout "en attaque" ta preuve car les preuves c'est par essence fait pour ça : être attaquées. C'est anti-éthique de défendre une preuve.