Dénombrabilité

Résumé en cinq points

1Ensembles dénombrables

1.1Définitions

Deux critères pratiques en découlent, et ce sont ceux qu'on utilise réellement.

1.2Parties de N

L'idée de la construction est simple. On énumère les éléments de la partie dans l'ordre croissant, ce qui est possible parce que toute partie non vide de $\N$ a un plus petit élément. La partie étant infinie, le procédé ne s'arrête jamais. On obtient une bijection de $\N$ sur cette partie.

1.3Stabilité par produit et par réunion

Deux théorèmes, dont les démonstrations ne sont pas exigibles.

L'idée du premier dans le cas de $\N \times \N$ est le parcours en diagonales. On range les couples $(p, q)$ par valeur croissante de $p + q$, et à somme fixée par $p$ croissant. Chaque diagonale est finie, donc on épuise bien $\N \times \N$.

L'idée du second est le parcours d'un tableau à double entrée, la ligne $n$ listant les éléments du $n$-ième ensemble, en ne comptant qu'une fois les éléments communs.

1.4R n'est pas dénombrable

L'idée est l'argument diagonal. Supposons qu'on dispose d'une énumération $x_0, x_1, x_2, \dots$ de tous les réels de $\intff{0}{1}$. On construit un réel $y$ de $\intff{0}{1}$ en choisissant sa $n$-ième décimale différente de celle de $x_n$, en évitant les chiffres 0 et 9 pour écarter les écritures décimales doubles. Alors $y$ diffère de chaque $x_n$, ce qui contredit l'énumération.

L'ensemble des irrationnels n'est pas dénombrable, puisque sinon $\R$ serait réunion de deux ensembles dénombrables. « Dénombrable » ne veut pas dire « petit » au sens de la taille intuitive, mais « énumérable ».

1.5Lien avec les familles sommables

Le support d'une famille sommable de nombres complexes, c'est-à-dire l'ensemble des indices où le terme est non nul, est au plus dénombrable.

Rappel du strict nécessaire :

• pour une famille de réels positifs, la somme est la borne supérieure dans $\intfo{0}{+\infty}$ des sommes finies, éventuellement $+\infty$ ;
• une famille de complexes est sommable si la famille des modules est de somme finie, et alors sa somme ne dépend pas de l'ordre d'énumération.

Cette invariance par réindexation rend cohérentes les définitions probabilistes, puisqu'aucun ordre ne s'impose sur les valeurs d'une variable aléatoire.

2Tribus et espaces probabilisables

2.1Définition

Le programme précise que la manipulation des tribus n'est pas un objectif. On n'attend pas de construire des tribus exotiques, mais de savoir pourquoi elle est là. Sur un univers infini non dénombrable, on ne peut pas toujours affecter une probabilité à toutes les parties de $\Omega$ de façon cohérente. La tribu délimite les parties auxquelles on sait donner un sens probabiliste.

2.2Vocabulaire des événements

Il prolonge celui de première année.

• Deux événements $A$ et $B$ sont incompatibles si $A \cap B = \emptyset$.
• Le contraire de $A$ est son complémentaire.
• Une famille finie ou dénombrable $(A_i)$ d'événements deux à deux incompatibles dont la réunion est $\Omega$ s'appelle un système complet d'événements.

3Probabilités et espaces probabilisés

3.1Définition

3.2Propriétés élémentaires

Elles se démontrent comme en première année, en complétant par des ensembles vides quand il faut passer du fini au dénombrable.

3.3Continuité croissante et continuité décroissante

C'est le cœur calculatoire du chapitre.

Pour une suite quelconque $(A_n)$ d'événements, la suite des réunions des $A_k$ pour $k$ de 0 à $n$ est croissante, et la suite des intersections est décroissante. Donc :

$$\begin{aligned} P\Big(\bigcup_{k=0}^{n} A_k\Big) &\to P\Big(\bigcup_{k} A_k\Big),\\ P\Big(\bigcap_{k=0}^{n} A_k\Big) &\to P\Big(\bigcap_{k} A_k\Big). \end{aligned}$$

