Maîtrise les Ensembles : Cardinal, Axiome du Choix & Exercices Corrigés

Correction :

a) Le cardinal d'un ensemble fini est le nombre de ses éléments distincts. Pour $A$, il y a 3 éléments, donc $|A| = 3$. Pour $B$, il y a 3 éléments, donc $|B| = 3$.

b) $A \cup B = \{1, 2, 3, 4, 5\}$. Cet ensemble contient 5 éléments distincts.

Astuce : Pour deux ensembles, on peut utiliser la formule $|A \cup B| = |A| + |B| - |A \cap B|$. Ici, $A \cap B = \{3\}$, donc $|A \cap B|=1$. $|A \cup B| = 3 + 3 - 1 = 5$.

c) $A \cap B = \{3\}$. Cet ensemble contient 1 élément.

d) $A \setminus B = \{1, 2\}$. Cet ensemble contient 2 éléments.

Correction :

Pour démontrer cette formule, on peut utiliser un diagramme de Venn ou raisonner sur les éléments.

Considérons les éléments dans $A \cup B$. Un élément $x$ est dans $A \cup B$ si $x \in A$ ou $x \in B$ (ou les deux).

1. Si $x \in A \setminus B$, alors $x \in A$ mais $x \notin B$. Ce $x$ est compté une fois dans $|A|$. Il n'est ni dans $B$ ni dans $A \cap B$. Ce $x$ est donc compté 1 fois dans $|A| + |B| - |A \cap B|$.

2. Si $x \in B \setminus A$, alors $x \in B$ mais $x \notin A$. Ce $x$ est compté une fois dans $|B|$. Il n'est ni dans $A$ ni dans $A \cap B$. Ce $x$ est donc compté 1 fois dans $|A| + |B| - |A \cap B|$.

3. Si $x \in A \cap B$, alors $x \in A$ et $x \in B$. Ce $x$ est compté une fois dans $|A|$ et une fois dans $|B|$. Il est donc compté 2 fois dans $|A| + |B|$. Comme il est dans $A \cap B$, il est compté 1 fois dans $|A \cap B|$. Au total, il est compté $2 - 1 = 1$ fois dans $|A| + |B| - |A \cap B|$.

Tous les éléments de $A \cup B$ sont ainsi comptés exactement une fois.

Point méthode : Cette formule est une généralisation du principe d'inclusion-exclusion pour deux ensembles.

Correction :

a) Les éléments de $P$ sont les entiers naturels qui sont divisibles par 2. Donc, $P = \{0, 2, 4, 6, 8, \dots\}$.

b) L'ensemble $P$ est un ensemble infini. Plus précisément, il est dénombrable car il peut être mis en bijection avec l'ensemble des entiers naturels $\mathbb{N}$.

c) Nous cherchons une fonction $f: \mathbb{N} \to P$ qui soit bijective.

Considérons la fonction $f(n) = 2n$ pour tout $n \in \mathbb{N}$.

• Injective : Si $f(n_1) = f(n_2)$, alors $2n_1 = 2n_2$, ce qui implique $n_1 = n_2$. Donc $f$ est injective.
• Surjective : Soit $p \in P$. Par définition de $P$, $p$ est un entier naturel pair, donc $p = 2k$ pour un certain $k \in \mathbb{N}$. On peut alors écrire $p = f(k)$. Donc $f$ est surjective.

Puisque $f$ est injective et surjective, c'est une bijection.

Point méthode : Pour montrer qu'un ensemble infini est dénombrable, il suffit de trouver une bijection entre cet ensemble et $\mathbb{N}$.

Correction :

Soit $A$ un ensemble fini de cardinal $n$, c'est-à-dire $|A| = n$. Soit $B$ un sous-ensemble de $A$. Nous voulons montrer que $|B| \le n$.

Puisque $B \subseteq A$, chaque élément de $B$ est aussi un élément de $A$.

Considérons une bijection $g: B \to B'$ où $B'$ est un sous-ensemble de $A$. Si nous pouvons montrer que $|B'| \le |A|$, alors $|B| \le |A|$.

