Exercices — Logique, raisonnement, ensembles et applications

On pose $E=\{1,2,\{1\},\{1,2\},\mathrm{\varnothing }\}$.

Cet ensemble possède donc cinq éléments : les deux nombres $1$ et $2$, les deux ensembles $\{1\}$ et $\{1,2\}$, et l'ensemble vide $\mathrm{\varnothing }$.

1. Dire si chacune des dix affirmations suivantes est vraie ou fausse, et justifier à chaque fois en une phrase.

   a. $1\in E$

   b. $\{1\}\in E$

   c. $\{1\}\subset E$

   d. $\{2\}\in E$

   e. $\mathrm{\varnothing }\in E$

   f. $\mathrm{\varnothing }\subset E$

   g. $\{\mathrm{\varnothing }\}\in E$

   h. $\{\mathrm{\varnothing }\}\subset E$

   i. $\{1,2\}\in \mathcal{P}(E)$

   j. $\mathcal{P}(E)\subset E$

2. Écrire en extension l'ensemble $\mathcal{P}(F)$ des parties de $F=\{a,b,c\}$, puis donner $\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}\mathcal{P}(F)$.

3. Donner $\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}(E)$, puis $\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}\mathcal{P}(E)$. On ne demande pas d'écrire $\mathcal{P}(E)$ en extension.

4. Une copie contient l'écriture « $2\subset E$ ». Qu'en penser ?

Dans tout l'exercice, $P$, $Q$ et $R$ désignent des assertions. On note $V$ la valeur « vrai » et $F$ la valeur « faux ».

1. Dresser dans un même tableau les valeurs de vérité des deux assertions

   $$A=(P⟹Q)⟹R\text{et}B=P⟹(Q⟹R)$$

   Sont-elles équivalentes ? Si non, donner toutes les lignes où elles diffèrent, puis un exemple concret d'assertions $P$, $Q$, $R$ pour lesquelles l'une est vraie et l'autre fausse.

2. Que peut-on en conclure sur l'écriture « $P⟹Q⟹R$ » ?

3. Montrer que $B$ est équivalente à $(P\wedge Q)⟹R$.

4. Le ou exclusif de $P$ et $Q$, noté $P⊻Q$, est l'assertion « $P$ ou $Q$, mais pas les deux ». Dresser sa table de vérité, puis démontrer

   $$P⊻Q\equiv (P\vee Q)\wedge \mathrm{\neg }(P\wedge Q)$$

5. Pour chacune des trois assertions suivantes, dire si elle est une tautologie (toujours vraie), une contradiction (toujours fausse), ou ni l'une ni l'autre.

   a. $(P⟹Q)\vee (Q⟹P)$

   b. $(P⟹Q)\wedge P\wedge \mathrm{\neg }Q$

   c. $(P\vee Q)⟹(P\wedge Q)$

6. Les assertions $(P\wedge Q)\vee R$ et $P\wedge (Q\vee R)$ sont-elles équivalentes ?

Partie A. Dans cette partie, $f$ désigne une application de $\mathbb{R}$ dans $\mathbb{R}$. Traduire chacune des phrases suivantes par une formule quantifiée, sans utiliser de mot français à l'intérieur de la formule (sauf « et » et « ou »).

1. $f$ prend la valeur $3$ au moins deux fois.
2. Tout réel a au plus deux antécédents par $f$.
3. $f$ ne s'annule qu'une seule fois sur $[0,1]$.
4. $f$ est constante sur un intervalle non réduit à un point.

Partie B. Dans cette partie, $A$ et $B$ sont deux parties d'un ensemble $E$. Même consigne.

5. $A$ et $B$ ont au moins deux éléments communs.
6. $A$ n'est pas inclus dans $B$.

Partie C. On travaille maintenant dans l'autre sens : deux formules sont proposées, qui ne diffèrent que par un jeu de parenthèses. Dire laquelle traduit la phrase française donnée, et décrire en français ce que dit l'autre. Dans chaque cas, produire un exemple explicite où les deux formules n'ont pas la même valeur de vérité.

7. Phrase : « tout élément de $A$ est pair ou impair », où $A$ est une partie de $\mathbb{Z}$.

   Formule I : $\mathrm{\forall }n\in A,\left(n\text{ est pair ou }n\text{ est impair}\right)$

   Formule II : $(\mathrm{\forall }n\in A,n\text{ est pair})\text{ ou }(\mathrm{\forall }n\in A,n\text{ est impair})$

8. Phrase : « il existe un réel en lequel $f$ et $g$ sont toutes deux strictement positives », où $f$ et $g$ vont de $\mathbb{R}$ dans $\mathbb{R}$.

   Formule I : $(\mathrm{\exists }x\in \mathbb{R},f(x)>0)\text{ et }(\mathrm{\exists }x\in \mathbb{R},g(x)>0)$

   Formule II : $\mathrm{\exists }x\in \mathbb{R},(f(x)>0\text{ et }g(x)>0)$

Dans cet exercice, on ne demande pas de fabriquer une négation, mais de diagnostiquer : reconnaître la bonne parmi quatre candidates, et prouver que chacune des trois autres est fausse en exhibant un objet témoin.

Partie A. Soit $f:\mathbb{R}\to \mathbb{R}$. L'assertion « $f$ est injective » s'écrit

$$\mathcal{I}:\mathrm{\forall }(x,x^{\mathrm{\prime }})\in {\mathbb{R}}^2,(f(x)=f(x^{\mathrm{\prime }})⟹x=x^{\mathrm{\prime }})$$

On propose quatre candidates au titre de négation de $\mathcal{I}$ :

a. $\mathrm{\forall }(x,x^{\mathrm{\prime }})\in {\mathbb{R}}^2,(f(x)=f(x^{\mathrm{\prime }})⟹x\mathrm{\ne }{x}^{\mathrm{\prime }})$

b. $\mathrm{\exists }(x,x^{\mathrm{\prime }})\in {\mathbb{R}}^2,(f(x)=f(x^{\mathrm{\prime }})⟹x\mathrm{\ne }{x}^{\mathrm{\prime }})$

c. $\mathrm{\exists }(x,x^{\mathrm{\prime }})\in {\mathbb{R}}^2,(f(x)=f(x^{\mathrm{\prime }})\text{ et }x\mathrm{\ne }{x}^{\mathrm{\prime }})$

d. $\mathrm{\exists }(x,x^{\mathrm{\prime }})\in {\mathbb{R}}^2,(f(x)\mathrm{\ne }f(x^{\mathrm{\prime }})\text{ et }x\mathrm{\ne }{x}^{\mathrm{\prime }})$

1. Dire laquelle est la négation de $\mathcal{I}$.
2. Pour chacune des trois autres, expliquer quelle manipulation fautive l'a produite, et exhiber une application $f$ précise qui prouve qu'elle n'est pas la négation de $\mathcal{I}$.

Partie B. Soient $A$ et $B$ deux parties d'un ensemble $E$. L'assertion « toute partie non vide de $A$ contient un élément de $B$ » s'écrit

$$\mathcal{J}:\mathrm{\forall }X\in \mathcal{P}(A),(X\mathrm{\ne }\mathrm{\varnothing }⟹\mathrm{\exists }b\in B,b\in X)$$

Quatre candidates au titre de négation de $\mathcal{J}$ :

a. $\mathrm{\exists }X\in \mathcal{P}(A),(X=\mathrm{\varnothing }\text{ et }\mathrm{\exists }b\in B,b\mathrm{\notin }X)$

