Le théorème de Kuratowski

Choisissez une partie quelconque du plan. A cette partie, on peut lui appliquer deux types d’opérations:

  • Soit on prend son complémentaire;
  • Soit on prend sa fermeture (au sens topologique du terme). Pour ceux qui ne sauraient pas vraiment ce que représente la fermeture d’un ensemble, considérez que cela revient à ajouter son bord à l’ensemble de départ.
lolilolol

Prendre la fermeture d’un ensemble revient à lui ajouter son bord.

Maintenant, appliquez ces opérations autant de fois que vous le souhaitez, dans l’ordre que vous voulez sur la partie du plan que vous voulez. Selon vous, combien d’ensembles différents pourra-t-on obtenir au maximum avec ce procédé ?

Disque rayé…

Pour bien comprendre le problème, voici un exemple. Dans le plan \mathbb{R}^2, on considère le disque ouvert D de centre (0,0) et de rayon 1, c’est-à-dire l’ensemble des points (x,y) tels que x^2+y^2 <1.

theoreme_Kuratowski_disque_ouvertDe ce disque, on peut commencer par en prendre son complémentaire:

theoreme_Kuratowski_complementaire_du_disque_ouvertOn peut aussi en prendre sa fermeture:

theoreme_Kuratowski_fermeture_du_disque_ouvertOn peut itérer ce processus, et à partir de chaque nouvel ensemble obtenu, on prend soit le complémentaire, soit la fermeture. Voici ci-dessous tous les ensembles qu’on obtient lorsqu’on applique ces deux opérations de fermeture (F) et de complémentaire (C) à notre disque initial:

Chaque ensemble obtenu est représenté en bleu. Un contour en pointillés signifie que ce contour est exclu et ne fait pas partie de l'ensemble.

Chaque ensemble obtenu est représenté en bleu. Un contour en pointillés signifie que ce contour est exclu et ne fait pas partie de l’ensemble.

Vous voyez qu’à partir d’un certain moment, on retombe sur des ensembles que l’on déjà vus et il est donc inutile d’aller plus loin. Ainsi, en prenant autant de fois que l’on veut la fermeture et le complémentaire de notre disque de départ, nous avons obtenu 4 ensembles différents.

Peut-on faire mieux que 4 ? Car ce que nous avons fait pour un disque, vous comprenez bien que nous pouvons le faire pour n’importe quelle partie du plan, aussi biscornue et bizarre soit-elle. Essayez par vous-même avec d’autres parties du plan avant de lire la suite (par exemple, avec un triangle plein dont deux des côtés sont exclus, ou bien avec l’ensemble de Cantor pourquoi pas !)

Le théorème de Kuratowski

Le théorème qui va nous intéresser dans cet article, est le théorème démontré par le mathématicien polonais Kuratowski en 1922 qui dit que:

En prenant autant de fois que l’on veut la fermeture et le complémentaire d’une partie A quelconque, on ne peut obtenir que 14 ensembles différents au plus.

Vous pouvez donc partir de n’importe quel ensemble au départ, vous ne pourrez jamais créer plus de 14 ensembles différents juste en prenant la fermeture et le complémentaire !

Au fait, pourquoi 14 ? D’où peut bien sortir ce 14 ?! Lisez attentivement la suite pour comprendre car nous allons démontrer ce théorème.

Quelques notations

Pour dire qu’on prend le complémentaire d’une partie A, on notera C(A) et pour dire qu’on en prend la fermeture, on notera F(A). Puis, pour dire qu’on prend d’abord le complémentaire de cette partie puis sa fermeture, on notera FC(A)  — un peu à la manière de la notation de la composée de deux fonctions.

D’ailleurs, cette notation FC(A) est adaptée à  la langue française, car lorsque l’ont dit « Je prends la fermeture du complémentaire de A », on prend bien d’abord le complémentaire et ensuite la fermeture ! (qui eut crû que le Français utilisait la même structure que celle de la notation d’une composée de fonctions ?).

Enfin, pour alléger les notations, au lieu de noter FC(A), on notera plus simplement FC.

Bref, tout ça pour dire que si j’écris CFCF, ça veut dire: « Je prends la fermeture, puis je prends le complémentaire, puis je prends la fermeture, puis je prends le complémentaire ». Dans cet ordre !

Crise des monoïdes

