Curiosité à propos de la limite d'une suite d'ensembles

nicolasb · 27-05-2016 00:41:20

Bonjour,

Je suis nouveau ici. Je voulais partager un petit problème sur lequel je suis tombé aujourd'hui et qui me laisse un peu perplexe. J'ai essayé de donner un exposé le plus court possible, désolé si c'est un peu long !

Donc, voilà. Soit un ensemble dénombrable (fini ou infini) [tex]S[/tex] et une suite [tex]X = (x_1, x_2, x_3, ...)[/tex] d'ensembles finis croissants. Pour tout [tex]x_n \in X[/tex], [tex]x_n \subset x_{n+1}[/tex] et [tex]x_n \subset S[/tex]. J'ai voulu formaliser la notion d'une limite qui s'approche de [tex]S[/tex] lorsque [tex]n[/tex] tend vers l'infini. Voici donc la définition qui m'a semblé la plus naturelle:

L'ensemble [tex]S[/tex] est la limite de [tex]x_n[/tex] lorsque [tex]n[/tex] tend vers l'infini si et seulement si pour tout sous-ensemble fini [tex]\epsilon \subset S[/tex], il existe un entier [tex]c[/tex] tel que pour tout entier [tex]n > c[/tex], [tex]\epsilon \subset x_n[/tex].

J'ai fait exprès de spécifier la finitude de [tex]\epsilon[/tex] et des [tex]x_n[/tex], et la dénombrabilité de [tex]S[/tex], car j'étais inquiet que cela intraîne des problèmes avec les infinis non-dénombrables.

Je vais maintenant donner un exemple trivial pour montrer le tout en action. Soit [tex]\mathbb{N} = \{1, 2, 3, 4, ...\}[/tex], l'ensemble des nombres entiers supérieurs à [tex]0[/tex], et la suite [tex]X = (x_1, x_2, ...)[/tex] définie par récurrence telle que [tex]x_1 = \{1\}[/tex] et [tex]x_{n+1}=x_n \cup \{n+1\}[/tex].

Essayons de démontrer que l'ensemble [tex]\mathbb{N}[/tex] est la limite de [tex]x_n[/tex] lorsque [tex]n[/tex] tend vers l'infini:

Soit un ensemble fini [tex]\epsilon \subset \mathbb{N}[/tex]. Puisque [tex]\epsilon[/tex] est fini et ses éléments sont des entiers, alors il possède un élément maximum [tex]\operatorname{max}(\epsilon)[/tex]. Soit un terme [tex]x_n[/tex] de la suite [tex]X[/tex]. L'ensemble [tex]x_n[/tex] contient tous les entiers plus petits ou égaux à [tex]n[/tex]. Si [tex]n[/tex] est plus grand ou égal à [tex]\operatorname{max}(\epsilon)[/tex] alors tous les éléments de [tex]\epsilon[/tex] sont contenus dans [tex]x_n[/tex], puisque tous les entiers plus petits ou égaux à [tex]n[/tex] sont contenus dans [tex]x_n[/tex]. Sinon, alors la différence [tex]\operatorname{max}(\epsilon) - \operatorname{max}(x_{n+1})[/tex] est plus petite que [tex]\operatorname{max}(\epsilon) - \operatorname{max}(x_n)[/tex] ce qui implique qu'il existe un entier [tex]k[/tex] tel que [tex]\operatorname{max}(\epsilon) - \operatorname{max}(x_{n+k}) = 0[/tex] et donc que tous les éléments de [tex]\epsilon[/tex] sont compris dans [tex]x_{n+k}[/tex]. Alors la limite de [tex]x_n[/tex] lorsque [tex]n[/tex] tends vers l'inifini est [tex]\mathbb{N}[/tex]. Ouf... fin de la démonstration.

Voici maintenant la question qui me trouble. Modifions un petit peu la définition de la suite [tex]X[/tex] en introduisant une bijection [tex]\pi:\mathbb{N}\to\mathbb{N}[/tex]. Pour savoir la valeur de [tex]\pi(x)[/tex] pour un entier [tex]x[/tex] donné, on procède de la sorte avec un algorithme qui construit en quelque sorte la définition de [tex]\pi[/tex] au fur et à mesure:

on initialise la variable CHOISIS avec un ensemble vide
on initialise la variable MIN à 1

définition de la fonction [tex]\pi[/tex]:
Si [tex]\pi(x)[/tex] a déjà été défini, alors on retourne la valeur définie

Sinon:
pour [tex]i[/tex] allant de MIN à [tex]x[/tex]:
on choisit de manière aléatoire un nombre entier [tex]y[/tex] qui n'est pas dans l'ensemble CHOISIS
on ajoute [tex]y[/tex] à l'ensemble CHOISIS
on définit [tex]\pi(i) = y[/tex]

MIN devient [tex]x + 1[/tex]
on retourne [tex]\pi(x)[/tex]

Maintenant, posons la suite [tex]X = (x_1, x_2, ...)[/tex] définie telle que [tex]x_1 = \{\pi(1)\}[/tex] et [tex]x_{n+1} = x_n \cup \{\pi(n+1)\}[/tex]. Peut-on encore dire que la limite de [tex]x_n[/tex] lorsque [tex]n[/tex] tend vers l'infini est [tex]\mathbb{N}[/tex] ? Puisque les valeur de [tex]\pi(x)[/tex] sont choisies de manière totalement aléatoire, il n'y a pas de façon de garantir que tous les éléments d'un sous-ensemble fini [tex]\epsilon \subset \mathbb{N}[/tex] seront contenus dans un [tex]x_n[/tex] alors on ne peut pas conclure que la limite de [tex]x_n[/tex] lorsque [tex]n[/tex] tend vers l'infini est [tex]\mathbb{N}[/tex].

Je trouve ce résultat plutôt contre-intuitif. Y a-t-il une erreur dans le raisonnement, ou un défaut à ma définition de limite ? Est-ce que cela signifie que l'on ne peut pas dénombrer les entiers avec une fonction aléatoire ? Qu'en pensez-vous ?

Yassine · 28-05-2016 09:06:28

Bonjour,
J'ai plusieurs remarques

1) Dans ta définition de la limite, on peut simplifier en demandant que pour tout [tex]\epsilon[/tex], il existe un [tex]n[/tex] tel que [tex]\epsilon \subset x_n[/tex]. Comme la suite est croissante, l'inclusion dans les autres [tex]x_N[/tex] pour [tex]N > n[/tex] est déjà garantie.

2) Ta bijection [tex]\pi[/tex] ne me semble pas bien définie. Dans le monde de la programmation, tu as utilisé ce qu'on appelle un effet de bord (les variables MIN et CHOISIS sont modifiées après chaque invocation). Si j'utilise la séquence [tex]\pi(20)[/tex] puis [tex]\pi(4)[/tex], je n'ai aucune garantie d'obtenir les mêmes valeurs que si j'avais d'abord commencé dans l'ordre [tex]\pi(4)[/tex] puis [tex]\pi(20)[/tex]. Dans un pur langage fonctionnel (type Haskel), on ne pourrait pas coder cette "fonction" (sans effet de bords je veux dire). Mathématiquement, la notion de "nombre aléatoire" est en réalité, comme son nom ne l'indique pas, une fonction [tex]X: \Omega \to \mathbb{N}[/tex] où [tex]\Omega[/tex] représente l'ensemble de tous "les états du monde" (plus de détail ici sur Bibm@ath). Ta fonction [tex]\pi[/tex] est donc un peu plus compliquée qu'une simple permutation de [tex]\mathbb{N}[/tex]