b. $\mathrm{\forall }X\in \mathcal{P}(A),(X\mathrm{\ne }\mathrm{\varnothing }\text{ et }\mathrm{\forall }b\in B,b\mathrm{\notin }X)$

c. $\mathrm{\exists }X\in \mathcal{P}(A),(X\mathrm{\ne }\mathrm{\varnothing }\text{ et }\mathrm{\forall }b\in B,b\mathrm{\notin }X)$

d. $\mathrm{\exists }X\in \mathcal{P}(A),(X\mathrm{\ne }\mathrm{\varnothing }\text{ et }\mathrm{\exists }b\in B,b\mathrm{\notin }X)$

3. Mêmes questions : identifier la bonne, et réfuter les trois autres avec un couple $(A,B)$ explicite à chaque fois.

Partie C. Écrire la négation des deux assertions suivantes.

4. Pour $f:E\to F$ : $\mathrm{\forall }y\in F,\mathrm{\exists }x\in E,f(x)=y$.
5. Pour $A$ et $B$ deux parties de $E$ : $(A\subset B)\text{ ou }(B\subset A)$.

Partie A. On travaille dans ${\mathbb{N}}^{\ast }$, et on note $D(m,n)$ l'assertion « $m$ divise $n$ », c'est-à-dire « il existe $k\in {\mathbb{N}}^{\ast }$ tel que $n=km$ ».

Avec un prédicat à deux variables et deux quantificateurs, quatre énoncés sont possibles. Les voici :

$$\begin{array}{rl}{\displaystyle (1)}& {\displaystyle \mathrm{\forall }n\in {\mathbb{N}}^{\ast },\mathrm{\exists }m\in {\mathbb{N}}^{\ast },D(m,n)}\\ {\displaystyle (2)}& {\displaystyle \mathrm{\exists }m\in {\mathbb{N}}^{\ast },\mathrm{\forall }n\in {\mathbb{N}}^{\ast },D(m,n)}\\ {\displaystyle (3)}& {\displaystyle \mathrm{\forall }m\in {\mathbb{N}}^{\ast },\mathrm{\exists }n\in {\mathbb{N}}^{\ast },D(m,n)}\\ {\displaystyle (4)}& {\displaystyle \mathrm{\exists }n\in {\mathbb{N}}^{\ast },\mathrm{\forall }m\in {\mathbb{N}}^{\ast },D(m,n)}\end{array}$$

1. Traduire chacun de ces quatre énoncés par une phrase française.
2. Dire pour chacun s'il est vrai ou faux, avec une démonstration ou un contre-exemple.
3. Parmi ces quatre énoncés, l'un implique-t-il un autre ? Que peut-on dire des réciproques ?

Partie B. Soit $E=\{1,2,3\}$. On note ${\mathcal{P}}^{\ast }(E)$ l'ensemble des parties non vides de $E$, et on considère le prédicat $S(X,Y)$ : « $X\subset Y$ ».

4. Écrire les quatre énoncés analogues à ceux de la partie A, en remplaçant ${\mathbb{N}}^{\ast }$ par ${\mathcal{P}}^{\ast }(E)$ et $D$ par $S$, puis les traduire en français.
5. Dire pour chacun s'il est vrai ou faux, avec démonstration ou contre-exemple.
6. Comparer les deux tableaux de réponses obtenus et commenter.

Voici six extraits de copies, rendus sur des énoncés simples. Les lignes sont numérotées.

Pour chacun, répondre aux trois questions suivantes.

• a. La preuve tient-elle ?
• b. Si non, à quelle ligne se situe la faute, et comment la nomme-t-on ?
• c. Si non, rédiger une preuve correcte.

Attention : l'une de ces six copies est entièrement correcte du point de vue logique. Savoir dire « c'est juste » fait partie du travail : une preuve n'est pas fausse parce qu'elle est courte.

Copie 1

Énoncé traité. On pose $A=\{n\in \mathbb{Z};n\text{ est un multiple de }6\}$ et $B=\{n\in \mathbb{Z};n\text{ est un multiple de }3\}$. Montrer que $A\subset B$.

L1. On prend $n=12$. On a $12=6\times 2$, donc $12\in A$.

L2. Et $12=3\times 4$, donc $12\in B$.

L3. Pareil avec $18$ : $18=6\times 3$ et $18=3\times 6$, donc $18$ est dans $A$ et dans $B$.

L4. Ça marche à chaque fois, donc $A\subset B$.

Copie 2

Énoncé traité. Soient $A$ et $B$ deux parties d'un ensemble $E$. Montrer que si $A\subset B$, alors $A\cap B=A$.

L1. Supposons $A\cap B=A$.

L2. Soit $x\in A$. Alors $x\in A\cap B$, donc $x\in B$.

L3. Donc $A\subset B$, ce qu'il fallait démontrer.

Copie 3

Énoncé traité. Soient $A$, $B$, $C$ trois parties d'un ensemble $E$. Montrer que si $A\subset B$ et $B\subset C$, alors $A\subset C$.

L1. $x\in A⟹x\in B$ car $A\subset B$.

L2. $x\in B⟹x\in C$ car $B\subset C$.

L3. Donc $x\in A⟹x\in C$, c'est-à-dire $A\subset C$.

Copie 4

Énoncé traité. Soient $A$ et $B$ deux parties d'un ensemble $E$. Montrer que $A\cup (A\cap B)=A$.

L1. Soit $x\in A\cup (A\cap B)$. Alors $x\in A$ ou $x\in A\cap B$.

L2. Si $x\in A$, c'est fini.

L3. Si $x\in A\cap B$, alors $x\in A$ et $x\in B$, donc en particulier $x\in A$.

L4. Dans les deux cas $x\in A$. Donc $A\cup (A\cap B)=A$.

Copie 5

Énoncé traité. Soient $a$ et $b$ deux réels tels que $ab=a$. Montrer que $a=0$ ou $b=1$.

L1. On part de $ab=a$.

L2. On divise les deux membres par $a$, ce qui donne $b=1$.

L3. Donc $b=1$, et en particulier « $a=0$ ou $b=1$ » est vraie.

Copie 6

Énoncé traité. Soit $x$ un réel. Montrer que $x\le \mathrm{\mid }x\mathrm{\mid }$.

L1. Si $x\ge 0$, alors $\mathrm{\mid }x\mathrm{\mid }=x$.

L2. Donc $x\le \mathrm{\mid }x\mathrm{\mid }$, et on a même l'égalité.

L3. C'est vrai pour tout réel $x$, donc $x\le \mathrm{\mid }x\mathrm{\mid }$.

Les trois premières questions donnent un énoncé et le squelette de sa démonstration : la structure est écrite, il reste à remplir les trous, numérotés (1), (2), etc. Chaque trou se remplit par une formule, une phrase courte, ou les deux.

La quatrième question ne fournit aucun squelette : c'est à ce moment-là que l'exercice sert à quelque chose.

1. Une implication à démontrer directement

Énoncé. Si $m$ et $n$ sont deux entiers impairs, alors $m+n$ est pair.

Squelette à compléter.

Soient (1).

Supposons (2).

Par définition d'un entier impair, il existe (3) tels que $m=$ (4) et $n=$ (5).

Alors $m+n=$ (6), que l'on met sous la forme $2\times$ (7).

Or (8) est un entier, donc (9).

Conclusion : (10).

2. Une inclusion

