Devoir surveillé — Raisonnement et vocabulaire ensembliste

Consignes générales. Durée : 4 heures. Calculatrices et documents interdits. Les cinq exercices sont indépendants et peuvent être traités dans l'ordre de votre choix ; l'exercice 5 est un problème en trois parties. Le barème, indiqué question par question, totalise $20$ points. Le sujet est dense : il n'est pas attendu que tout le monde le termine.

Dans la question 1., $E$ désigne un ensemble et $P(x)$ un prédicat portant sur les éléments de $E$. On rappelle que l'assertion $\mathrm{\exists }!x\in E,P(x)$ est vraie lorsque exactement un élément de $E$ rend $P(x)$ vraie.

1. a. (0,5 pt) Écrire l'assertion $\mathrm{\exists }!x\in E,P(x)$ en n'employant que les quantificateurs $\mathrm{\forall }$ et $\mathrm{\exists }$, le prédicat $P$, l'égalité et les connecteurs « et », « ou », $⟹$.

   b. (0,75 pt) En déduire la négation de $\mathrm{\exists }!x\in E,P(x)$, sous forme positive : aucune négation ne doit porter sur un quantificateur ni sur un connecteur, seuls « non $P(x)$ » et « $x\mathrm{\ne }y$ » étant tolérés. Traduire ensuite le résultat en une phrase française.

2. (0,75 pt) Déterminer, en justifiant, la valeur de vérité des deux assertions suivantes. Lorsque l'assertion est fausse, on démontrera sa négation en s'appuyant sur la question 1.b.

$$\mathcal{A}:\mathrm{\exists }!x\in \mathbb{R},\mathrm{\forall }y\in \mathbb{R},xy=x$$ $$\mathcal{B}:\mathrm{\exists }!x\in \mathbb{R},x^2=x$$

3. On rappelle le vocabulaire du cours : lorsque l'implication $\mathcal{U}⟹\mathcal{V}$ est vraie, on dit que $\mathcal{U}$ est une condition suffisante pour $\mathcal{V}$, et que $\mathcal{V}$ est une condition nécessaire pour $\mathcal{U}$.

   Pour chacun des quatre couples ci-dessous, dire si la première assertion est, pour la seconde, une condition nécessaire seulement, suffisante seulement, nécessaire et suffisante, ou ni l'une ni l'autre. Chaque verdict s'établit en examinant les deux implications : démonstration si elle est vraie, contre-exemple explicite si elle est fausse. Une chaîne d'équivalences correctement justifiée tient lieu de double examen.

   a. (0,25 pt) Pour $x\in \mathbb{R}$ : « $x\in \mathbb{Z}$ » pour « $2x\in \mathbb{Z}$ ».

   b. (0,25 pt) Pour une application $f:E\to F$ : « $f$ est injective » pour « $f$ est bijective ».

   c. (0,5 pt) Pour deux parties $A$ et $B$ d'un ensemble $E$, le complémentaire étant pris dans $E$ : « $A\cap B=\mathrm{\varnothing }$ » pour « $A\subset \bar{B}$ ».

   d. (0,5 pt) Pour $x\in \mathbb{R}$ : « $x>0$ » pour « $x^3>x$ ». On pourra utiliser la factorisation $x^3-x=x(x-1)(x+1)$.

Partie A — une hérédité qui ne s'enchaîne pas partout.

Pour tout entier $n⩾1$, on note ${\mathcal{P}}_n$ la proposition suivante :

« pour toute famille $(u_1,\dots ,u_n)$ de $n$ nombres réels, on a $u_i=u_j$ pour tous indices $i$ et $j$ compris entre $1$ et $n$. »