Nous allons à présent nous intéresser à toutes les combinaisons possibles que l’on peut former avec F et C (en termes plus savants, nous allons étudier le monoïde engendré par F et C). Par exemple, on peut commencer par prendre 10 fois le complémentaire, puis 8 fois la fermeture, puis 34 fois le complémentaire, puis 21 fois la fermeture puis 13 fois le complémentaire. On notera cette suite d’opérations par:

C^{13}F^{21}C^{34}F^{8}C^{10}

Plus généralement, une suite de fermetures et de complémentaires, qu’on appellera opération complexe dans la suite de l’article, peut être représentée par l’une des 4 formes suivantes:

\begin{array}{c}  C^{n_1} F^{n_2} \cdots C^{n_k}\\  ou \\  C^{n_1} F^{n_2} \cdots F^{n_k}\\  ou \\  F^{n_1} C^{n_2} \cdots C^{n_k}\\  ou\\  F^{n_1} C^{n_2} \cdots F^{n_k}\\  \end{array}

Première réduction

Vous aurez sans doute constaté les deux faits suivants:

  • Prendre deux fois de suite le complémentaire revient à ne rien faire;
  • Prendre deux fois de suite la fermeture revient à prendre une seule fois la fermeture.

Ces propriétés sont faciles à comprendre: quand on prend le complémentaire du complémentaire, on revient au point de départ. De même, si j’ajoute le bord alors que je viens de l’ajouter, je ne fais rien de plus !

Si on note Id l’opération qui consiste à ne rien changer, on peut traduire les deux faits précédents de la façon suivante: C² = Id et F²=F.

Cette première réduction montre qu’une opération complexe peut s’écrire comme une simple suite de C et de F. Par exemple, C^{13} = C et C^{34}=Id. De même, F^{21}=F et F^{8}=F. Ainsi,

C^{13}F^{21}C^{34}F^{8}C^{10} = C F Id F Id = CFF= CF

Une opération complexe n’est donc, après réduction, qu’une suite de C et de F qui alternent successivement !

Seconde réduction

On peut montrer que FCFCFCF=FCF. J’ai mis la démonstration de ce fait dans le fichier suivant:

Démonstration

Cette propriété fait bien comprendre que la longueur d’une opération complexe (qui est une suite de F et de C qui alternent comme on l’a vu) ne peut pas dépasser 7 termes après réduction (7 étant la longueur de l’opération complexe FCFCFCF).

Fin de la démonstration

A présent, nous allons utiliser les deux réductions précédentes pour montrer qu’il n’y a que 14 opérations complexes possibles. Le plus simple pour le voir est de faire le graphe de Cayley du monoïde engendré par F et C (ça y est je sors les grands termes !). Il s’agit du graphe obtenu en partant de Id et qui, à chaque étape, ajoute F ou C. Chaque fois qu’on prend le complémentaire, j’ai mis une flèche rouge et chaque fois qu’on prend la fermeture, j’ai mis une flèche bleue:theoreme_Kuratowski_graphe_de_CayleyLa flèche en pointillés de gauche exprime l’égalité FCFCFCF=FCF démontrée plus haut. La flèche en pointillés de droite vient du fait que F(CFCFCFC) = (FCFCFCF)C=(FCF)C=FCFC.

Au final, vous voyez qu’il n’y a que 14 sommets sur ce graphe, donc au plus 14 ensembles différents. CQFD.

Peut-on descendre en dessous de 14 ?

Pour être tout à fait complet, il faudrait se poser la question de savoir si la borne de 14 est optimale, c’est-à-dire s’il existe une partie qui, quand elle est soumise aux différentes opérations de fermeture et de complémentaire donne effectivement 14 ensembles différents. Si vous vous souvenez de notre exemple du disque, nous n’avions obtenu que 4 ensembles distincts, ce qui était loin du compte !

En fait, il existe bel et bien une partie qui donne 14 ensembles différents: il s’agit de la partie A de \mathbb{R} donnée par:

A = ]0;1[ \bigcup ]1;2[ \bigcup \{ 3\} \bigcup \left( [4;5] \bigcap \mathbb{Q} \right)

Voici les 14 ensembles obtenus en partant de A (rappelons que \mathbb{Q} est dense dans \mathbb{R}…):

theoreme_Kuratowski_14_ensembles_differentsComme vous le constatez, il y a bien 14 ensembles différents !

Notes:

Publicités
Cet article, publié dans Topologie, est tagué , , , , , , . Ajoutez ce permalien à vos favoris.

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s