Énoncé. On pose $A=\{x\in \mathbb{R};x^2-3x+2<0\}$ et $B=]0,3[$. Montrer que $A\subset B$.

Squelette à compléter.

Pour montrer une inclusion, on montre que (1).

Soit (2).

Par définition de $A$, on a (3).

Or, pour tout réel $x$, le trinôme $x^2-3x+2$ se factorise sous la forme (4) $\times$ (5).

Un produit de deux réels est strictement négatif si et seulement si (6). En étudiant les deux cas, on obtient l'encadrement (7) $<x<$ (8).

En particulier $0<x$ et $x<3$, c'est-à-dire (9).

Conclusion : (10).

3. Une équivalence, par double implication

Énoncé. Soient $A$ et $B$ deux parties d'un ensemble $E$. Montrer que $A\cup B=A\cap B$ si et seulement si $A=B$.

Squelette à compléter.

Pour montrer une équivalence, on montre (1).

Sens direct. Supposons (2). Montrons $A=B$, c'est-à-dire les deux inclusions $A\subset B$ et $B\subset A$.

Soit $x\in A$. Alors $x\in A\cup B$, car (3). Par hypothèse, $A\cup B=A\cap B$, donc (4), et en particulier (5). On a donc montré (6).

Le rôle de $A$ et celui de $B$ étant (7) dans l'hypothèse, le même raisonnement donne $B\subset A$.

Les deux inclusions donnent $A=B$.

Sens réciproque. Supposons (8). Alors $A\cup B$ et $A\cap B$ valent tous deux (9), donc $A\cup B=A\cap B$.

Conclusion : (10).

4. Sans squelette

Soient $A$ et $B$ deux parties d'un ensemble $E$. Démontrer que

$$A\subset B⟺A\setminus B=\mathrm{\varnothing }$$

Rédiger la démonstration complètement, en reprenant de vous-même la structure des trois questions précédentes.

Les quatre textes ci-dessous ont l'apparence de démonstrations. Aucun n'en est une.

Pour chacun, répondre aux trois questions suivantes.

• a. À quelle ligne exactement se situe la faute ?
• b. Comment se nomme-t-elle ?
• c. Que la preuve démontre-t-elle réellement ? C'est la question la plus instructive : le texte établit souvent quelque chose de parfaitement vrai, mais qui ne sert à rien pour l'énoncé visé.

On précisera aussi, dans chaque cas, si l'énoncé annoncé est vrai ou faux : les deux situations se présentent ici.

Démonstration 1

Énoncé annoncé. Pour tout $n\in \mathbb{N}$, $3^n\ge 2n+1$.

L1. Notons $P(n)$ l'assertion « $3^n\ge 2n+1$ ».

L2. Initialisation. $3^0=1$ et $2\times 0+1=1$, donc $P(0)$ est vraie.

L3. Hérédité. Soit $n\in \mathbb{N}$. Supposons $P(n)$ vraie et montrons $P(n+1)$, c'est-à-dire $3^{n+1}\ge 2n+3$.

L4. L'hypothèse de récurrence appliquée au rang $n+1$ donne $3^{n+1}\ge 2(n+1)+1=2n+3$.

L5. C'est exactement $P(n+1)$ : l'hérédité est établie.

L6. Conclusion. Par récurrence, $P(n)$ est vraie pour tout $n\in \mathbb{N}$.

Démonstration 2

Énoncé annoncé. Toute suite réelle $(u_n{)}_{n\in \mathbb{N}}$ est majorée.

L1. Pour $n\in \mathbb{N}$, notons $P(n)$ l'assertion : « il existe $M\in \mathbb{R}$ tel que $u_k\le M$ pour tout $k\in \{0,\dots ,n\}$ ».

L2. Initialisation. $P(0)$ est vraie : il suffit de prendre $M=u_0$.

L3. Hérédité. Soit $n\in \mathbb{N}$. Supposons $P(n)$ vraie : il existe $M\in \mathbb{R}$ tel que $u_k\le M$ pour tout $k\le n$.

L4. Posons $M^{\mathrm{\prime }}=\max (M,u_{n+1})$. Alors $u_k\le M^{\mathrm{\prime }}$ pour tout $k\le n$, et $u_{n+1}\le M^{\mathrm{\prime }}$ : donc $u_k\le M^{\mathrm{\prime }}$ pour tout $k\le n+1$, et $P(n+1)$ est vraie.

L5. Conclusion. Par récurrence, $P(n)$ est vraie pour tout $n\in \mathbb{N}$.

L6. Il existe donc $M\in \mathbb{R}$ tel que $u_n\le M$ pour tout $n\in \mathbb{N}$, c'est-à-dire que $(u_n)$ est majorée.

Démonstration 3

Énoncé annoncé. Soient $A$ et $B$ deux parties d'un ensemble $E$. Si $A\cup B=E$, alors $A=E$ ou $B=E$.

L1. Raisonnons par l'absurde : supposons le contraire, c'est-à-dire « si $A\cup B=E$, alors $A\mathrm{\ne }E$ et $B\mathrm{\ne }E$ ».

L2. Prenons $A=E$ et $B=\mathrm{\varnothing }$. On a bien $A\cup B=E\cup \mathrm{\varnothing }=E$.

L3. D'après L1, on devrait donc avoir $A\mathrm{\ne }E$. Or $A=E$.

L4. Contradiction. L'énoncé de départ est donc vrai.

Démonstration 4

Énoncé annoncé. $1=2$.

L1. Soient $a$ et $b$ deux réels tels que $a=b$.

L2. En multipliant les deux membres par $a$ : $a^2=ab$.

L3. En retranchant $b^2$ aux deux membres : $a^2-b^2=ab-b^2$.

L4. En factorisant chaque membre : $(a-b)(a+b)=b(a-b)$.

L5. En simplifiant par $a-b$ : $a+b=b$.

L6. En prenant $a=b=1$ : $1+1=1$, c'est-à-dire $2=1$.

On rappelle le résultat du cours : une implication $P⟹Q$ et sa contraposée $\mathrm{\neg }Q⟹\mathrm{\neg }P$ sont équivalentes. Démontrer l'une, c'est donc démontrer l'autre.

Pour chacun des trois énoncés suivants, écrire d'abord la contraposée, puis la démontrer.

1. Soient $m$ et $n$ deux réels positifs. Si $mn>100$, alors $m>10$ ou $n>10$.

2. Soient $a_1,a_2,a_3,a_4,a_5$ cinq entiers. Si $a_1+a_2+a_3+a_4+a_5=51$, alors l'un au moins de ces cinq entiers est supérieur ou égal à $11$.

3. Soient $f:E\to F$ une application et $A$, $B$ deux parties de $E$. Si $f(A)\cap f(B)=\mathrm{\varnothing }$, alors $A\cap B=\mathrm{\varnothing }$.

4. Dans la question 1, l'hypothèse « $m$ et $n$ positifs » est-elle nécessaire ?

5. Qu'apporte concrètement la contraposée dans ces trois exemples ? Répondre en une ou deux phrases, en regardant la forme des conclusions de départ.

On admet dans tout l'exercice que $\sqrt{2}$ est irrationnel.

On admet également le résultat suivant, démontré dans la deuxième partie de l'exercice 13 : tout entier $n\ge 1$ s'écrit de manière unique sous la forme $n=2^{k}m$, avec $k\in \mathbb{N}$ et $m$ impair. L'entier $k$ s'appelle la valuation $2$-adique de $n$ : c'est le nombre de facteurs $2$ que contient $n$.

Partie A.

1. Soient $u$ et $v$ deux entiers impairs. Montrer que $uv$ est impair, puis que $u^3$ est impair.
2. Démontrer par l'absurde que $\sqrt[3]{2}$ est irrationnel.

Partie B.

3. Soient $r$ et $s$ deux rationnels tels que $r<s$. On pose

   $$t=r+\frac{s-r}{\sqrt{2}}$$

   Montrer que $r<t<s$.

4. Démontrer par l'absurde que $t$ est irrationnel. Conclure : entre deux rationnels distincts, il existe toujours un irrationnel.

Partie C.

5. Démontrer par l'absurde qu'il n'existe aucun entier $n$ tel que $n^2+n+1$ soit pair.

On rappelle la définition : pour tout réel $x$, $\mathrm{\mid }x\mathrm{\mid }=x$ si $x\ge 0$, et $\mathrm{\mid }x\mathrm{\mid }=-x$ si $x<0$.

Chaque fois qu'une valeur absolue apparaît, on ne sait pas laquelle des deux formules s'applique : c'est ce qui rend la disjonction de cas inévitable. Tout l'exercice consiste à choisir les bons cas, à vérifier qu'ils recouvrent bien toutes les situations, et à conclure sur l'ensemble des cas.

1. On veut résoudre dans $\mathbb{R}$ l'équation

$$\mathrm{\mid }x-1\mathrm{\mid }+\mathrm{\mid }x+2\mathrm{\mid }=5$$

a. Les deux valeurs absolues changent de formule en $x=1$ et en $x=-2$. Ces deux valeurs découpent $\mathbb{R}$ en trois zones :

Dans chacune des trois zones, écrire $\mathrm{\mid }x-1\mathrm{\mid }$ et $\mathrm{\mid }x+2\mathrm{\mid }$ sans valeur absolue.

b. Résoudre l'équation dans chaque zone, sans oublier de vérifier que la solution trouvée appartient bien à la zone où on l'a cherchée.

c. Conclure en donnant l'ensemble $\mathcal{S}$ des solutions, et vérifier chaque solution dans l'équation de départ.

2. Soient $a$ et $b$ deux réels. Démontrer que

$$\max (a,b)=\frac{a+b+\mathrm{\mid }a-b\mathrm{\mid }}{2}$$

En déduire une formule analogue pour $\min (a,b)$.

3. Soient $a$ et $b$ deux réels. Démontrer l'inégalité triangulaire

$$\mathrm{\mid }a+b\mathrm{\mid }\le \mathrm{\mid }a\mathrm{\mid }+\mathrm{\mid }b\mathrm{\mid }$$

par disjonction sur les signes de $a$ et de $b$, puis déterminer exactement dans quels cas l'égalité a lieu.

Dans tout l'exercice, $E$ et $F$ désignent des ensembles, $A$, $B$, $C$ des parties de $E$, et $f:E\to F$ une application.

On rappelle que l'image réciproque d'une partie $B^{\mathrm{\prime }}$ de $F$ est

$$f^{-1}(B^{\mathrm{\prime }})=\{x\in E;f(x)\in B^{\mathrm{\prime }}\}$$

Cette notation ne suppose pas que $f$ soit bijective : $f^{-1}(B^{\mathrm{\prime }})$ est une partie de $E$, définie pour toute application $f$.

Chacune des six assertions ci-dessous est soit vraie, soit fausse. Trancher, puis :

• si elle est vraie, la démontrer ;
• si elle est fausse, produire un contre-exemple explicite, entièrement calculé. Écrire « il suffit de prendre des ensembles bien choisis » ne vaut aucun point.

1. Si $A\cup B=A\cup C$, alors $B=C$.
2. Si $A\times B\subset A\times C$ et $A\mathrm{\ne }\mathrm{\varnothing }$, alors $B\subset C$.
3. $\mathcal{P}(A)\cup \mathcal{P}(B)=\mathcal{P}(A\cup B)$.
4. Toute application injective de $E$ dans $E$ est surjective.
5. Pour toute partie $A$ de $E$ et toute partie $B^{\mathrm{\prime }}$ de $F$ : $f(A)\subset B^{\mathrm{\prime }}⟺A\subset f^{-1}(B^{\mathrm{\prime }})$.
6. Si $f\circ g=g\circ f$, alors $f=g$ (où $f$ et $g$ vont de $E$ dans $E$).

Partie A. On cherche toutes les applications $f:{\mathbb{R}}^{\ast }\to \mathbb{R}$ telles que

$$(E)\mathrm{\forall }x\in {\mathbb{R}}^{\ast },f(x)+2f\text{\hspace{0.17em}⁣}\left(\frac{1}{x}\right)=3x$$

1. Analyse. Soit $f$ une solution de $(E)$. En appliquant $(E)$ au réel ${\displaystyle \frac{1}{x}}$, écrire une seconde égalité, puis résoudre le système des deux égalités d'inconnues $f(x)$ et $f\text{\hspace{0.17em}⁣}\left({\displaystyle \frac{1}{x}}\right)$. En déduire qu'il existe au plus une solution, et donner son expression.

2. Synthèse. Vérifier que l'application obtenue est effectivement solution de $(E)$.

3. Expliquer pourquoi la question 2 est indispensable : que sait-on exactement à la fin de la question 1, et que sait-on de plus après la question 2 ?

Partie B. On veut montrer que tout entier $n\ge 1$ s'écrit de manière unique sous la forme

$$n=2^{k}m,k\in \mathbb{N},m\text{ impair}$$

4. Écrire cette décomposition pour $n=40$, $n=96$ et $n=7$.

5. Existence. Soit $n\ge 1$. On pose $S=\{j\in \mathbb{N};2^j\text{ divise }n\}$. Montrer que $S$ est une partie non vide et majorée de $\mathbb{N}$, puis conclure en considérant son plus grand élément.

6. Unicité. Montrer que si $2^{k}m=2^{k^{\mathrm{\prime }}}{m}^{\mathrm{\prime }}$ avec $k,k^{\mathrm{\prime }}\in \mathbb{N}$ et $m$, $m^{\mathrm{\prime }}$ impairs, alors $k=k^{\mathrm{\prime }}$ et $m=m^{\mathrm{\prime }}$.

7. Cette écriture fait de $n$ un produit. L'exercice 17 étudie une autre écriture de $n$, sous forme de somme de puissances de $2$. En quoi les deux questions sont-elles différentes ?

Les trois démonstrations demandées sont à rédiger en entier, en respectant le modèle en quatre temps :

• on nomme la propriété $P(n)$ et on dit pour quels entiers on veut la démontrer ;
• initialisation : on vérifie $P(n_0)$ par un calcul explicite ;
• hérédité : on écrit « soit $n\ge n_0$, supposons $P(n)$ », on énonce ce que dit $P(n)$, puis on démontre $P(n+1)$ ;
• conclusion : on invoque le principe de récurrence et on énonce le résultat.

1. Démontrer que pour tout entier $n\ge 1$,

$$\sum _{k=1}^n\frac{1}{k(k+1)}=\frac{n}{n+1}$$

2. Démontrer que pour tout entier $n\ge 1$,

$$\sum _{k=1}^{n}k(k+1)=\frac{n(n+1)(n+2)}{3}$$

3. Soit $E$ un ensemble fini à $n$ éléments. Démontrer par récurrence sur $n$ que

$$\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}\mathcal{P}(E)=2^n$$

