Ultrafiltre
En mathématiques, et plus précisément en théorie des ensembles, un ultrafiltre sur un ensemble X est une collection de sous-ensembles de X qui est un filtre, et qui n'est pas contenue dans un filtre plus grand. On peut considérer un ultrafiltre comme étant une mesure (finiment additive), et alors tout sous-ensemble de X est, pour cette mesure, soit négligeable (de mesure 0), soit valant « presque tout » X (de mesure 1). Cette notion se généralise aux algèbres de Boole et aux ordres partiels, et a de nombreuses applications en théorie des modèles et en topologie.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/68/Filter_vs_ultrafilter.svg/220px-Filter_vs_ultrafilter.svg.png)
Définition
modifierÉtant donné un ensemble X, un ultrafiltre sur X est un ensemble U formé de sous-ensembles de X tel que :
- l'ensemble vide n'est pas un élément de U ;
- toute partie de X incluant un élément de U est aussi un élément de U ;
- L'intersection de deux éléments de U est également dans U ;
- si A est un sous-ensemble de X, alors A ou son complémentaire X\A est un élément de U.
Remarques :
- les axiomes 1 et 3 impliquent que A et X\A ne peuvent être tous les deux éléments de U ; le ou de l'axiome 4 est exclusif ;
- tout ultrafiltre sur X est un filtre sur X, c'est-à-dire qu'il vérifie les axiomes 1, 2 et 3 et qu'il est non vide (d'après l'axiome 4).
D'autres caractérisations des ultrafiltres sont données par le théorème suivant :
Pour tout filtre U sur X, les conditions suivantes sont équivalentes :
- U est un ultrafiltre sur X ;
- il n'y a pas de filtre sur X strictement plus fin que U, c'est-à-dire que pour tout filtre F sur X, U ⊂ F entraîne U = F[1] ;
- A∪B ∈ U entraîne A ∈ U ou B ∈ U[2].
Une autre façon d'envisager les ultrafiltres sur X est de définir une fonction m sur l'ensemble des parties de X en posant m(A) = 1 si A est un élément de U et m(A) = 0 sinon. Alors m est une mesure finiment additive sur X, et (par rapport à m), toute propriété des éléments de X est soit vraie presque partout, soit fausse presque partout. Il faut remarquer que cela ne définit pas une mesure au sens usuel, lequel demande que m soit dénombrablement additive ; d'ailleurs, un ultrafiltre qui définit ainsi une mesure dénombrablement additive est dit σ-complet, et l'existence d'un tel ultrafiltre (non trivial) est en fait non démontrable dans ZFC, et est équivalente à un axiome de grand cardinal.
Complétude
modifierLe degré de complétude d'un ultrafiltre U est le plus petit cardinal κ tel qu'il existe une famille de κ éléments de U dont l'intersection n'est pas dans U. Cette définition implique que le degré de complétude de tout ultrafiltre est au moins ℵ₀. Un ultrafiltre dont le degré de complétude est supérieur à ℵ₀ — autrement dit, tel que l'intersection de toute famille dénombrable d'éléments de U est encore dans U — est dit dénombrablement complet ou encore σ-complet.
Le degré de complétude d'un ultrafiltre (non trivial) σ-complet est toujours un cardinal mesurable.
Généralisation aux ensembles partiellement ordonnés
modifierDans la théorie des ensembles ordonnés, un filtre F d'un ensemble ordonné E est un sous-ensemble non vide strict de E tel que, si x appartient à F et x inférieur à y, alors y appartient à F, et pour tout x et y éléments de F, il existe z élément de F qui soit inférieur ou égal à x et à y. Un ultrafiltre de E est un filtre maximal pour l'inclusion.
Un cas particulier important d'ensemble ordonné est celui d'une algèbre de Boole. Dans ce cas, un filtre est un sous-ensemble non vide strict de E tel que, si x appartient à F et x inférieur à y, alors y appartient à F, et pour tout x et y éléments de F, x ∧ y appartient à F. Les ultrafiltres d'une algèbre de Boole sont caractérisés par le fait de contenir, pour chaque élément a de l'algèbre, soit a, soit son complémentaire non-a (égal à 1-a).
Les ultrafiltres d'une algèbre de Boole sont associés aux idéaux premiers (qui dans ce cas sont également les idéaux maximaux), par l'intermédiaire des homomorphismes de l'algèbre vers le corps F2 (noté ici ), de la manière suivante.
- Étant donné un homomorphisme d'une algèbre de Boole vers {vrai, faux}, la pré-image de « vrai » est un ultrafiltre, et la pré-image de « faux » est un idéal maximal.
- Étant donné un idéal maximal d'une algèbre de Boole, son complémentaire est un ultrafiltre, et il y a un unique homomorphisme vers {vrai, faux} envoyant l'idéal sur « faux ».
- Étant donné un ultrafiltre d'une algèbre de Boole, son complémentaire est un idéal maximal, et il y a un unique homomorphisme vers {vrai, faux} envoyant l'ultrafiltre sur « vrai ».
Un autre théorème pourrait fournir une caractérisation alternative du concept d'ultrafiltre : soit B une algèbre de Boole et F un filtre non trivial (ne contenant pas 0). F est un ultrafiltre si, et seulement si,
- pour tous , si , alors ou
pour éviter des confusions, les signes , sont utilisés pour noter les opérations de l'algèbre, tandis que les connecteurs logiques sont écrits en français[3].
Ultrafiltres triviaux et non triviaux
modifierUn filtre principal (ou trivial, ou fixé) est un filtre ayant un élément minimal, qui est alors minimum. Les filtres triviaux sont donc des ultrafiltres particuliers, de la forme Fa = {x | a ≤ x} pour un certain élément a de l'ensemble (partiellement ordonné) de base. Dans ce cas, a s'appelle l'élément principal de l'ultrafiltre. Dans le cas de filtres sur des ensembles, les éléments principaux sont exactement les singletons. Ainsi, un ultrafiltre trivial sur S est formé de tous les ensembles contenant un point donné de S. Les ultrafiltres sur des ensembles finis sont tous triviaux. Tout ultrafiltre non trivial est appelé un ultrafiltre libre (ou non principal).
On peut montrer, en utilisant le lemme de Zorn que tout filtre (ou plus généralement tout sous-ensemble ayant la propriété d'intersection finie) est contenu dans un ultrafiltre, et par conséquent que des ultrafiltres libres existent, mais cette démonstration utilisant l'axiome du choix, il n'est pas possible de donner des exemples d'ultrafiltres non triviaux, et il existe d'ailleurs des modèles de ZF n'en contenant pas. Cependant, si on admet l'axiome du choix, on peut montrer que « presque tous » les ultrafiltres sur un ensemble infini X sont libres ; plus précisément[4] : le cardinal de l'ensemble des ultrafiltres (donc aussi celui des ultrafiltres libres) est égal à 22|X| (strictement supérieur au cardinal |X| de l'ensemble des ultrafiltres triviaux).
Applications
modifierLes ultrafiltres (sur des ensembles) ont des applications en topologie, en particulier en relation avec l'étude de la compacité, et en théorie des modèles, pour la construction d'ultraproduits et d'ultrapuissances. Tout ultrafiltre sur un espace compact (séparé) est convergent, vers un point unique (et ce résultat caractérise les espaces compacts). De même, les ultrafiltres sur des ensembles partiellement ordonnés sont particulièrement utiles si l'ensemble est une algèbre de Boole, car alors ils coïncident avec les filtres premiers ; cette forme joue un rôle central dans le théorème de représentation de Stone pour les algèbres de Boole.
L'ensemble G de tous les ultrafiltres sur un ordre partiel P peut être muni d'une structure topologique naturelle, qui est d'ailleurs étroitement reliée au théorème de représentation précédent : pour tout élément a de P, soit Da = {U ∈ G | a ∈ U} ; alors, si P est une algèbre de Boole, l'ensemble de tous les D est une base d'une topologie compacte (séparée) sur G. En particulier, considérant les ultrafiltres sur un ensemble S (autrement dit, en prenant pour P l'ensemble des parties de S ordonné par inclusion), l'espace topologique correspondant est le compactifié de Stone-Čech de S muni de la topologie discrète.
La construction des ultraproduits en théorie des modèles utilise des ultrafiltres pour obtenir des extensions élémentaires (en) de structures. Par exemple, la construction des nombres hyperréels commence par étendre le domaine du discours des réels à l'ensemble des suites de réels, considéré comme une extension des réels, identifiés aux suites constantes. Les opérations et les relations entre réels ne peuvent être directement être étendues aux suites, parce que, par exemple, les suites ne sont pas totalement ordonnées par l'ordre produit. On définit donc ces relations « modulo U » (où U est un ultrafiltre sur les entiers), c'est-à-dire, par exemple, qu'on pose si l'ensemble des indices k tels que appartient à U. D'après le théorème de Łoś, ceci préserve toutes les propriétés des réels exprimables dans une logique du premier ordre, et si U est non trivial, l'extension ainsi obtenue contient de nouveaux objets (qui seront par exemple « infiniment grands », c'est-à-dire plus grands que tous les réels) ; cela permet donc de définir rigoureusement des nombres infiniment petits (ou infiniment grands), et donc une construction explicite de l'analyse non standard.
En théorie géométrique des groupes, on utilise des ultraproduits pour définir le cône asymptotique d'un groupe. Cette construction donne un sens rigoureux au fait de « considérer le groupe vu de l'infini », c'est-à-dire d'étudier la géométrie du groupe à grande échelle. Le cône asymptotique est un cas particulier de la notion d'ultralimite d'un espace métrique.
La preuve ontologique de Gödel (de l'existence de Dieu) utilise parmi ses axiomes une caractérisation de l'ensemble des « propriétés positives » qui en fait un ultrafiltre.
En théorie du choix social, on utilise des ultrafiltres libres pour définir une règle (appelée fonction de bien-être social) permettant de grouper les préférences d'une infinité d'individus. Contrairement au théorème d'impossibilité d'Arrow correspondant au cas fini, une telle règle satisfait à toutes les conditions d'Arrow[5]. Ces règles ont cependant été démontrées n'avoir pas d'intérêt pratique, car elles sont non calculables[6], [7].
Ordre sur les ultrafiltres
modifierL'ordre de Rudin–Keisler est un préordre sur la classe des ultrafiltres défini de la manière suivante : si U est un ultrafiltre sur X, et V un ultrafiltre sur Y, alors si et seulement s'il existe une fonction f: X → Y telle que
pour tout sous-ensemble C de Y.
Deux ultrafiltres U et V sont RK- équivalents, , s'il existe des ensembles , , et une bijection f: A → B vérifiant la condition précédente (si X et Y ont le même cardinal, la définition peut être simplifiée en fixant A = X, B = Y).
On démontre que est le noyau de , c'est-à-dire que si et seulement si et .
Ultrafiltres sur ω
modifierWalter Rudin a prouvé que l'hypothèse du continu prouve l'existence d'ultrafiltres de Ramsey.
Voir le paragraphe correspondant de l'article en anglais.
Notes
modifier- C'est la définition choisie par N. Bourbaki, Éléments de mathématique, livre III : Topologie générale [détail des éditions], p. I.39.
- On en déduit par récurrence que si une réunion finie A1 ∪ … ∪ An de parties de X appartient à un ultrafiltre U sur X, alors au moins l'un des Ak appartient à U : Bourbaki, p. I.39.
- On trouvera les détails (et les démonstrations) dans Corollary 3.13, p. 133. ,
- (en) Thomas Jech, Set Theory : The Third Millennium Edition, revised and expanded, Springer, , 3e éd., 772 p. (ISBN 978-3-540-44085-7, lire en ligne), p. 75.
- (en) A.P. Kirman et D. Sondermann, Arrow's Theorem, many agents, and invisible dictators, Journal of Economic Theory, , 267–277 p. (lire en ligne), chap. 2.
- (en) Mihara, H.R., Arrow's theorem and Turing computability, vol. 10, Economic Theory, , 257–276 p. (lire en ligne), chap. 2.
- (en) Mihara, H.R., Arrow's theorem, countably many agents, and more visible invisible dictators, vol. 32, Journal of Mathematical Economics, , 267–288 p. (lire en ligne), chap. 3.
Références
modifier- (en) W. W. Comfort, Ultrafilters : some old and some new results (DOI 10.1090/S0002-9904-1977-14316-4, lire en ligne)
- (en) W. W. Comfort et S. Negrepontis, The theory of ultrafilters, Berlin, New York, Springer-Verlag