1. a. (0,5 pt) Déterminer la valeur de vérité de ${\mathcal{P}}_1$ et celle de ${\mathcal{P}}_2$, en justifiant les deux réponses.

   b. (1 pt) On considère le raisonnement suivant, qui prétend établir l'implication ${\mathcal{P}}_n⟹{\mathcal{P}}_{n+1}$ pour tout $n⩾1$.

   Soit $n⩾1$ et supposons ${\mathcal{P}}_n$ vraie. Soit $(u_1,\dots ,u_{n+1})$ une famille de $n+1$ réels. La famille $(u_1,\dots ,u_n)$ compte $n$ termes, donc ${\mathcal{P}}_n$ donne $u_1=u_2=\cdots =u_n$. La famille $(u_2,\dots ,u_{n+1})$ compte elle aussi $n$ termes, donc ${\mathcal{P}}_n$ donne $u_2=u_3=\cdots =u_{n+1}$. Les deux familles ont le terme $u_2$ en commun : tous les termes sont donc égaux à $u_2$, et ${\mathcal{P}}_{n+1}$ est vraie.

   Démontrer que ce raisonnement est valide pour tout $n⩾2$, c'est-à-dire que chacune de ses étapes y est justifiée, et dire précisément à quel endroit et pour quelle raison il ne l'est pas pour $n=1$.

   c. (0,5 pt) Généraliser le contre-exemple de la question a. pour démontrer que ${\mathcal{P}}_n$ est fausse pour tout $n⩾2$. Expliquer en une ou deux phrases ce qu'une récurrence exige de plus que « chaque implication a l'air de marcher ».

Partie B — le principe du minimum.

On munit $\mathbb{N}$ de l'ordre usuel $⩽$. On rappelle qu'un élément $m$ est un plus petit élément d'une partie $A$ lorsque $m\in A$ et $m⩽a$ pour tout $a\in A$, un plus grand élément lorsque $m\in A$ et $a⩽m$ pour tout $a\in A$, et un majorant de $A$ lorsque $a⩽m$ pour tout $a\in A$, sans qu'on demande $m\in A$.

Dans toute cette partie, on utilise librement les propriétés usuelles de l'ordre de $\mathbb{N}$ : il est total, tout entier naturel est supérieur ou égal à $0$, aucun entier ne se trouve strictement entre $n$ et $n+1$, et tout entier non nul a un prédécesseur. En revanche, dans toute la question 2., on s'interdit d'utiliser le principe du minimum : c'est précisément le résultat que l'on admet d'ordinaire sans démonstration, il n'a pas été énoncé en cours, et la question 2.c. l'établit à partir du principe de récurrence. La question 3. pourra ensuite s'en servir librement.

2. Soit $A$ une partie de $\mathbb{N}$ ne possédant pas de plus petit élément. Pour $n\in \mathbb{N}$, on note ${\mathcal{Q}}_n$ la proposition : « aucun entier $k$ vérifiant $k⩽n$ n'appartient à $A$ ».

   a. (0,25 pt) Démontrer ${\mathcal{Q}}_0$.

   b. (0,75 pt) Soit $n\in \mathbb{N}$ tel que ${\mathcal{Q}}_n$ soit vraie. En raisonnant par l'absurde et en supposant $n+1\in A$, démontrer que $n+1$ serait alors un plus petit élément de $A$. Conclure que ${\mathcal{Q}}_{n+1}$ est vraie.

   c. (0,25 pt) En invoquant le principe de récurrence, en déduire que $A=\mathrm{\varnothing }$, puis énoncer et démontrer le résultat obtenu par contraposition : c'est le principe du minimum.

3. (0,5 pt) Application. Soit $B$ une partie de $\mathbb{N}$ non vide et admettant un majorant dans $\mathbb{N}$. Démontrer que $B$ admet un plus grand élément. On pourra considérer l'ensemble des majorants de $B$ dans $\mathbb{N}$.

Dans tout l'exercice, $E$ désigne un ensemble et $A$ une partie de $E$ telle que $A\mathrm{\ne }\mathrm{\varnothing }$ et $A\mathrm{\ne }E$. On note $\bar{A}=E\setminus A$ le complémentaire de $A$ dans $E$ ; ces deux hypothèses assurent que $\{A,\bar{A}\}$ est une partition de $E$, ses deux blocs étant non vides. On considère l'application