On pourra, pour l'hérédité, choisir un élément $a$ de $E$ et séparer les parties de $E$ selon qu'elles contiennent ou non cet élément.

On considère la suite $(u_n{)}_{n\in \mathbb{N}}$ définie par

$$u_0=1\text{et}\mathrm{\forall }n\in \mathbb{N},u_{n+1}=\sqrt{2+u_n}$$

Une telle définition pose une question préalable : rien ne garantit a priori que la racine carrée soit calculable à chaque étape. C'est le premier point à établir.

1. Calculer $u_1$, $u_2$ et $u_3$ : valeur exacte, puis valeur approchée à ${10}^{-3}$ près.

2. Démontrer par récurrence que, pour tout $n\in \mathbb{N}$, le terme $u_n$ est bien défini et vérifie $0\le u_n\le 2$.

3. On pose $g(x)=\sqrt{2+x}$ pour $x\ge -2$. Reformuler la question 2 en une phrase portant sur $g$ et sur l'intervalle $[0,2]$.

4. Démontrer par récurrence que la suite $(u_n)$ est croissante, c'est-à-dire que $u_n\le u_{n+1}$ pour tout $n\in \mathbb{N}$.

5. Retrouver le résultat de la question 4 sans récurrence, en étudiant le signe de $u_{n+1}^2-u_n^2$.