C'est le réflexe qui permet de traiter les événements du type « il y a au moins un succès » ou « il n'y a jamais de succès » dans un jeu infini.

3.4Sous-additivité

3.5Événements négligeables et presque sûrs

Le programme introduit aussi les systèmes quasi-complets d'événements, c'est-à-dire les familles finies ou dénombrables d'événements deux à deux incompatibles dont la réunion est presque sûre. Tout développement supplémentaire est hors programme.

4Espaces probabilisés discrets

Son support, c'est-à-dire l'ensemble des $\omega$ tels que $p_\omega \neq 0$, est au plus dénombrable. C'est une conséquence directe du résultat sur les familles sommables.

À une telle distribution on associe une probabilité $P$ sur la tribu $\mathcal{P}(\Omega)$ en posant, pour toute partie $A$ de $\Omega$ : $$P(A) = \sum_{\omega \in A} p_\omega.$$ Cette somme a un sens car la famille est sommable.

Sur un univers au plus dénombrable, se donner une probabilité revient exactement à se donner les probabilités des singletons, de somme 1. C'est le cadre de tous les exercices concrets.

5Conditionnement et indépendance

5.1Probabilités conditionnelles

L'application $P_B$ est une probabilité sur $(\Omega, \mathcal{A})$, ce qui autorise à lui appliquer tous les résultats du chapitre, continuité croissante comprise.

Les formules de première année s'étendent mot pour mot.

La nouveauté par rapport à la première année est que la somme peut être une série. Elle converge toujours, à termes positifs et de somme au plus 1.

5.2Indépendance

Cette définition ne suppose rien sur les probabilités de $A$ et de $B$. Lorsque $P(B) > 0$, elle équivaut à $P(A \mid B) = P(A)$.

Méthodes

Ce qu'il faut savoir refaire en khôlle

1. Démontrer que toute partie infinie de $\N$ est dénombrable, en décrivant l'énumération croissante.
2. Justifier la dénombrabilité de $\Z$, de $\N^2$, puis de $\Q$, en donnant à chaque fois l'injection ou la surjection utilisée.
3. Énoncer l'argument diagonal montrant que $\R$ n'est pas dénombrable.
4. Donner la définition d'une tribu et en déduire la stabilité par intersection dénombrable.
5. Démontrer la continuité croissante à partir de la $\sigma$-additivité, en construisant les événements deux à deux incompatibles.
6. Calculer, dans un jeu de pile ou face infini, la probabilité d'obtenir au moins une fois pile, par continuité croissante ou par passage au complémentaire.
7. Écrire la formule des probabilités totales avec un système complet dénombrable et justifier la convergence de la série.
8. Donner un exemple de trois événements deux à deux indépendants mais non indépendants dans leur ensemble.

Les résultats à connaître