3) Je pense qu'une approche alternative est de considérer une bijection quelconque de [tex]\mathbb{N}[/tex], et de montrer que la suite telle que construite "tend" vers [tex]\mathbb{N}[/tex] (au sens de ta définition). La démonstration n'est pas très compliquée : il suffit de considérer l'ensemble [tex]\pi^{-1}(\epsilon')[/tex] où [tex]\epsilon' = \{1,2,\cdots,\max(\epsilon)\}[/tex] et de prendre sa borne supérieur (qui existe car [tex]\epsilon[/tex] est fini, donc [tex]\epsilon'[/tex] est fini, et donc [tex]\pi^{-1}(\epsilon')[/tex] aussi). Le fait que [tex]\pi[/tex] soit quelconque englobe en réalité ta tentative avec les nombres aléatoires.

4) tu peux maintenant essayer de généraliser en considérant non plus l'inclusion (on se fiche pas mal des éléments de chacun des [tex]x_n[/tex]) mais l'existence d'une injection [tex]x_n \hookrightarrow x_{n+1}[/tex]. En généralisant encore plus (tu "réduis" chacun des [tex]x_n[/tex] à son cardinal), tu arrives au fait qu'une suite croissante d'entiers non bornée tend vers l'infini.

Dernière modification par Yassine (28-05-2016 11:36:15)

Yassine · 28-05-2016 11:57:46

Plus généralement, le cadre mathématique qui englobe les questions que tu te poses est la théorie des ensemble, initiée par Cantor et axiomatisée par Zermelo et Fraenkel. On la désigne par Axiomatique ZF ou ZFC (C pour Choix : avec ou sans l'Axiome du Choix). C'est de la belle Mathématique. David Hilbert a dit : "Personne ne nous expulsera du paradis que Cantor a construit pour nous".

Je sais aussi qu'il y a quelques mathématiciens qui souhaiterait justement expulser les gens de ce paradis ! Il y a notamment un mathématiciens australien, Norman Wildberger, qui souhaiterait qu'on enseigne les mathématiques autrement. Sa chaîne Youtube est très riche et je trouve ses cours très intéressants. Il appelle les gens qui utilisent les infinis de Cantor "les croyants" !!
Il revisite tout en s'interdisant d'utiliser le matériel issu des infinis de Cantor : pas de nombres réels, uniquement les rationnels, pas de notion de distance (la distance requiert de la racine carrée, donc une série infinie, il utilise la notion de "quadrant" : [tex](x-y)^2[/tex]), pas de notion de continuité, de dérivabilité, ...
Ce qui est impressionnant, c'est la quantité de résultats qu'on peut montrer avec ces contraintes.

nicolasb · 30-05-2016 18:51:35

Bonjour Yassine,

Merci pour ces commentaires riches !

En fait, après y avoir bien réfléchi, deux points ressortent:

1) Par rapport à ton point 3, oui c'est un peu ce que j'avais fait à l'origine, introduire une fonction [tex]\pi:\mathbb{N} \to \mathbb{N}[/tex] bijective et je voyais que la limite était préservée (mais je réalise maintenant que si la fonction est surjective, c'est une condition suffisante). Ensuite j'avais pensé à la fonction aléatoire que j'ai essayé de décrire et j'arrivais à un constat bizarre.

2) La question est en fait de savoir, est-ce que la fonction [tex]\pi[/tex] que j'ai décrite est surjective? Comme elle est aléatoire, cela donne un drôle de résultat: on ne peut décider si la fonction est surjective ou non-surjective en un nombre fini d'étapes.

Je pense que l'essentiel de mon interrogation ce résume à cette question: est-ce que la fonction [tex]\pi[/tex] est surjective ?

Je réalise que je n'ai peut-être pas le vocabulaire suffisant pour parler de nombre aléatoire: je n'ai que des notions élémentaires de probabilité de l'école primaire pour seuls bagages dans ce domaine. Je dois avouer que la définition de variable aléatoire que tu m'as référée a pris un certain temps avant d'avoir un peu de sens et je ne crois pas que j'en saisi toutes les subtilités et particularités. Un petit cours de probabilités ne me ferait pas de mal!

J'aime l'idée d'utiliser de manière plus générale l'existence d'une injection pour passer de [tex]x_n[/tex] à [tex]x_{n+1}[/tex], au lieu de l'inclusion. Le domaine et l'image de l'injection n'ont pas besoin d'être identiques. L'image (au sens figuré, pas mathématique) que cela m'évoque est celle d'une suite qui «change de vêtement» à chaque terme, mais qui reste toujours la même en réalité. (Cette remarque n'est pas vraiment d'ordre mathématique et n'a peut-être de sens que dans ma tête...)