6. La suite est croissante et majorée par $2$. Que peut-on en dire ici, et que ne peut-on pas encore en dire ?

On considère la suite $(u_n{)}_{n\in \mathbb{N}}$ définie par

$$u_0=2,u_1=3,\mathrm{\forall }n\in \mathbb{N},u_{n+2}=3u_{n+1}-2u_n$$

Chaque terme dépend ici des deux précédents. Une récurrence simple ne suffira donc pas : il faudra deux initialisations et une hérédité qui utilise deux hypothèses.

1. Calculer $u_2$, $u_3$ et $u_4$.

2. L'énoncé donne la formule close

   $$\mathrm{\forall }n\in \mathbb{N},u_n=2^n+1$$

   Il ne s'agit pas de la deviner mais de la démontrer, par récurrence double. Rédiger la démonstration en entier.

3. Démontrer que $u_n$ est impair pour tout $n\ge 1$, sans utiliser la formule close, par une récurrence portant elle aussi sur deux rangs.

4. Pourquoi l'énoncé de la question 3 exclut-il le rang $0$ ?

5. Relire l'hérédité de la question 3 : de laquelle des deux hypothèses a-t-elle réellement eu besoin ? Qu'en conclure ?

Dans tout l'exercice, on appelle écriture binaire d'un entier $n\ge 1$ toute égalité de la forme

$$n=2^{k_1}+2^{k_2}+\cdots +2^{k_r}$$

où $r\ge 1$ et où $k_1>k_2>\cdots >k_r$ sont des entiers naturels. Les exposants sont donc deux à deux distincts, et on convient de les ranger dans l'ordre décroissant : deux écritures binaires sont dites distinctes lorsque les listes d'exposants qu'elles utilisent ne sont pas les mêmes.

On admet le principe du bon ordre : toute partie non vide de $\mathbb{N}$ admet un plus petit élément, ainsi que sa conséquence, à savoir que toute partie non vide et majorée de $\mathbb{N}$ admet un plus grand élément.

1. Écrire $13$, puis $100$, sous cette forme, en retranchant à chaque étape la plus grande puissance de $2$ inférieure ou égale au nombre qui reste.

2. Préliminaire.

   a. Démontrer par récurrence que $2^k\ge k+1$ pour tout $k\in \mathbb{N}$.

   b. En déduire que, pour tout entier $n\ge 1$, l'ensemble $K_n=\{k\in \mathbb{N};2^k\le n\}$ est non vide et majoré. Il admet donc un plus grand élément, noté $k(n)$. Démontrer que $2^{k(n)}\le n<2^{k(n)+1}$.

3. Existence. Démontrer par récurrence forte que tout entier $n\ge 1$ admet au moins une écriture binaire.

4. Un encadrement. Soient $k_1>k_2>\cdots >k_r$ des entiers naturels. Démontrer que

   $$2^{k_1}\le 2^{k_1}+2^{k_2}+\cdots +2^{k_r}\le 2^{k_1+1}-1$$

   En déduire que, si $n=2^{k_1}+\cdots +2^{k_r}$ est une écriture binaire de $n$, alors nécessairement $k_1=k(n)$.

5. Unicité. Démontrer que l'écriture binaire d'un entier $n\ge 1$ est unique. On raisonnera par l'absurde en considérant le plus petit entier qui en admettrait deux distinctes.

6. L'exercice 13 démontre que tout entier $n\ge 1$ s'écrit de façon unique sous la forme $n=2^{k}m$ avec $k\in \mathbb{N}$ et $m$ impair. Expliquer en une phrase pourquoi ce résultat et celui du présent exercice ne disent pas la même chose, et donner les deux écritures de $100$.

Pour $n\ge 2$, on note $P(n)$ la propriété suivante :

pour tous réels positifs $x_1,x_2,\dots ,x_n$, on a $\sqrt[n]{x_1{x}_2\cdots x_n}\le {\displaystyle \frac{x_1+x_2+\cdots +x_n}{n}}$.

Autrement dit : la moyenne géométrique de $n$ réels positifs est toujours inférieure ou égale à leur moyenne arithmétique. Le but de l'exercice est de démontrer $P(n)$ pour tout $n\ge 2$, par un schéma de récurrence inhabituel dû à Cauchy : on monte de $n$ à $2n$, puis on redescend de $n$ à $n-1$.