• Toute partie infinie de N est dénombrable. Exigible avec démonstration.
• E est au plus dénombrable si et seulement si E est en bijection avec une partie de N. Exigible avec démonstration.
• S'il existe une injection de E dans un ensemble au plus dénombrable, alors E est au plus dénombrable. Exigible.
• Si E est non vide et s'il existe une surjection d'un ensemble au plus dénombrable sur E, alors E est au plus dénombrable. Exigible.
• Un produit cartésien fini d'ensembles dénombrables est dénombrable. Exigible sans démonstration.
• Une réunion finie ou dénombrable d'ensembles au plus dénombrables est au plus dénombrable. Exigible sans démonstration.
• N^p pour p ≥ 1, Z et Q sont dénombrables. Exigible.
• R n'est pas dénombrable. Exigible sans démonstration.
• Le support d'une famille sommable de complexes est au plus dénombrable. Exigible.
• Une tribu contient ∅ et est stable par réunion finie, par intersection finie ou dénombrable et par différence. Exigible avec démonstration.
• Propriétés élémentaires d'une probabilité : P(∅) = 0, additivité finie, complémentaire, croissance, formule de P(A ∪ B). Exigibles avec démonstration.
• Continuité croissante et continuité décroissante. Exigibles avec démonstration.
• Pour une suite quelconque (A_n), P de la réunion des A_k pour k ≤ n tend vers P de la réunion totale, et de même pour les intersections. Exigible.
• Sous-additivité dénombrable, sans hypothèse d'incompatibilité. Exigible avec démonstration.
• Une réunion finie ou dénombrable d'événements négligeables est négligeable. Une intersection finie ou dénombrable d'événements presque sûrs est presque sûre. Exigible.
• Probabilités composées, probabilités totales avec un système complet ou quasi-complet dénombrable, formule de Bayes. Exigibles.
• Si A et B sont indépendants, A et le contraire de B le sont. Exigible avec démonstration.
• Extension à une famille indépendante, dont on peut remplacer n'importe quels événements par leurs contraires. Elle se prouve par récurrence et est à savoir refaire.
• Une distribution discrète sur Ω définit une probabilité sur P(Ω). Si Ω est au plus dénombrable, on obtient ainsi toutes les probabilités sur P(Ω). Exigible.
• Hors programme : tribu engendrée, lemmes de Borel-Cantelli comme résultats de cours (le premier se traite en exercice), théorème de Cantor sur P(E), construction d'espaces probabilisés, convergences presque sûre, en probabilité et en loi. On admet l'existence d'un espace modélisant une suite infinie de lancers indépendants.

Clés de démonstration

Parties infinies de N. Soit A une partie infinie de N. On pose φ(0) = min A, puis φ(n+1) égal au plus petit élément de A strictement supérieur à φ(n), qui existe car A est infinie. La suite φ est strictement croissante, donc injective, et vérifie φ(n) ≥ n. Pour la surjectivité, on prend a dans A non atteint. Il existe n tel que φ(n) > a, et on prend le plus petit. Ce n n'est pas nul car φ(0) ≤ a. Alors φ(n−1) < a, donc φ(n) ≤ a par définition, ce qui est contradictoire. Astuce : définir par récurrence avec le bon ordre, puis raisonner sur le premier rang où l'on dépasse a.

Injection et surjection. Si f injecte E dans N, E est en bijection avec f(E), partie finie ou infinie de N. Si s est une surjection d'une partie de N sur E, l'application qui à e associe le plus petit antécédent de e est une injection de E dans N. Astuce : le plus petit antécédent transforme une surjection en injection, sans axiome du choix.

Une injection explicite de N² dans N. L'application (p, q) ↦ 2^p 3^q est injective par unicité de la décomposition en facteurs premiers. Astuce : les nombres premiers codent autant de coordonnées qu'on veut.

Stabilités d'une tribu. Le complémentaire d'une intersection dénombrable est la réunion des complémentaires, par De Morgan. La différence A privé de B est l'intersection de A et du contraire de B. Astuce : tout se ramène aux trois axiomes par complémentaire.

Continuité croissante. On découpe la réunion en « tranches » B_n, égales à A_n privé de A_n−1. Comme A_n−1 ⊂ A_n, on a P(B_n) = P(A_n) − P(A_n−1). La somme partielle télescope en P(A_n), et la σ-additivité conclut. Astuce : télescopage. Pour la continuité décroissante, on passe aux complémentaires.

Sous-additivité. On pose C_n égal à A_n privé de la réunion des A_k pour k < n. Les C_n sont deux à deux incompatibles, de même réunion que les A_n, et C_n ⊂ A_n. La σ-additivité et la croissance donnent la majoration. Astuce : rendre disjoint en retirant ce qui précède.

Support d'une famille sommable. Le support est la réunion, pour k ≥ 1, des ensembles S_k des indices i tels que |a_i| ≥ 1/k. Chaque S_k est fini, de cardinal au plus k fois la somme des modules. Astuce : réunion dénombrable d'ensembles finis.