En fait, la définition même de sous-ensemble implique cette relation. Si $B \subseteq A$, alors $B$ est constitué d'éléments qui sont tous dans $A$. On peut définir une application inclusion $i: B \to A$ par $i(x) = x$ pour tout $x \in B$. Cette application est injective.

L'existence d'une injection de $B$ dans $A$ implique $|B| \le |A|$. Si $A$ est fini, $|A|=n$, et si $B$ est fini, $|B|=m$. L'existence d'une injection de $B$ dans $A$ signifie que $m \le n$.

Alternativement, par récurrence sur $|A|$ :

Cas de base : Si $|A| = 0$, alors $A = \emptyset$. Le seul sous-ensemble est $B = \emptyset$, et $|B| = 0 \le |A|$. La propriété est vraie.

Hypothèse de récurrence : Supposons que pour tout ensemble $X$ tel que $|X|=k$, et pour tout sous-ensemble $Y \subseteq X$, on ait $|Y| \le k$.

Hérédité : Soit $A$ un ensemble tel que $|A| = k+1$. Soit $B \subseteq A$. Si $A = \emptyset$, c'est le cas de base. Sinon, choisissons un élément $a \in A$. Soit $A' = A \setminus \{a\}$. Alors $|A'| = k$. Il y a deux cas pour $B$ :

• Si $a \notin B$, alors $B \subseteq A'$. Par hypothèse de récurrence, $|B| \le |A'| = k$. Comme $k < k+1$, on a $|B| \le k+1 = |A|$.
• Si $a \in B$, alors $B = B' \cup \{a\}$, où $B' = B \setminus \{a\}$. $B'$ est un sous-ensemble de $A'$, donc $|B'| \le |A'| = k$ par hypothèse de récurrence. Alors $|B| = |B'| + 1 \le k + 1 = |A|$.

Dans les deux cas, $|B| \le |A|$.

Correction :

a) Pour montrer que $\mathbb{Z}$ est dénombrable, il faut trouver une bijection entre $\mathbb{N}$ et $\mathbb{Z}$. On peut ordonner les entiers relatifs ainsi : $0, 1, -1, 2, -2, 3, -3, \dots$

Définissons une fonction $f: \mathbb{N} \to \mathbb{Z}$ comme suit :

• Si $n$ est pair, $n = 2k$ pour $k \in \mathbb{N}$. On pose $f(n) = k$.
• Si $n$ est impair, $n = 2k+1$ pour $k \in \mathbb{N}$. On pose $f(n) = -(k+1)$.

Vérifions si $f$ est bijective :

• Injective : Si $f(n_1) = f(n_2)$.
  • Si $f(n_1) = 0$, alors $n_1$ est pair ($n_1=2k$) et $f(n_1)=k=0$, donc $n_1=0$. Si $f(n_2)=0$, alors $n_2=0$. Donc $n_1=n_2$.
  • Si $f(n_1) > 0$, alors $n_1$ est pair ($n_1=2k$) et $f(n_1)=k$. Si $f(n_2)=k>0$, alors $n_2$ est pair ($n_2=2j$) et $f(n_2)=j=k$, donc $n_1=2k, n_2=2k$, $n_1=n_2$.
  • Si $f(n_1) < 0$, alors $n_1$ est impair ($n_1=2k+1$) et $f(n_1)=-(k+1)$. Si $f(n_2)=-(k+1)<0$, alors $n_2$ est impair ($n_2=2j+1$) et $f(n_2)=-(j+1)=-(k+1)$, donc $j=k$, $n_1=2k+1, n_2=2k+1$, $n_1=n_2$.
  Donc $f$ est injective.
• Surjective : Soit $z \in \mathbb{Z}$.
  • Si $z \ge 0$, alors $z = k$ pour $k \in \mathbb{N}$. On peut prendre $n=2k$ (pair). $f(2k)=k=z$.
  • Si $z < 0$, alors $z = -(k+1)$ pour $k \in \mathbb{N}$ (en posant $k' = -z - 1$, $k' \ge 0$). On peut prendre $n=2k+1$ (impair). $f(2k+1) = -(k+1) = z$.
  Donc $f$ est surjective.