On utilisera librement le fait que, pour tout entier $p\ge 1$, les applications $t\mapsto t^p$ et $t\mapsto \sqrt[p]{t}$ sont croissantes sur $[0,+\mathrm{\infty }[$, et que $\sqrt[p]{t}\ge 0$ pour tout $t\ge 0$.

1. Le cas $n=2$. Démontrer $P(2)$, en partant de $(\sqrt{a}-\sqrt{b}{)}^2\ge 0$. Préciser à quelle condition l'inégalité est une égalité.

2. La montée. Soit $n\ge 2$. On suppose $P(n)$ vraie ; on veut en déduire $P(2n)$. Soient $x_1,\dots ,x_{2n}$ des réels positifs. On pose

   $$A=\frac{x_1+\cdots +x_n}{n}\text{et}B=\frac{x_{n+1}+\cdots +x_{2n}}{n}$$

   a. Justifier que $\sqrt[2n]{x_1\cdots x_{2n}}=\sqrt{\sqrt[n]{x_1\cdots x_n}\times \sqrt[n]{x_{n+1}\cdots x_{2n}}}$.

   b. En utilisant $P(n)$ deux fois, puis $P(2)$ une fois, démontrer $P(2n)$.

3. En déduire, par récurrence sur $p$, que $P(2^p)$ est vraie pour tout entier $p\ge 1$.

4. La descente. Soit $n\ge 3$. On suppose $P(n)$ vraie ; on veut en déduire $P(n-1)$. Soient $x_1,\dots ,x_{n-1}$ des réels positifs et

   $$m=\frac{x_1+\cdots +x_{n-1}}{n-1}$$

   a. Appliquer $P(n)$ aux $n$ nombres $x_1,\dots ,x_{n-1},m$ et montrer que l'on obtient $\sqrt[n]{x_1\cdots x_{n-1}m}\le m$.

   b. En déduire $P(n-1)$. On traitera à part le cas $m=0$, et l'on dira précisément pourquoi il doit être traité à part.

5. Conclusion. Démontrer que $P(n)$ est vraie pour tout entier $n\ge 2$. On pourra, pour $n$ donné, choisir un entier $p$ tel que $2^p\ge n$, puis redescendre.

6. Application. Soient $a$, $b$, $c$ des réels strictement positifs. Démontrer que

   $$(a+b+c)(\frac{1}{a}+\frac{1}{b}+\frac{1}{c})\ge 9$$

Dans tout l'exercice, $E$ est un ensemble et $A$, $B$, $C$ sont des parties de $E$. On rappelle que $A\setminus B=\{x\in A;x\mathrm{\notin }B\}$.

1. Soit $x\in E$. Écrire ce que signifie $x\mathrm{\notin }B\setminus C$ sous la forme d'une phrase portant sur « $x\in B$ » et « $x\in C$ ». On prendra garde à la négation d'un « et ».

2. Démontrer, par double inclusion, l'égalité

   $$A\setminus (B\setminus C)=(A\setminus B)\cup (A\cap C)$$

   La rédaction devra suivre exactement le squelette suivant, à recopier et à compléter.

   Inclusion directe. Soit $x\in A\setminus (B\setminus C)$. Alors … . D'après la question 1, … . Distinguons deux cas. Si … , alors … , donc $x\in (A\setminus B)\cup (A\cap C)$. Si … , alors … , donc $x\in (A\setminus B)\cup (A\cap C)$. Dans les deux cas … . Ceci prouve que $A\setminus (B\setminus C)\subset (A\setminus B)\cup (A\cap C)$.

   Inclusion réciproque. Soit $x\in (A\setminus B)\cup (A\cap C)$. … . Ceci prouve que $(A\setminus B)\cup (A\cap C)\subset A\setminus (B\setminus C)$.

   Conclusion. Les deux inclusions étant établies, … .

3. Démontrer que $(A\cup B)\setminus C=(A\setminus C)\cup (B\setminus C)$.

4. Un étudiant affirme que, pour toutes parties $A$, $B$, $C$ de $E$, on a

   $$A\cup (B\setminus C)=(A\cup B)\setminus (A\cup C)$$

   Produire un contre-exemple avec $E=\{1,2,3\}$, en calculant explicitement les deux membres.

5. L'une des deux inclusions reste vraie en toute généralité. Dire laquelle et la démontrer.

6. Réparer l'énoncé de deux façons.

   a. Démontrer que $(A\cup B)\setminus (A\cup C)=B\setminus (A\cup C)$ : le membre de droite de l'étudiant se simplifie, et le $A$ qu'il y avait mis en tête ne sert à rien.

   b. Démontrer que $A\cup (B\setminus C)=(A\cup B)\setminus (C\setminus A)$ : c'est cette fois le membre de gauche qui est conservé, et l'on corrige ce que l'on retranche.

Dans tout l'exercice, $E$ est un ensemble et $A$, $B$ sont des parties de $E$. On rappelle que $\mathcal{P}(A)$ désigne l'ensemble des parties de $A$, et que $X\in \mathcal{P}(A)$ signifie exactement $X\subset A$.

1. Sur un exemple. On prend $E=\{1,2,3\}$, $A=\{1,2\}$ et $B=\{2,3\}$. Écrire en extension les six ensembles suivants, puis comparer.

   a. $\mathcal{P}(A)$ et $\mathcal{P}(B)$

   b. $\mathcal{P}(A\cap B)$ et $\mathcal{P}(A)\cap \mathcal{P}(B)$

   c. $\mathcal{P}(A\cup B)$

   d. $\mathcal{P}(A)\cup \mathcal{P}(B)$

2. Démontrer que $\mathcal{P}(A)\subset \mathcal{P}(B)$ si et seulement si $A\subset B$.

3. Démontrer que $\mathcal{P}(A\cap B)=\mathcal{P}(A)\cap \mathcal{P}(B)$.

4. Démontrer que $\mathcal{P}(A)\cup \mathcal{P}(B)\subset \mathcal{P}(A\cup B)$, puis donner un contre-exemple montrant que cette inclusion peut être stricte.

5. La question qui porte l'exercice. Démontrer que

   $$\mathcal{P}(A)\cup \mathcal{P}(B)=\mathcal{P}(A\cup B)⟺(A\subset B\text{ ou }B\subset A)$$

   Pour le sens direct, on pourra raisonner par contraposée.

On rappelle les définitions, pour une famille $(X_i{)}_{i\in I}$ de parties d'un ensemble $E$ indexée par un ensemble $I$ non vide :

$$\bigcup _{i\in I}{X}_i=\{x\in E;\mathrm{\exists }i\in I,x\in X_i\}\bigcap _{i\in I}{X}_i=\{x\in E;\mathrm{\forall }i\in I,x\in X_i\}$$

On travaille dans $E=\mathbb{R}$ et l'on pose, pour tout entier $n\ge 1$,

$$A_n=]-\frac{1}{n},\frac{1}{n}[\text{et}{B}_n=[\frac{1}{n},1]$$

Les calculs de cet exercice reposent tous sur le résultat suivant, que l'on admet ici : sa démonstration relève de l'étude de $\mathbb{R}$, menée dans le chapitre sur les suites réelles.

Propriété d'Archimède (admise). Pour tous réels $a>0$ et $b$, il existe un entier $n\ge 1$ tel que $na>b$.

1. Échauffement.

   a. Écrire $A_1$, $A_2$, $A_3$ et $B_1$, $B_2$, $B_3$ comme intervalles explicites.

   b. Démontrer que $A_{n+1}\subset A_n$ pour tout $n\ge 1$, et que $B_n\subset B_{n+1}$ pour tout $n\ge 1$.

   c. En déduire ${\displaystyle \bigcup _{n\ge 1}{A}_n}$ et ${\displaystyle \bigcap _{n\ge 1}{B}_n}$.

2. Déduire de la propriété d'Archimède que, pour tout réel $a>0$, il existe un entier $n\ge 1$ tel que ${\displaystyle \frac{1}{n}}<a$.

3. Démontrer, en rédigeant les deux inclusions, que ${\displaystyle \bigcap _{n\ge 1}{A}_n=\{0\}}$.

4. Démontrer que ${\displaystyle \bigcup _{n\ge 1}{B}_n=]0,1]}$.

5. Loi de De Morgan pour une famille quelconque. Soit $(X_i{)}_{i\in I}$ une famille de parties de $E$, avec $I$ non vide. Démontrer que

   $$\overline{\bigcup _{i\in I}{X}_i}=\bigcap _{i\in I}\overline{X_i}$$

6. Question de vigilance. À la question 3, l'intersection des $A_n$ n'est pas vide, alors que ces intervalles ouverts « rétrécissent » indéfiniment. Donner une famille $(C_n{)}_{n\ge 1}$ d'intervalles ouverts non vides, emboîtés (c'est-à-dire vérifiant $C_{n+1}\subset C_n$ pour tout $n$), dont l'intersection est vide. Démontrer les trois points, et expliquer ce qui distingue cette famille de celle des $A_n$.

Tous les ensembles de cet exercice sont finis, sauf mention contraire. On utilisera librement les deux résultats du cours suivants.