$$\mathrm{\Gamma }:\mathcal{P}(E)⟶\mathcal{P}(A)\times \mathcal{P}(\bar{A}),\mathrm{\Gamma }(X)=(X\cap A,X\cap \bar{A})\mathrm{.}$$

Elle est bien définie, puisque $X\cap A$ est une partie de $A$ et $X\cap \bar{A}$ une partie de $\bar{A}$. Pour alléger le vocabulaire, on appellera trace de $X$ sur $A$ la partie $X\cap A$, et de même sur $\bar{A}$ : l'application $\mathrm{\Gamma }$ associe donc à une partie de $E$ le couple de ses deux traces.

1. Dans cette question seulement, $E=\{1,2,3,4\}$ et $A=\{1,2\}$.

   a. (0,25 pt) Déterminer $\mathrm{\Gamma }(\{1,3\})$ et $\mathrm{\Gamma }(A)$.

   b. (0,25 pt) Déterminer toutes les parties $X$ de $E$ telles que $\mathrm{\Gamma }(X)=(\{1\},\{4\})$.

2. (0,5 pt) On revient au cas général. Démontrer que $\mathrm{\Gamma }$ est injective.

3. (0,75 pt) Démontrer que $\mathrm{\Gamma }$ est surjective. On soignera la vérification que la partie proposée convient.

4. (0,25 pt) Conclure quant à $\mathrm{\Gamma }$ et expliciter son application réciproque.

5. (0,75 pt) Soient $X$ et $Y$ deux parties de $E$. Démontrer l'équivalence

$$X\subset Y⟺(X\cap A\subset Y\cap A\text{ et }X\cap \bar{A}\subset Y\cap \bar{A})\mathrm{.}$$

6. On considère enfin l'application $t:\mathcal{P}(E)\to \mathcal{P}(A)$ qui ne retient que la première trace, c'est-à-dire $t(X)=X\cap A$.

   a. (0,5 pt) Démontrer que $t$ est surjective mais qu'elle n'est pas injective, et préciser à quel endroit exact intervient l'une des deux hypothèses faites sur $A$, en disant laquelle.

   b. (0,25 pt) Soit $U$ une partie de $A$. Déterminer l'image réciproque $t^{-1}(\{U\})$ en s'appuyant sur la question 4.

On rappelle qu'une relation binaire $\mathcal{R}$ sur un ensemble $E$ est dite réflexive lorsque $\mathrm{\forall }x\in E,x\mathcal{R}x$, symétrique lorsque $\mathrm{\forall }(x,y)\in E^2,(x\mathcal{R}y⟹y\mathcal{R}x)$, antisymétrique lorsque $\mathrm{\forall }(x,y)\in E^2,((x\mathcal{R}y\text{ et }y\mathcal{R}x)⟹x=y)$, et transitive lorsque $\mathrm{\forall }(x,y,z)\in E^3,((x\mathcal{R}y\text{ et }y\mathcal{R}z)⟹x\mathcal{R}z)$. Une relation d'équivalence est réflexive, symétrique et transitive ; une relation d'ordre est réflexive, antisymétrique et transitive, et elle est dite totale lorsque deux éléments quelconques sont toujours comparables. Enfin, $m\in E$ est un majorant d'une partie $A$ pour $\mathcal{R}$ lorsque $a\mathcal{R}m$ pour tout $a\in A$, et un minorant lorsque $m\mathcal{R}a$ pour tout $a\in A$.

1. (0,5 pt) Sur ${\mathbb{N}}^{\ast }$, on définit la relation $\mathcal{C}$ par

$$a\mathcal{C}b⟺\left(a\text{ divise }b\text{ ou }b\text{ divise }a\right)\mathrm{.}$$

Démontrer que $\mathcal{C}$ est réflexive et symétrique, puis qu'elle n'est ni antisymétrique ni transitive.

2. L'ordre opposé. Soit $(E,\mathcal{R})$ un ensemble ordonné. On définit une relation $\mathcal{S}$ sur $E$ par