Il existe donc une bijection entre $\mathbb{N}$ et $\mathbb{Z}$, ce qui prouve que $\mathbb{Z}$ est dénombrable.

b) Pour montrer que $\mathbb{Z} \times \mathbb{Z}$ est dénombrable, on peut utiliser un argument similaire ou un argument plus général : le produit d'un nombre fini d'ensembles dénombrables est dénombrable. Puisque $\mathbb{Z}$ est dénombrable, $\mathbb{Z} \times \mathbb{Z}$ est aussi dénombrable.

On peut aussi construire une bijection explicite. Une méthode courante est d'utiliser une fonction qui "serpente" sur la grille $\mathbb{Z} \times \mathbb{Z}$. Une autre méthode est d'utiliser la décomposition en facteurs premiers. Pour $(a,b) \in \mathbb{Z} \times \mathbb{Z}$, on peut associer à $(a,b)$ un entier $N$ dont la décomposition en facteurs premiers permet de retrouver $a$ et $b$. Une manière plus simple est de mapper $\mathbb{Z}$ sur $\mathbb{N}$ puis d'utiliser une bijection de $\mathbb{N} \times \mathbb{N}$ sur $\mathbb{N}$ (comme la fonction de Cantor). Soit $f: \mathbb{N} \to \mathbb{Z}$ et $g: \mathbb{N} \to \mathbb{Z}$ les bijections trouvées précédemment. Soit $h: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ une bijection (par exemple, la fonction de Cantor : $h(n,m) = \frac{1}{2}(n+m)(n+m+1) + m$). Alors la fonction $\phi: \mathbb{Z} \times \mathbb{Z} \to \mathbb{N}$ définie par $\phi(a,b) = h(f^{-1}(a), f^{-1}(b))$ est une bijection. Puisque $\mathbb{N}$ est dénombrable, $\mathbb{Z} \times \mathbb{Z}$ est dénombrable.

Astuce : Le produit cartésien d'ensembles dénombrables est dénombrable. Cela inclut $\mathbb{N} \times \mathbb{N}$, $\mathbb{Q}$ (qui peut être vu comme $\mathbb{Z} \times \mathbb{N}$ et en appliquant deux fois cette propriété). Le cardinal de ces ensembles est $\aleph_0$.

Correction :

a) L'énoncé de la fonction de choix nous dit qu'il existe une fonction $f$ qui sélectionne un élément dans chaque ensemble non vide.

Pour la famille $(A_1, A_2, A_3)$, le produit cartésien est $A_1 \times A_2 \times A_3 = \{(1,1,2), (1,1,3), (1,2,2), (1,2,3)\}$.

L'axiome du choix garantit l'existence d'une fonction $f: \{A_1, A_2, A_3\} \to \mathbb{N}$ telle que $f(A_1) \in A_1$, $f(A_2) \in A_2$, $f(A_3) \in A_3$. Par exemple, une telle fonction $f$ pourrait choisir $f(A_1)=1$, $f(A_2)=2$, $f(A_3)=3$. Le triplet $(f(A_1), f(A_2), f(A_3)) = (1, 2, 3)$ est un élément du produit cartésien $A_1 \times A_2 \times A_3$. L'axiome du choix garantit donc qu'il existe au moins un tel triplet.

b) L'ensemble $F$ est une collection d'ensembles : $F = \{\{0,1\}, \{2,3\}, \{4,5\}, \dots\}$. Chaque ensemble de $F$ est de la forme $A_n = \{2n, 2n+1\}$ pour $n \in \mathbb{N}$.

L'axiome du choix, sous la forme du produit cartésien, affirme que pour toute famille d'ensembles non vides $(B_i)_{i \in I}$, le produit cartésien $\prod_{i \in I} B_i$ est non vide.