1. Soient $A$ et $B$ deux parties finies d'un ensemble. Démontrer la formule du crible à deux ensembles :

   $$\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}(A\cup B)=\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}(A)+\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}(B)-\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}(A\cap B)$$

   On pourra commencer par décomposer $A\cup B$ en trois morceaux deux à deux disjoints.

2. En déduire la formule pour trois ensembles $A$, $B$, $C$.

3. Application. Dans une promotion de $120$ étudiants, $70$ suivent l'anglais et $45$ l'espagnol, dont $20$ qui suivent les deux.

   a. Combien d'étudiants ne suivent aucune de ces deux langues ?

   b. On ajoute l'allemand, suivi par $30$ étudiants. On sait de plus que $15$ étudiants suivent anglais et allemand, $10$ suivent espagnol et allemand, et $5$ suivent les trois langues. Combien d'étudiants ne suivent aucune des trois langues ?

4. Principe des tiroirs. Démontrer par récurrence sur $n\ge 1$ la propriété $T(n)$ suivante : il n'existe aucune application injective de $\{1,\dots ,n+1\}$ dans $\{1,\dots ,n\}$.

   Indication pour l'hérédité. Soit $f:\{1,\dots ,n+2\}\to \{1,\dots ,n+1\}$ que l'on suppose injective. Distinguer selon que la valeur $n+1$ est atteinte ou non par la restriction de $f$ à $\{1,\dots ,n+1\}$, et fabriquer dans chaque cas une injection de $\{1,\dots ,n+1\}$ dans $\{1,\dots ,n\}$.

5. Forme générale. En déduire que si $X$ et $Y$ sont deux ensembles finis tels que $\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}(X)>\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}(Y)$, alors aucune application de $X$ dans $Y$ n'est injective.

6. Trois applications. Démontrer chacune des affirmations suivantes.

   a. Dans tout groupe de $13$ personnes, deux au moins sont nées le même mois.

   b. Parmi $6$ entiers quelconques, deux au moins ont le même reste dans la division par $5$.

   c. Parmi les parties de $\{1,2,3,4\}$, deux parties distinctes au moins ont la même somme d'éléments (la somme des éléments de $\mathrm{\varnothing }$ étant $0$). En exhiber deux.

Une « formule » ne suffit pas à définir une application : encore faut-il qu'elle attribue à chaque élément de l'ensemble de départ une et une seule valeur, et que cette valeur appartienne à l'ensemble d'arrivée annoncé.

On rappelle la notation du chapitre pour les classes de congruence modulo $5$ : pour $x\in \mathbb{Z}$,

$$\mathrm{c}\mathrm{l}(x)=\{y\in \mathbb{Z};5\text{ divise }y-x\}$$

et le cours donne l'équivalence $\mathrm{c}\mathrm{l}(x)=\mathrm{c}\mathrm{l}(x^{\mathrm{\prime }})⟺5\text{ divise }x-x^{\mathrm{\prime }}$. On écrit $\mathrm{c}\mathrm{l}(x)$ et jamais $\bar{x}$ : dans tout le chapitre, la barre est réservée au complémentaire.

1. Énoncer précisément les deux conditions à vérifier pour qu'une correspondance $x\mapsto \dots$ définisse bien une application de $D$ dans $F$. Ajouter la condition supplémentaire qui apparaît lorsque l'élément de départ est décrit par un représentant (une fraction, une classe de congruence).

2. Les correspondances suivantes définissent-elles des applications ? Répondre pour chacune en justifiant, et, lorsque la réponse est non, dire si l'on peut réparer la définition.

   a. $f:\mathbb{Q}\to \mathbb{Z}$, ${\displaystyle \frac{p}{q}}\mapsto p+q$.

   b. $g:\mathbb{Z}\to \{0,1,2,3,4\}$, $x\mapsto$ le reste de la division euclidienne de $x$ par $5$.

   c. $h:\mathbb{R}\to \mathbb{R}$, $x\mapsto$ l'unique réel $y$ tel que $y^2=x$.

   d. $k$, définie sur l'ensemble des classes modulo $5$ par $k(\mathrm{c}\mathrm{l}(x))=\mathrm{c}\mathrm{l}(x^2)$.

   e. $\mathrm{\ell }$, définie sur l'ensemble des classes modulo $5$ par $\mathrm{\ell }(\mathrm{c}\mathrm{l}(x))=\mathrm{c}\mathrm{l}(2^x)$ pour tout $x\in \mathbb{N}$ (on se restreint aux représentants entiers naturels, faute de quoi $2^x$ ne serait même pas un entier).

3. Dresser le tableau des valeurs de $k$ sur les cinq classes, et dire si $k$ est injective, surjective.

4. Pour finir. Notons ${\mathrm{c}\mathrm{l}}_4(x)$ la classe de $x$ modulo $4$ et ${\mathrm{c}\mathrm{l}}_5(x)$ sa classe modulo $5$. Démontrer que la correspondance

   $$\mathrm{\Lambda }({\mathrm{c}\mathrm{l}}_4(x))={\mathrm{c}\mathrm{l}}_5\left(2^x\right)(x\in \mathbb{N})$$

   est, elle, bien définie. Expliquer en une phrase pourquoi $4$ marche là où $5$ échouait.

Dans tout l'exercice, $E$ est un ensemble non vide et $A$ est une partie de $E$ fixée. Le complémentaire d'une partie $X$ dans $E$ est noté $\bar{X}$.

Consigne de rédaction, valable pour les cinq études. Chaque réponse doit commencer par la phrase attendue :

• pour l'injectivité : « soient $x$ et $x^{\mathrm{\prime }}$ tels que $f(x)=f(x^{\mathrm{\prime }})$ », puis on démontre $x=x^{\mathrm{\prime }}$ ;
• pour la surjectivité : « soit $y$ dans l'ensemble d'arrivée, cherchons un antécédent », puis on en exhibe un ;
• pour réfuter, on donne deux éléments distincts de même image, ou un élément sans antécédent, et on le vérifie par le calcul.

1. $\phi :\mathcal{P}(E)\to \mathcal{P}(E)$, $X\mapsto \bar{X}$. Étudier l'injectivité et la surjectivité, puis calculer $\phi \circ \phi$ et en déduire la réciproque de $\phi$ lorsqu'elle existe.

2. $\psi :\mathcal{P}(E)\to \mathcal{P}(A)$, $X\mapsto X\cap A$. Vérifier d'abord que $\psi$ arrive bien dans $\mathcal{P}(A)$. Puis montrer que $\psi$ est toujours surjective, et déterminer à quelle condition sur $A$ elle est injective.

3. $s:\mathbb{N}\to \mathbb{N}$ définie par $s(0)=0$ et $s(n)=n-1$ pour $n\ge 1$.

4. $t:\mathbb{Z}\to \mathbb{Z}$, $n\mapsto 3n+1$. Préciser l'image de $t$.

5. $u:\{1,2,3\}\to \{a,b\}$ donnée par le tableau suivant.

   $x$	$1$	$2$	$3$
   $u(x)$	$a$	$b$	$a$