$$x\mathcal{S}y⟺y\mathcal{R}x\mathrm{.}$$

a. (0,5 pt) Démontrer que $\mathcal{S}$ est une relation d'ordre sur $E$, appelée ordre opposé de $\mathcal{R}$. On soignera particulièrement la transitivité.

b. (0,75 pt) Soient $A$ une partie de $E$ et $m\in E$. Démontrer que $m$ est un majorant de $A$ pour $\mathcal{R}$ si et seulement si $m$ est un minorant de $A$ pour $\mathcal{S}$. En déduire que $A$ admet un plus grand élément pour $\mathcal{R}$ si et seulement si $A$ admet un plus petit élément pour $\mathcal{S}$, et que ces deux éléments coïncident alors.

3. Combiner deux ordres. Soient $\mathcal{R}$ et ${\mathcal{R}}^{\mathrm{\prime }}$ deux relations d'ordre sur un même ensemble $E$. On définit deux relations $\mathcal{R}\wedge {\mathcal{R}}^{\mathrm{\prime }}$ et $\mathcal{R}\vee {\mathcal{R}}^{\mathrm{\prime }}$ par

$$x(\mathcal{R}\wedge {\mathcal{R}}^{\mathrm{\prime }})y⟺\left(x\mathcal{R}y\text{ et }x{\mathcal{R}}^{\mathrm{\prime }}y\right),x(\mathcal{R}\vee {\mathcal{R}}^{\mathrm{\prime }})y⟺\left(x\mathcal{R}y\text{ ou }x{\mathcal{R}}^{\mathrm{\prime }}y\right)\mathrm{.}$$

a. (0,5 pt) Démontrer que $\mathcal{R}\wedge {\mathcal{R}}^{\mathrm{\prime }}$ est une relation d'ordre sur $E$.

b. (0,25 pt) On note $\mathcal{D}$ la relation de divisibilité sur ${\mathbb{N}}^{\ast }$, qui est une relation d'ordre, et ${\mathcal{D}}^{\mathrm{o}\mathrm{p}}$ son ordre opposé. Vérifier que la relation $\mathcal{C}$ de la question 1. est exactement $\mathcal{D}\vee {\mathcal{D}}^{\mathrm{o}\mathrm{p}}$. Que peut-on en conclure sur la relation $\mathcal{R}\vee {\mathcal{R}}^{\mathrm{\prime }}$ en général ?

4. (0,5 pt) Démontrer qu'une relation binaire $\mathcal{R}$ sur un ensemble $E$ est à la fois une relation d'équivalence et une relation d'ordre si et seulement si $\mathcal{R}$ est la relation d'égalité sur $E$.

Peut-on ranger tous les couples d'entiers naturels dans une seule liste indexée par $\mathbb{N}$, sans en oublier aucun et sans en compter deux fois ? Autrement dit, existe-t-il une bijection de ${\mathbb{N}}^2$ sur $\mathbb{N}$ ? Ce problème étudie une application $\phi$ candidate, puis tire les conséquences de ce qu'il aura établi à son sujet.

Pour $n\in \mathbb{N}$, on pose

$$T_n={\displaystyle \frac{n(n+1)}{2}},$$

et l'on considère l'application

$$\phi :{\mathbb{N}}^2⟶\mathbb{N},\phi (p,q)={\displaystyle \frac{(p+q)(p+q+1)}{2}}+q=T_{p+q}+q\mathrm{.}$$

Points admis. D'une part, $\phi$ prend bien ses valeurs dans $\mathbb{N}$ : le cours établit en effet, par disjonction de cas sur la parité, que $n^2+n$ est pair pour tout entier $n$, de sorte que $T_n$ est un entier naturel. D'autre part, un calcul direct que l'on ne demande pas de refaire donne, pour tout $n\in \mathbb{N}$,

$$T_{n+1}=T_n+n+1,\text{et donc}{T}_n+n=T_{n+1}-1.$$

Pour $n\in \mathbb{N}$, on note enfin