Par rapport à Normand Wilberger, j'ai vu une ou deux de ses vidéos (je me rappelle de la notion de «spread» il me semble, qui correspond à un «quadrant»). Son point de vue sur l'infini est intéressant, même si je ne crois pas que le miens soit aussi radical! Je ne crois pas qu'il admettrait l'existence de la fonction [tex]\pi[/tex] que j'ai décrite...

Dernière modification par nicolasb (30-05-2016 18:54:08)

Yassine · 31-05-2016 10:14:49

bonjour nicolasb,

Comme je l'ai indiqué avant, [tex]\pi[/tex] n'est pas une fonction de [tex]\mathbb{N} \to \mathbb{N}[/tex]. Je vais tenter ci-après une définition un peu plus rigoureuse.
On se donne donc un espace probabilisé [tex](\Omega, \mathcal{A}, \mathbb{P})[/tex] et on considère une famille de variables aléatoires [tex]X_n : \Omega \to \mathbb{N}[/tex] vérifiant la propriété suivante [tex]\forall n, \forall i < n, \forall \omega \in \Omega, \ X_n(\omega) \neq X_i(\omega)[/tex] (il en existe au moins une : [tex]\forall \omega \in \Omega, \ X_n(\omega)=n[/tex]).
Alors, la fonction [tex]\pi[/tex] est définie comme [tex]\pi : \Omega \times \mathbb{N} \to \mathbb{N}, \ \pi(\omega,n)=X_n(\omega)[/tex]

Maintenant, concernant la question de la surjectivité de [tex]\pi[/tex], il n'y a aucune raison pour que ce soit vérifiée. Considère par exemple un tirage aléatoire où on s'interdit de choisir des nombre pairs, on un autre où on s'astreint à ne tirer que des nombres premiers, etc.

nicolasb · 31-05-2016 16:27:14

J'essaie de décortiquer ta réponse, mais j'éprouve quelques difficultés et je n'arrive pas à recoller les morceaux avec l'algorithme que j'ai décrit. Je sais ce qu'est l'ensemble [tex]\Omega[/tex] en général, mais dans le contexte de [tex]\pi[/tex], je ne suis pas certain de ce qu'il représente: quels sont les événements qu'il contient ? J'ai aussi beaucoup de difficultés à voir où est l'aléatoire dans la définition [tex]\pi:\Omega \times \mathbb{N} \to \mathbb{N}, \pi(\omega, n) = X_n(\omega)[/tex] et aussi à comprendre comment cette définition a rapport concrètement avec l'algorithme décrit. Je crois comprendre que la condition imposée sur la famille de [tex]X_i[/tex] assure de ne pas tirer deux fois le même entier pour une même fonction, mais je n'en suis pas sûr. Que représente, dans le contexte de la fonction [tex]\pi[/tex], l'entier associé à un élément de [tex]\Omega[/tex] par la variable aléatoire [tex]X_i[/tex] ?

Peut-être qu'un exemple avec un petit ensemble, disons [tex]\{1,2\}[/tex], à la place de [tex]\mathbb{N}[/tex] pourrait m'éclairer ?

Dernière modification par nicolasb (31-05-2016 16:28:02)

nicolasb · 31-05-2016 16:46:06

Ok, je crois avoir compris. Je vais tenter moi-même de donner l'exemple avec l'ensemble [tex]\{1, 2\}[/tex] et on me corrige si je me trompe!

nicolasb · 31-05-2016 20:01:50