6. Le sens inverse. On considère $w:\mathbb{R}\to \mathbb{R}$, $x\mapsto x^3-x$.

   a. Montrer que $w$ n'est pas injective en exhibant trois antécédents de $0$.

   b. Démontrer que la restriction de $w$ à $[1,+\mathrm{\infty }[$ est injective. On pourra factoriser $w(y)-w(x)$.

   c. Quel ensemble d'arrivée faut-il donner à $w$ pour la rendre surjective ? Quel ensemble de départ pour la rendre injective ? Répondre en distinguant ce qui se démontre de ce que l'on admet.

On note $h:\mathbb{R}\to \mathbb{Z}$ l'application partie entière : pour tout réel $x$, $h(x)=\lfloor x\rfloor$ est l'unique entier $n$ tel que $n\le x<n+1$.

On rappelle les deux définitions, pour $f:D\to F$, $A\subset D$ et $B\subset F$ :

$$f(A)=\{f(x);x\in A\}{f}^{-1}(B)=\{x\in D;f(x)\in B\}$$

L'écriture $f^{-1}(B)$ ne suppose pas que $f$ soit bijective : c'est une notation d'ensemble, et non l'image par une application réciproque. La question 7 y revient.

1. Échauffement. Calculer $\lfloor \mathrm{2,5}\rfloor$, $\lfloor 3\rfloor$, $\lfloor -\mathrm{1,5}\rfloor$ et $\lfloor -3\rfloor$.

2. Question de rédaction. Soient $A$ une partie de $\mathbb{R}$ et $J$ une partie de $\mathbb{Z}$. Écrire, avec des quantificateurs, les deux énoncés qu'il faut exactement démontrer pour établir $h(A)=J$. Dire lequel des deux est le plus souvent bâclé.

3. Déterminer $h([0,\mathrm{2,5}[)$, en rédigeant les deux inclusions selon le modèle de la question 2.

4. Déterminer $h^{-1}(\{3\})$, puis $h^{-1}(2\mathbb{Z})$ où $2\mathbb{Z}=\{2k;k\in \mathbb{Z}\}$, puis $h^{-1}(\mathbb{Z})$.

5. Déterminer $h([-\mathrm{1,5},\mathrm{1,5}])$.

6. On considère maintenant $k:\mathbb{Z}\to \mathbb{Z}$, $n\mapsto n^2$. Déterminer $k^{-1}(\{0,1,4,5\})$ et $k(\{-3,\dots ,3\})$.

7. L'application $h$ est-elle bijective ? Expliquer alors pourquoi l'écriture $h^{-1}(\{3\})$ a malgré tout un sens.

On considère l'application $f:\{1,2,3,4\}\to \{a,b,c\}$ définie par le tableau suivant.

Dans tout l'exercice, $A$ et $B$ désignent des parties de l'ensemble de départ, et $C$ et $D$ des parties de l'ensemble d'arrivée.

1. Calculs. Déterminer, en écrivant chaque ensemble en extension :

   a. $f(A\cap B)$ et $f(A)\cap f(B)$ pour $A=\{1\}$ et $B=\{2\}$ ;

   b. $f(A\cup B)$ et $f(A)\cup f(B)$ pour $A=\{1\}$ et $B=\{3\}$ ;

   c. $f^{-1}(C\cap D)$ et $f^{-1}(C)\cap f^{-1}(D)$ pour $C=\{a,b\}$ et $D=\{b,c\}$ ;

   d. $f^{-1}(C\cup D)$ et $f^{-1}(C)\cup f^{-1}(D)$ pour les mêmes $C$ et $D$.

2. Pour chacune des quatre relations ci-dessus, chercher des parties qui mettent l'inclusion en défaut, c'est-à-dire pour lesquelles les deux membres diffèrent. Combien de relations peut-on ainsi mettre en défaut ?

3. Conjecture. Énoncer, pour chacune des quatre relations, ce que l'on pense être vrai pour une application quelconque : égalité, ou inclusion dans un sens seulement (et lequel).

4. Démontrer, pour une application quelconque $f:X\to Y$ :

   a. $f(A\cap B)\subset f(A)\cap f(B)$ ;

   b. $f^{-1}(C\cap D)=f^{-1}(C)\cap f^{-1}(D)$, par équivalences.

5. Le cœur de l'exercice. Expliquer pourquoi la rédaction de la question 4. b ne peut pas servir de modèle à celle de la question 4. a : quel est exactement le pas de raisonnement qui passe dans un cas et pas dans l'autre ?

6. Démontrer, pour une application quelconque, les deux inclusions $A\subset f^{-1}(f(A))$ et $f(f^{-1}(C))\subset C$, puis montrer sur l'application $f$ du tableau que chacune peut être stricte.

Dans les questions 1 à 4, $f:E\to F$ et $g:F\to G$ sont deux applications, et l'on s'intéresse à ce que les propriétés de $g\circ f:E\to G$ imposent à $f$ et à $g$. Les questions 5 et 6 portent sur le cas particulier des ensembles finis.

On dispose des six couples suivants, tous entre ensembles finis explicites.

Couple 1. $E=\{1,2\}$, $F=\{a,b,c\}$, $G=\{u,v\}$ ; $f(1)=a$, $f(2)=b$ ; $g(a)=u$, $g(b)=v$, $g(c)=u$.

Couple 2. $E=\{1,2\}$, $F=\{a,b,c\}$, $G=\{u,v\}$ ; $f(1)=a$, $f(2)=c$ ; $g(a)=u$, $g(b)=v$, $g(c)=u$.

Couple 3. $E=\{1,2\}$, $F=\{a,b\}$, $G=\{u,v\}$ ; $f(1)=a$, $f(2)=b$ ; $g(a)=v$, $g(b)=u$.

Couple 4. $E=\{1,2,3\}$, $F=\{a,b\}$, $G=\{u,v,w\}$ ; $f(1)=a$, $f(2)=a$, $f(3)=b$ ; $g(a)=u$, $g(b)=v$.

Couple 5. $E=\{1,2,3\}$, $F=\{a,b,c\}$, $G=\{u,v\}$ ; $f(1)=a$, $f(2)=b$, $f(3)=c$ ; $g(a)=u$, $g(b)=v$, $g(c)=v$.

Couple 6. $E=\{1,2\}$, $F=\{a,b\}$, $G=\{u,v,w\}$ ; $f(1)=a$, $f(2)=b$ ; $g(a)=u$, $g(b)=v$.

1. Pour chacun des six couples, calculer $g\circ f$ et dire, pour les trois applications $g\circ f$, $f$ et $g$, lesquelles sont injectives et lesquelles sont surjectives.

2. En déduire la valeur de vérité des quatre cases du tableau suivant, où chaque case se lit « si $g\circ f$ est … , alors … ».

   	conclusion sur $f$	conclusion sur $g$
   $g\circ f$ injective	$f$ est injective	$g$ est injective
   $g\circ f$ surjective	$f$ est surjective	$g$ est surjective

3. Démontrer les deux implications vraies, dans le cas de deux applications quelconques.

4. Réfuter les deux implications fausses, en s'appuyant sur celui des six couples qui convient et en vérifiant explicitement les valeurs.

5. Soient $E$ et $F$ deux ensembles finis de même cardinal $n$, et $f:E\to F$. Démontrer les équivalences

   $$f\text{ injective\hspace{0.25em}\hspace{0.05em}}⟺f\text{ surjective\hspace{0.25em}\hspace{0.05em}}⟺f\text{ bijective}$$

   On s'appuiera sur le principe des tiroirs démontré à l'exercice 22 (question 5), que l'on n'a pas à redémontrer. Pour le sens « surjective donne injective », on pourra choisir un antécédent pour chaque élément de $F$ et étudier l'application ainsi construite.

6. Montrer que l'hypothèse de finitude est indispensable, en donnant sur $\mathbb{N}$ une application injective non surjective, et une application surjective non injective.