Considérons la famille $(A_n)_{n \in \mathbb{N}} = (\{2n, 2n+1\})_{n \in \mathbb{N}}$. Chaque $A_n$ est un ensemble non vide.

L'axiome du choix garantit l'existence d'un élément $(x_n)_{n \in \mathbb{N}} \in \prod_{n \in \mathbb{N}} A_n$, c'est-à-dire une suite où $x_n \in A_n$ pour tout $n \in \mathbb{N}$.

Le fait que $A_n = \{2n, 2n+1\}$ et que pour $n \neq m$, $A_n \cap A_m = \emptyset$, implique tous les ensembles dans la famille $F$ sont déjà disjoints deux à deux.

Par conséquent, la famille $F$ elle-même est une collection infinie d'ensembles disjoints (puisque chaque élément de $F$ est un ensemble de la forme $\{2n, 2n+1\}$ et que ces ensembles sont disjoints pour différents $n$). L'axiome du choix n'est pas strictement nécessaire pour montrer que $F$ contient une sous-famille infinie d'ensembles disjoints, car $F$ l'est déjà par construction.

Cependant, l'axiome du choix est crucial pour prouver des résultats plus profonds comme l'existence d'une base dans tout espace vectoriel, ou le lemme de Zorn, qui ont des conséquences sur l'existence d'ensembles aux propriétés intéressantes.

Pour répondre plus directement à la question, l'axiome du choix garantit l'existence de $(x_n)_{n \in \mathbb{N}}$ où $x_n \in \{2n, 2n+1\}$. Si nous considérons une sous-famille infinie de $F$, par exemple $F' = \{A_0, A_1, A_2, \dots\}$, l'axiome du choix garantit qu'il existe un élément $(a_0, a_1, a_2, \dots)$ tel que $a_n \in A_n$. Ces ensembles $A_n$ sont déjà disjoints.

Correction :

Pour prouver que pour un ensemble fini $A$, "bien ordonné par $\in$" est équivalent à "ne contient pas de suite infinie $x_{n+1} \in x_n$", nous devons montrer les deux implications.

Partie 1 : Si $A$ est bien ordonné par $\in$, alors il n'y a pas de suite infinie $x_{n+1} \in x_n$.

Supposons par l'absurde qu'il existe une suite infinie $x_1, x_2, x_3, \dots$ d'éléments de $A$ telle que $x_{n+1} \in x_n$ pour tout $n \ge 1$.

Soit $B = \{x_1, x_2, x_3, \dots\}$. Cet ensemble $B$ est un sous-ensemble de $A$. Si $B$ est fini, alors la suite $(x_n)$ ne peut pas être infinie à moins qu'elle ne devienne périodique. Si $x_k = x_j$ pour $k < j$, alors on aurait une situation où $x_k \in x_{k-1} \in \dots \in x_1$. Si la suite est infinie, il faut que les éléments soient distincts au moins pendant un temps, ou qu'il y ait une récurrence infinie.

Le problème est que la relation $\in$ n'est pas toujours un ordre. Pour qu'elle soit un ordre, il faut aussi que $x \notin x$ (irréflexivité) et que si $x \in y$ et $y \in x$, alors $x=y$ (antisymétrie). Ces propriétés ne sont pas toujours vraies pour tous les ensembles.

Cependant, si on suppose que $\in$ définit un bon ordre sur $A$, cela signifie qu'il n'y a pas de suite infinie décroissante pour $\in$. L'existence d'une telle suite $x_1, x_2, \dots$ avec $x_{n+1} \in x_n$ contredirait directement la définition d'un bon ordre (qui est un ordre total où toute partie non vide admet un plus petit élément, ce qui implique l'absence de suites infinies strictement décroissantes).

Dans le contexte des ensembles finis, si on a une suite infinie $x_1, x_2, \dots$ d'éléments de $A$ telle que $x_{n+1} \in x_n$, cela implique l'on peut toujours trouver un élément plus petit dans la suite. Si $A$ est bien ordonné par $\in$, cela signifie qu'il n'y a pas de suite infinie décroissante.