$$L_n=\{(p,q)\in {\mathbb{N}}^2;p+q=n\},$$

que l'on appellera la ligne de niveau $n$. Pour deux entiers naturels $a⩽b$, on note $[\text{\hspace{0.17em}⁣}[a,b]\text{\hspace{0.17em}⁣}]$ l'ensemble des entiers $k$ tels que $a⩽k⩽b$.

Partie A — les lignes de niveau et leurs numéros.

1. (0,5 pt) Calculer $\phi (p,q)$ pour tous les couples $(p,q)$ tels que $p+q⩽3$. On présentera les résultats dans un tableau à double entrée et l'on décrira en quelques phrases l'ordre dans lequel les couples reçoivent les numéros $0,1,2,\dots$

2. (0,5 pt) Démontrer que la suite $(T_n{)}_{n\in \mathbb{N}}$ est strictement croissante, c'est-à-dire que $T_m<T_n$ dès que $m<n$. On prendra garde que l'inégalité $T_{n+1}>T_n$ ne suffit pas : elle ne compare que deux rangs consécutifs.

3. (0,25 pt) On définit sur ${\mathbb{N}}^2$ la relation $\sim$ par

$$(p,q)\sim (p^{\mathrm{\prime }},q^{\mathrm{\prime }})⟺p+q=p^{\mathrm{\prime }}+q^{\mathrm{\prime }}\mathrm{.}$$

On admet que $\sim$ est une relation d'équivalence, étant du type « avoir la même image » par l'application $(p,q)\mapsto p+q$. Déterminer sa classe d'équivalence $\mathrm{C}\mathrm{l}((p,q))$, puis en déduire, à l'aide du théorème du cours sur les classes d'équivalence, que la famille $(L_n{)}_{n\in \mathbb{N}}$ est une partition de ${\mathbb{N}}^2$.

4. Soit $n\in \mathbb{N}$.

   a. (0,75 pt) Démontrer que l'image directe $\phi (L_n)$ est égale à $[\text{\hspace{0.17em}⁣}[T_n,T_{n+1}-1]\text{\hspace{0.17em}⁣}]$.

   b. (0,5 pt) Démontrer que la restriction de $\phi$ à $L_n$ est injective : deux couples distincts d'une même ligne de niveau ont des numéros distincts.

Partie B — l'application $\phi$ est-elle bijective ?

5. (1,25 pt) Démontrer que, pour tout $N\in \mathbb{N}$, il existe un unique entier $n\in \mathbb{N}$ tel que

$$T_n⩽N<T_{n+1}\mathrm{.}$$

On démontrera l'existence par récurrence sur $N$, en distinguant deux cas dans l'hérédité, puis l'unicité séparément.

6. (0,5 pt) Démontrer que $\phi$ est injective. On pourra commencer par justifier, à l'aide de la question 3., que tout couple appartient à une unique ligne de niveau, puis établir que deux couples de même numéro appartiennent à la même.

7. (0,5 pt) Démontrer que $\phi$ est surjective, puis répondre à la question posée en tête du problème.

Partie C — exploitation.

8. (0,5 pt) Déterminer le couple ${\phi }^{-1}(777)$. On donnera le détail du calcul, en commençant par vérifier que $T_{38}=741$.

9. (0,75 pt) Soient $(p,q)$ et $(p^{\mathrm{\prime }},q^{\mathrm{\prime }})$ deux éléments de ${\mathbb{N}}^2$. Démontrer l'équivalence

$$\phi (p,q)<\phi (p^{\mathrm{\prime }},q^{\mathrm{\prime }})⟺(p+q<p^{\mathrm{\prime }}+q^{\mathrm{\prime }}\text{ ou }(p+q=p^{\mathrm{\prime }}+q^{\mathrm{\prime }}\text{ et }q<q^{\mathrm{\prime }}\left)\right)\mathrm{.}$$

10. (0,25 pt) En déduire l'existence d'une bijection de ${\mathbb{N}}^3$ sur $\mathbb{N}$, et en donner une formule explicite en fonction de $\phi$.