# Ensemble (mathématiques)/Exercices/Ensembles
## Exercice 1-1

Pour tout ensemble $X$, vérifier que $\{\varnothing ,X\}\subset {\mathcal {P}}(X)$ et que $x\in X\Leftrightarrow \{x\}\subset X$.
* $\{\varnothing ,X\}\subset {\mathcal {P}}(X)$ car $\varnothing ,X\in {\mathcal {P}}(X)$ car $\varnothing ,X\subset X$.
* $\{x\}\subset X\Leftrightarrow \forall y\in \{x\}\quad y\in X\Leftrightarrow x\in X$.

## Exercice 1-2

* Vrai ou faux ?
** a) $\varnothing \subset \varnothing$ ?
** b) $\varnothing \in \varnothing$ ?
** c) $\varnothing \in \{\varnothing \}$ ?
** d) $\varnothing \in {\mathcal {P}}(\varnothing )$ ?
* Décrire les éléments de ${\mathcal {P}}(\varnothing )$ et de ${\mathcal {P}}({\mathcal {P}}(\varnothing ))$.
** a) Vrai (on a $X\subset X$ pour tout ensemble $X$).
** b) Faux (rien n'appartient à l'ensemble vide).
** c) Vrai (on a $x\in \{x\}$ pour tout $x$).
** d) Vrai (on a $X\in {\mathcal {P}}(X)$ pour tout ensemble $X$ d'après a), et aussi $\varnothing \in {\mathcal {P}}(X)$).
* ${\mathcal {P}}(\varnothing )=\{\varnothing \}$ donc ${\mathcal {P}}({\mathcal {P}}(\varnothing ))=\{\varnothing ,\{\varnothing \}\}$. Remarque : les cardinaux sont cohérents ($2^{0}=1$ et $2^{1}=2$).

## Exercice 1-3

À partir de la définition des couples par $(x,y)=\{\{x\},\{x,y\}\}$, montrer que :
* $(x,y)=(x',y')\Rightarrow (x=x'\quad {\text{et}}\quad y=y')$ ;
* $\{x\}\times \{x\}=\{\{\{x\}\}\}$.
* Il suffit d'utiliser la condition d'égalité pour deux paires (ou singletons), en distinguant soigneusement tous les cas possibles.
** Soit {x} = {x'} et {x, y} = {x', y'}. Alors (égalité des deux singletons) x = x'. D'autre part (égalité des deux paires), soit x = x' et y = y', ce que l'on veut démontrer, soit x = y' et y = x', mais comme par ailleurs x = x', les 4 éléments sont égaux d'où le résultat.
** Soit {x} = {x', y'} et {x, y} = {x'}. On déduit de ces deux égalités que les 4 éléments sont égaux, d'où le résultat.
* Par définition, $\{x\}\times \{x\}=\{(x,x)\}$ et $(x,x)=\{\{x\}\}$.
Remarquons qu'on aurait les mêmes résultats en définissant les couples par $(x,y)=\{\{y\},\{x,y\}\}$,
Avec cette même définition, décrire en compréhension le produit cartésien de deux ensembles $X$ et $Y$, comme sous-ensemble de ${\mathcal {P}}({\mathcal {P}}(X\cup Y))$.
Vérifions d'abord qu'on a bien $X\times Y\subset {\mathcal {P}}({\mathcal {P}}(X\cup Y))$. Soient $x\in X$ et $y\in Y$. Alors, le singleton $a=\{x\}$ et la paire $b=\{x,y\}$ sont inclus dans $X\cup Y$ donc appartiennent à ${\mathcal {P}}(X\cup Y)$, si bien que la paire $(x,y)=\{a,b\}$ est incluse dans ${\mathcal {P}}(X\cup Y)$ donc appartient à ${\mathcal {P}}({\mathcal {P}}(X\cup Y))$.
Moyennant quoi, on peut affirmer que
    $X\times Y=\{z\in {\mathcal {P}}({\mathcal {P}}(X\cup Y))\mid \exists x\in X\quad \exists y\in Y\quad z=(x,y)\}$.
A-t-on $(a,(b,c))=((a,b),c)$ ?
Les deux paires $(a,(b,c))=(a,\{b,\{b,c\}\})=\{a,\{a,\{b,\{b,c\}\}\}\}$ et $((a,b),c)=(\{a,\{a,b\}\},c)=\{\{a,\{a,b\}\},\{\{a,\{a,b\}\},c\}\}$ sont en général différentes : par exemple, les deux éléments de la seconde sont des paires, tandis que l'élément $a$ de la première n'en est généralement pas une.

## Exercice 1-4

On pose $E_{0}:=\varnothing$ et $E_{k+1}:=\{E_{k}\}$. Montrer que les ensembles $E_{0},E_{1},\dots$ sont deux à deux distincts et que l'ensemble $\{\varnothing ,\{\varnothing \}\}$ n'est égal à aucun des ensembles $E_{k}$.
$E_{0}$, les autres $E_{k}$, et $\{\varnothing ,\{\varnothing \}\}$ sont distincts car leur cardinal est respectivement 0, 1, 2. En particulier, pour tout $i>0$, $E_{0}\neq E_{i}$. Par récurrence, on en déduit : $\forall n\in \mathbb {N} \quad E_{n}\neq E_{i}+n$ (car $a\neq b\Rightarrow \{a\}\neq \{b\}$).

## Exercice 1-5

Soient ${\mathcal {A}}(x)$ et ${\mathcal {B}}(x)$ deux prédicats. On suppose : $\forall x({\mathcal {A}}(x)\Rightarrow {\mathcal {B}}(x))$. Montrer que si ${\mathcal {B}}(x)$ est collectivisant alors ${\mathcal {A}}(x)$ l'est aussi.
Soit $B$ l'ensemble tel que $\forall x({\mathcal {B}}(x)\Leftrightarrow x\in B)$. Soit $A$ l'ensemble $\{x\in B\mid {\mathcal {A}}(x)\}$. Alors, $\forall x({\mathcal {A}}(x)\Leftrightarrow x\in A)$.
Le prédicat $x=x$ est-il collectivisant ?
Non, sinon d'après la question précédente tout prédicat ${\mathcal {A}}(x)$ le serait — car $\forall x({\mathcal {A}}(x)\Rightarrow x=x)$ — or il existe des prédicats ${\mathcal {A}}(x)$ non collectivisants, par exemple $x\notin x$.

## Exercice 1-6

* Montrer que $A\subset B\Leftrightarrow {\mathcal {P}}(A)\subset {\mathcal {P}}(B)$.
* À quelle condition a-t-on respectivement ${\mathcal {P}}(E)=\varnothing$ ? ${\mathcal {P}}(E)=\{a\}$ ? $\operatorname {card} {\mathcal {P}}(E)=2$ ?
* $\Rightarrow$ : par transitivité de $\subset$. Réciproquement, ${\mathcal {P}}(A)\subset {\mathcal {P}}(B)\Rightarrow A\in {\mathcal {P}}(B)\Rightarrow A\subset B$.
* $\operatorname {card} {\mathcal {P}}(E)=2^{\operatorname {card} (E)}$ n'est jamais nul ; il vaut 1 si et seulement si $E=\varnothing$, et 2 si et seulement si $E$ est un singleton.

## Exercice 1-7

On pose $E_{0}=\varnothing$ et $E_{k+1}={\mathcal {P}}(E_{k})$. Montrer que les ensembles $E_{0},E_{1},\dots$ sont deux à deux distincts. L'ensemble $\{\varnothing ,\{\varnothing \}\}$ est-il égal à l'un des ensembles $E_{k}$ ?
La suite $\left(\operatorname {card} (E_{k})\right)$ est strictement croissante donc les $E_{k}$ sont distincts. $E_{1}=\{\varnothing \}$ donc $E_{2}=\{\varnothing ,\{\varnothing \}\}$.

## Exercice 1-8

On dit qu'un ensemble $E$ est transitif si tout élément de $E$ est inclus dans $E$ : $\forall x\quad x\in E\Rightarrow x\subset E$.
* On définit par récurrence $E_{0}=\varnothing$ et $\forall k\in \mathbb {N} \quad E_{k+1}=E_{k}\cup \{E_{k}\}$. Démontrer que les $E_{k}$ sont transitifs.
* Démontrer que les $E_{k}$ forment une suite strictement croissante d'ensembles (pour l'inclusion). Combien l'ensemble $E_{k}$ a-t-il d'éléments ?
* Prouver plus généralement que si un ensemble $E$ est transitif, alors l'ensemble $F:=E\cup \{E\}$ l'est également, et que si de plus $E\notin E$, alors $F\notin F$ et l'inclusion $E\subset F$ est stricte.
* $\varnothing$ est transitif donc par récurrence (cf. question 3 pour l'hérédité) tous les $E_{k}$ le sont.
* La suite est croissante par construction. Elle l'est strictement par récurrence, car $\varnothing \notin \varnothing$ (cf. question 3 pour l'hérédité), et $\operatorname {card} (E_{k})=k$ (à nouveau par récurrence).
** Soit $x\in F$, c'est-à-dire $x\in E$ ou $x=E$. Si $E$ est transitif, on a dans les deux cas $x\subset E$.
** Si de plus $x=F$ alors $F\subset E$, c'est-à-dire $E\in E$. Par contraposition, on en déduit : si $E\notin E$ alors $F\notin F$. Par ailleurs, $E\notin E\Leftrightarrow F\not \subset E$ (par définition de $F$).

## Exercice 1-9

* Dans certaines variantes de la théorie des ensembles, on introduit l'axiome de fondation : $\forall x\neq \varnothing \quad \exists y\in x\quad y\cap x=\varnothing$. Démontrer que cet axiome équivaut à l'affirmation suivante : il n'existe pas de suite d'ensembles $x_{0},x_{1},\dots$ telle que $\forall i\in \mathbb {N} \quad x_{i+1}\in x_{i}$. (Pour l'implication directe, considérer $x=\{x_{i}\mid i\in \mathbb {N} \}$.)
* Démontrer que l'axiome de fondation entraine qu'il n'existe aucun ensemble qui soit élément de lui-même.
* On pose $s(x)=x\cup \{x\}$ (« successeur » de $x$). Sous la même hypothèse, montrer que $x,s(x),s{\bigls(x){\bigr )},\dots$ sont deux à deux distincts.
* Toujours sous l'hypothèse de l'axiome de fondation, la relation $\left(\forall y\in x\quad y\in y\right)$ est-elle collectivisante ? Et la relation $\left(\forall y\in x\quad y\notin y\right)$ ?
* Supposons qu'il existe une suite d'ensembles $(x_{i})_{i\in I}$ telle que $\forall i\in \mathbb {N} \quad x_{i+1}\in x_{i}$ et posons $x=\{x_{i}\mid i\in \mathbb {N} \}$. Alors, $x$ est non vide et tout $y\in x$ est égal à un $x_{i}$, d'où $x_{i+1}\in y$, or $x_{i+1}\in x$, donc $x\cap y\neq \varnothing$. On a donc prouvé (par contraposition) l'implication directe. Réciproquement, supposons $\exists x\neq \varnothing \quad \forall y\in x\quad y\cap x\neq \varnothing$. Puisque $x\neq \varnothing$, soit $x_{0}\in x$. L'hypothèse sur $x$ permet ensuite de construire par récurrence (plus exactement : par choix dépendant) une suite $(x_{k})$ telle que $\forall k\in \mathbb {N} \quad x_{k+1}\in x_{k}\cap x$.
* Se déduit immédiatement de la question précédente, appliquée à une suite constante.
* Plus généralement, s'il existait deux indices $i<j$ tels que $s^{i}(x)=s^{j}(x)$ alors, à nouveau d'après la question 1 (appliquée cette fois à une suite périodique : $s^{j}(x),s^{j-1}(x),\dots ,s^{i+1}(x),s^{j}(x),s^{j-1}(x),\dots$), cela contredirait l'axiome de fondation. Autre argument : la suite des $s^{k}(x)$, a priori croissante pour l'inclusion, serait en fait constante à partir de l'indice $i$ donc on aurait $s^{i}(x)=s^{i+1}(x)$, ce qui équivaut à $s^{i}(x)\in s^{i}(x)$ donc nous ramène à la question précédente.
* La première relation est collectivisante — car $\left(\forall y\in x\quad y\in y\right)\Leftrightarrow x=\varnothing \Leftrightarrow x\in \{\varnothing \}$ — mais pas la seconde car $\left(\forall y\in x\quad y\notin y\right)\Leftrightarrow x=x$, or $x=x$ n'est pas collectivisant (voir supra).
| Sommaire | Ensembles et opérations |