Partie 2 : Si $A$ ne contient pas de suite infinie $x_{n+1} \in x_n$, alors $A$ est bien ordonné par $\in$.

Nous devons montrer que $A$ est un ensemble ordonné par $\in$ et que toute partie non vide de $A$ admet un plus petit élément. Pour que $\in$ soit un ordre, il faut vérifier l'irréflexivité ($x \notin x$) et l'antisymétrie (si $x \in y$ et $y \in x$, alors $x=y$). L'énoncé suppose que $\in$ est un ordre. On peut supposer que $A$ est un ensemble où $\in$ est un ordre (ce qui n'est pas toujours vrai en général, mais pour les ensembles bien définis, comme ceux manipulés en théorie des ensembles standard, on peut souvent le considérer ainsi, ou travailler dans un univers où ces propriétés sont assurées).

Considérons une partie non vide $S \subseteq A$. Nous voulons montrer que $S$ admet un plus petit élément pour la relation $\in$. Nous allons utiliser le lemme de Zorn.

Soit $P$ l'ensemble de toutes les parties $X \subseteq S$ telles que $X$ n'admet pas de plus petit élément dans $S$ pour la relation $\in$. Si $P$ est vide, cela signifie que toute partie de $S$ admet un plus petit élément. En particulier, $S$ lui-même admet un plus petit élément.

Considérons une chaîne dans $P$. Soit $(X_i)_{i \in I}$ une famille de parties de $S$, appartenant à $P$, telle que pour tout $i, j \in I$, si $i \le j$, alors $X_i \subseteq X_j$. Nous voulons montrer que l'union $X = \bigcup_{i \in I} X_i$ admet un majorant dans $P$. Si $X$ n'admet pas de plus petit élément, alors $X \in P$, et l'union est un majorant.

Cependant, l'application directe du lemme de Zorn est plus subtile ici. Il faut construire un ensemble ordonné dont les éléments maximaux correspondent à ce que l'on cherche.

Une approche plus standard pour prouver l'absence de suites infinies décroissantes dans un ensemble bien ordonné est de supposer qu'une telle suite existe et de montrer que cela mène à une contradiction, souvent par un argument de récurrence transfinie ou un autre lemme. Si l'on suppose que $A$ n'est pas bien ordonné, alors il existe une partie $S \subseteq A$ qui n'a pas de plus petit élément. Si $S$ n'a pas de plus petit élément, alors pour tout $x \in S$, l'ensemble $\{y \in S \mid y \in x\}$ n'est pas vide (sinon $x$ serait le plus petit élément). L'axiome du choix permet alors de construire une suite infinie décroissante.

La réciproque du lemme de Zorn est souvent utilisée ici : si un ensemble ordonné n'a pas d'élément maximal, alors il existe une chaîne infinie. Dans ce cas, si $A$ n'est pas bien ordonné, alors il existe une partie $S \subseteq A$ qui n'a pas de plus petit élément. On peut alors construire par récurrence une suite infinie $x_1, x_2, \dots$ d'éléments de $S$ telle que $x_{n+1} \in x_n$.

L'énoncé précis de l'exercice est un peu inhabituel car la relation $\in$ n'est pas toujours un bon ordre universellement. Si l'on se place dans un univers où $\in$ est un bon ordre, alors l'absence de suite infinie $x_{n+1} \in x_n$ est équivalente à être bien ordonné.

Point méthode : L'équivalence entre "bien ordonné" et "pas de suite infinie strictement décroissante" est une propriété fondamentale des bons ordres, souvent utilisée pour prouver d'autres résultats en théorie des ensembles.

Correction :

a) L'argument diagonal de Cantor vise à montrer qu'il n'existe pas de bijection entre $\mathbb{N}$ et l'ensemble des réels dans $[0, 1]$. Supposons par l'absurde qu'il existe une telle bijection $f: \mathbb{N} \to [0, 1]$. Cela signifierait que nous pouvons lister tous les nombres réels de $[0, 1]$ :

$r_1 = f(1), r_2 = f(2), r_3 = f(3), \dots$