Distribution discrète. Pour des parties A_n deux à deux disjointes, la somme des p_ω sur leur réunion se calcule par paquets. Astuce : le théorème de sommation par paquets des familles positives est exactement la σ-additivité.

Exemples et contre-exemples à connaître

1. L'application (p, q) ↦ 2^p(2q + 1) − 1 est une bijection explicite de N² sur N, car tout entier non nul s'écrit de façon unique comme une puissance de 2 fois un impair.
2. L'ensemble des suites à valeurs dans {0, 1} n'est pas dénombrable, alors que l'ensemble de celles qui sont nulles à partir d'un certain rang l'est. Le passage de « fini » à « infini » change tout.
3. Q est dénombrable et dense dans R. Dénombrable ne veut rien dire sur la répartition dans R.
4. Il n'existe pas de probabilité uniforme sur N. Si P({n}) = c pour tout n, la série des c vaut 0 ou +∞, jamais 1.
5. Dans un jeu de pile ou face infini, chaque suite de résultats fixée est un événement négligeable. Leur réunion est pourtant Ω, de probabilité 1. La réunion est ici non dénombrable, et la stabilité des négligeables exige une réunion dénombrable.
6. A est indépendant de lui-même si et seulement si P(A) vaut 0 ou 1, puisque P(A) = P(A)².
7. Deux événements incompatibles de probabilités strictement positives ne sont jamais indépendants, car P(A ∩ B) = 0 < P(A)P(B).
8. La suite alternée A, contraire de A, A, … avec P(A) = 1/3 n'a pas de probabilité convergente. La continuité exige la monotonie.
9. 2N* et 4N* ne sont pas indépendants pour la loi zêta de l'exercice 10, car l'un est inclus dans l'autre. L'indépendance des pN* demande des nombres premiers entre eux.

Techniques du chapitre

Technique 1 : injecter dans N par les nombres premiers. Mini-exercice : N³ est dénombrable. L'application (a, b, c) ↦ 2^a 3^b 5^c est injective par unicité de la décomposition. N³ est donc au plus dénombrable, et il est infini.

Technique 2 : écrire l'ensemble comme réunion dénombrable d'ensembles finis. Mini-exercice : l'ensemble des parties finies de N est la réunion, pour n ∈ N, des P({0, …, n}). Chacun est fini, la réunion est dénombrable et infinie.

Technique 3 : argument diagonal. Mini-exercice : soit (u_k) une suite de suites à valeurs dans {0, 1}. La suite v définie par v_n = 1 − u_n(n) diffère de u_n au rang n. Aucune énumération ne couvre donc {0, 1}^N.

Technique 4 : « jamais » s'écrit comme une intersection décroissante. Mini-exercice : on lance indéfiniment un dé équilibré. L'événement « aucun 6 parmi les n premiers lancers » a pour probabilité (5/6)ⁿ. Ces événements décroissent, leur intersection « jamais de 6 » a pour probabilité la limite, soit 0.

Technique 5 : découper selon le rang du premier succès. Mini-exercice : pièce donnant pile avec probabilité p ∈ ]0, 1[. Le premier pile au lancer n a pour probabilité (1 − p)ⁿ⁻¹ p. Ces événements sont deux à deux incompatibles, de probabilités de somme 1. Le jeu s'arrête presque sûrement.

Technique 6 : probabilités totales avec une série. Mini-exercice : l'événement E_n, de probabilité 1/2ⁿ pour n ≥ 1, forme un système complet. Sachant E_n, on lance n pièces équilibrées. La probabilité d'obtenir n piles vaut Σ (1/2ⁿ)(1/2ⁿ) = Σ 1/4ⁿ = 1/3.

Technique 7 : remonter par Bayes. Mini-exercice : dans la situation précédente, la probabilité de E₁ sachant qu'on a obtenu que des piles vaut (1/2 × 1/2)/(1/3) = 3/4.

Exercices classiques corrigés

Choisis ton niveau. Difficulté indicative ; les exercices qui se suivent restent dans l'ordre.

Erreurs fréquentes