L'événement aléatoire correspond à prendre au hasard une fonction [tex]f:\{1,2\} \to \{1,2\}[/tex] parmi l'ensemble de ces fonctions (qu'on va noter [tex]\{1,2\}^{\{1,2\}}[/tex].) Dans ce cas-ci [tex]\Omega = \{\omega_f\}_{f \in \{1,2\}^{\{1,2\}}}[/tex] et un événement [tex]\omega_g \in \Omega[/tex] est l'événement qui représente l'action de choisir au hasard la fonction [tex]g[/tex].

Donc l'ensemble [tex]\Omega[/tex] contient les événenements «piger une fonction parmi les fonctions [tex]f:\{1,2\} \to \{1,2\}[/tex]» suivantes (représentées par une paire [tex](y_1, y_2)[/tex] où [tex]f(i) = y_i[/tex]):

1. [tex]f_1 = (1, 1)[/tex]
2. [tex]f_2 = (1, 2)[/tex]
3. [tex]f_3 = (2, 1)[/tex]
4. [tex]f_4 = (2, 2)[/tex]

La variable aléatoire [tex]X_i:\Omega \to \mathbb{N}[/tex] est définie par l'événement [tex]\omega_{f_j}[/tex] tel que [tex]X_i(\omega_{f_j}) = f_j(i)[/tex]. Aussi nous avions dans l'algorithme comme contrainte de ne pas choisir plus d'une fois la même valeur [tex]y[/tex] pour un [tex]x[/tex] donné (injectivité). La propriété [tex]\forall n, \forall i < n, \forall \omega \in \Omega, \ X_n(\omega) \neq X_i(\omega)[/tex] assure que les [tex]\omega_{f_j}[/tex] retenus respecteront cette contrainte.

Les fonctions [tex]f_j[/tex] injectives ici sont [tex]f_2[/tex] et [tex]f_3[/tex]. Ainsi on obtient la fonction [tex]\pi:\Omega \times \{1,2\} \to \{1,2\}[/tex] définie telle que [tex]\pi(\omega_{f_j}, n) = X_n(\omega_{f_j}) = f_j(n)[/tex], où [tex]f_j \in \{f_2 = (1, 2), f_3 = (2, 1)\}[/tex].

Je vais m'arrêter ici pour l'instant. Ce que j'ai écrit a-t-il du sens ?

Yassine · 31-05-2016 20:49:15

Oui, je pense que tu as bien saisis la formalisation mathématique du problème.

Quelque remarques de forme :

nicolasb a écrit :

[tex]\omega_g \in \Omega[/tex] est l'événement qui représente l'action de choisir au hasard la fonction [tex]g[/tex]

L'évènement est plutôt l'ensemble [tex]\{\omega_g\}[/tex]. Et plutôt que la formulation 'choisir au hasard', je dirais que [tex]\omega_g[/tex] représente l'état de l'univers correspondant au choix de [tex]g[/tex].
Disons que je ne suis pas sûr de connaitre une définition mathématique précise de ce qu'est le Hasard, ou de ce qu'est un choix fait au hasard. Dans la formulation que j'ai donnée, tous les choix possibles sont là et l'état du monde où un de ces choix est fait est probabilisé par une mesure [tex]\mathbb{P}[/tex]

nicolasb · 01-06-2016 00:33:02

Super! Merci Yassine, j'ai appris des choses très intéressantes!

Yassine · 01-06-2016 20:19:42

Pas de quoi. Ravi si j'ai pu t'aider.

Forum de mathématiques - Bibm@th.net

#1 27-05-2016 00:41:20

Curiosité à propos de la limite d'une suite d'ensembles

#2 28-05-2016 09:06:28

Re : Curiosité à propos de la limite d'une suite d'ensembles

#3 28-05-2016 11:57:46

Re : Curiosité à propos de la limite d'une suite d'ensembles

#4 30-05-2016 18:51:35

Re : Curiosité à propos de la limite d'une suite d'ensembles

#5 31-05-2016 10:14:49

Re : Curiosité à propos de la limite d'une suite d'ensembles

#6 31-05-2016 16:27:14

Re : Curiosité à propos de la limite d'une suite d'ensembles

#7 31-05-2016 16:46:06

Re : Curiosité à propos de la limite d'une suite d'ensembles

#8 31-05-2016 20:01:50

Re : Curiosité à propos de la limite d'une suite d'ensembles

#9 31-05-2016 20:49:15

Re : Curiosité à propos de la limite d'une suite d'ensembles

#10 01-06-2016 00:33:02

Re : Curiosité à propos de la limite d'une suite d'ensembles

#11 01-06-2016 20:19:42

Re : Curiosité à propos de la limite d'une suite d'ensembles

Pied de page des forums