Chaque nombre réel $r_n$ dans $[0, 1]$ peut être représenté par son développement décimal :

$r_1 = 0.d_{11}d_{12}d_{13}\dots$

$r_2 = 0.d_{21}d_{22}d_{23}\dots$

$r_3 = 0.d_{31}d_{32}d_{33}\dots$

$\dots$

Nous allons maintenant construire un nombre réel $x \in [0, 1]$ qui ne figure dans cette liste. Pour cela, nous définissons son développement décimal $x = 0.x_1x_2x_3\dots$ en choisissant chaque chiffre $x_n$ de la manière suivante :

• Si $d_{nn} \neq 1$, alors on choisit $x_n = 1$.
• Si $d_{nn} = 1$, alors on choisit $x_n = 2$.

Ce nombre $x$ est bien dans $[0, 1]$ car ses chiffres décimaux sont 1 ou 2. Il est différent de tous les $r_n$ de la liste :

• $x \neq r_1$ car $x_1 \neq d_{11}$.
• $x \neq r_2$ car $x_2 \neq d_{22}$.
• $x \neq r_n$ car $x_n \neq d_{nn}$ pour tout $n$.

Ce nouveau nombre $x$ ne peut pas être dans la liste, ce qui contredit l'hypothèse que $f$ est une bijection qui liste tous les nombres de $[0, 1]$. Donc, l'intervalle $[0, 1]$ n'est pas dénombrable.

b) On sait que l'ensemble $\mathbb{N}$ est dénombrable, et donc possède le cardinal $\aleph_0$. L'ensemble $[0, 1]$ n'est pas dénombrable, il possèd'un cardinal strictement plus grand que $\aleph_0$. Ce cardinal est noté $c$ (continuum).

Il existe une bijection entre $[0, 1]$ et $\mathbb{R}$. Par exemple, la fonction tangente peut être utilisée pour mapper l'intervalle ouvert $(-1, 1)$ sur $\mathbb{R}$. On peut ensuite construire une bijection de $[0, 1]$ sur $(-1, 1)$ (cela nécessite un peu plus de travail car les ensembles sont fermés/ouverts, mais c'est possible en utilisant des propriétés des ensembles infinis et le lemme de décomposition de Cantor-Bernstein-Schroeder). Une autre façon de le voir est que l'ensemble des nombres réels $\mathbb{R}$ a le même cardinal que l'ensemble des suites infinies d'entiers, qui est le même cardinal que celui de $[0, 1]$.

Puisque $[0, 1]$ n'est pas dénombrable, et qu'il existe une bijection entre $[0, 1]$ et $\mathbb{R}$, alors $\mathbb{R}$ n'est pas dénombrable non plus. Le cardinal de $\mathbb{R}$ est $c$.

c) Le théorème de Cantor stipule que pour tout ensemble $E$, le cardinal de son ensemble des parties $\mathcal{P}(E)$ est strictement plus grand que le cardinal de $E$. Autrement dit, $|\mathcal{P}(E)| > |E|$.

En appliquant ce théorème à $E = \mathbb{N}$, on obtient $|\mathcal{P}(\mathbb{N})| > |\mathbb{N}|$. Comme $|\mathbb{N}| = \aleph_0$, on a $|\mathcal{P}(\mathbb{N})| > \aleph_0$.

L'argument diagonal de Cantor, appliqué à $[0, 1]$ et $\mathbb{R}$, montre que le cardinal de $\mathbb{R}$ est le même que le cardinal de $\mathcal{P}(\mathbb{N})$. Le cardinal de $\mathbb{R}$ est $c$, et le cardinal de $\mathcal{P}(\mathbb{N})$ est également $c$. Le cardinal de $\mathcal{P}(\mathbb{N})$ est souvent noté $2^{\aleph_0}$.

La question de savoir si $c = \aleph_1$ (le plus petit cardinal non dénombrable après $\aleph_0$) est le contenu de l'hypothèse du continu, qui est indépendante des axiomes de ZFC (Zermelo-Fraenkel avec l'axiome du choix).