Ensembles & Applications

Faire des dessins !

1. On a $\displaystyle \phi(\emptyset)=(\emptyset\cap A, \emptyset\cap B)=(\emptyset, \emptyset)$ et aussi $\displaystyle \phi(E\setminus (A \cup B))=(\emptyset, \emptyset)$.
2. Supposons que $\displaystyle E=A\cup B$ avec $\displaystyle A\cap B=\emptyset$. Alors pour tout $\displaystyle X\in\mathcal P(E)$, $\displaystyle X=(X\cap A)\cup (X\cap B)$ (Faire un dessin pour s’en convaincre !). Ceci montre que $\displaystyle \phi$ est injective en écrivant simplement la définission de l’injectivité.
3. La question est existe-il $\displaystyle X$ tel que $\displaystyle X\cap A=\emptyset$ et $\displaystyle X\cap B=B$ ? Si oui, cela veut dire que $\displaystyle X$ et $\displaystyle A$ sont disjoints, et que $\displaystyle X$ contient $\displaystyle B$. Ceci est possible si $\displaystyle A$ et $\displaystyle B$ sont disjoints.
4. Si $\displaystyle A$ et $\displaystyle B$ sont disjoints, on voit que $\displaystyle \phi$ est surjective.

1. Elle est fausse, à moins que $\displaystyle F$ ne contienne qu’un élément.
2. Elle est vraie (par définition de la notion d’application).
3. Elle est fausse, à moins que $\displaystyle F$ ne contienne qu’un élément.
4. Vraie puisque la 2. est vraie.
5. C’est la même assertion que la 1. (permuter deux $\displaystyle \forall$ consécutifs ne change pas la valeur de vérité d’une assertion).
6. C’est la définition d’application surjective.
7. C’est la définition d’application constante.
8. C’est la même assertion que la 4. (permuter deux $\displaystyle \exists$ consécutifs ne change pas la valeur de vérité d’une assertion).

• Toujours penser à des choses simples 👉 Que dire de $\displaystyle f(0)$ ?
• Trouver des récurrences (😱 plus facile à dire qu’à faire !)
• Propriété fondamentale de $\displaystyle \N$ 👉 Toute partie non vide possède un plus petit élément.

Nous ne faisons que traduire la très jolie solution donnée dans ce post sur math.stackexchange, en donnant un peu plus de détails pour faciliter la lecture.

1. Montrons que si $\displaystyle f(k)=0$ alors $\displaystyle k=0$. Supposons que $\displaystyle f(k)=0$ et que $\displaystyle k>0$. Alors $\displaystyle 0=f(k)>f(f(k-1))$, ce qui contredit que $\displaystyle f$ est à valeurs dans $\displaystyle \N$.
2. Montrons que $\displaystyle f(0)=0$. Soit $\displaystyle 𝑆=\{𝑓(𝑘), 𝑘>0\}$. Soit $\displaystyle a$ le plus petit entier de $\displaystyle S$. Alors il existe $\displaystyle k>0$ tel que
   $\displaystyle 𝑎=𝑓(𝑘)>𝑓(𝑓(𝑘−1))$. Donc cela force à avoir $\displaystyle 𝑓(𝑘−1)=0$, car sinon $\displaystyle 𝑓(𝑓(𝑘−1))$ serait dans $\displaystyle S$, ce qui n’est pas possible car $\displaystyle a$ est le plus petit élément. Donc $\displaystyle k-1=0$ par 1), d’où $\displaystyle k=1$ et $\displaystyle f(0)=0$.
3. Montrons que $\displaystyle f(n)=n$. Supposons, par récurrence forte, que pour tout $\displaystyle m\in\{0,\cdots,n-1\}$, $\displaystyle f(k)=m \iff k=m$. Pour $\displaystyle n=1$, c’est ce qui a été démontré en 1) et 2), montrant ainsi l’initialisation. On procède alors de la même manière que dans 1) et 2).
   Si $\displaystyle f(k)=n$ alors $\displaystyle 𝑓(𝑓(𝑘−1))<𝑛$. Notons $\displaystyle m=f(f(k-1))$. Comme $\displaystyle m\le n-1$, on a par l’hypothèse de récurrence que $\displaystyle m=f(k-1)$, et en recommençant l’argument : $\displaystyle m=k-1$. Ainsi $\displaystyle k-1<n$ et $\displaystyle k<n+1$, ce qui donne $\displaystyle k=n$. En effet on ne peut pas avoir $\displaystyle k<n$ car on tomberait dans l’hypothèse de récurrence qui donnerait $\displaystyle f(k)=k<n$, ce qui n’est pas possible car on a supposé $\displaystyle f(k)=n$ (!).
   Soit $\displaystyle T=\{𝑓(𝑘),𝑘>𝑛\}$ et $\displaystyle a$ le plus petit nombre dans $\displaystyle T$. Alors il existe $\displaystyle 𝑘>𝑛$ tel que $\displaystyle a=𝑓(𝑘)>𝑓(𝑓(𝑘−1))$. Donc nécessairement $\displaystyle 𝑓(𝑘−1)\le 𝑛$. Mais si $\displaystyle 𝑓(𝑘−1)<𝑛$, alors $\displaystyle 𝑓(𝑘−1)=𝑘−1$ par l’hypothèse de récurrence, et donc $\displaystyle 𝑘\le 𝑛$. Or $\displaystyle 𝑘>𝑛$. Ainsi, $\displaystyle 𝑓(𝑘−1)=𝑛$, et donc $\displaystyle 𝑘=𝑛+1$ par l’argument précédent. Finalement en réinjectant dans $\displaystyle f$, il vient $\displaystyle 𝑓(𝑛)=𝑛$, ce qui achève la récurrence.

C’est un pur exercice de réflexion : pas de méthode générale. …
👉 Analyser, petit à petit, ce qu’on peut dire des valeur de $\displaystyle f$. Que peut valoir $\displaystyle f(0)$ ? $\displaystyle f(1)$ ? Ensuite ?

$\displaystyle \bullet$ Montrons que $\displaystyle f(0)=0$.
Supposons, par l’absurde que $\displaystyle f(0)>0$. Comme $\displaystyle f$ est strictement croissante on a donc $\displaystyle f(f(0))>f(0)$. Or $\displaystyle f(0)\in\N$ donc $\displaystyle f(f(0))>0$. Ceci contredit l’hypothèse $\displaystyle f(f(0))=0$.
$\displaystyle \bullet$ Montrons que $\displaystyle f(1)=2$.
On a déjà $\displaystyle f(1)>f(0)=0$.
Supposons, par l’absurde que $\displaystyle f(1)\neq 2$.
Si $\displaystyle f(1)=1$ alors $\displaystyle f(f(1))=f(1)$ donc $\displaystyle f(1)=3$. Contradiction.
Si $\displaystyle f(1)>2$ alors $\displaystyle f(f(1))>f(2)$ donc $\displaystyle f(2)<3$. Contradiction avec $\displaystyle f(1)>2$ (car $\displaystyle f$ est strictement croissante).
$\displaystyle \bullet$ Donc $\displaystyle f(2)=f(f(1))=3$.
$\displaystyle \bullet$ Donc $\displaystyle f(3)=f(f(2))=6$.
$\displaystyle \bullet$ Donc $\displaystyle f(6)=f(f(3))=9$.
$\displaystyle \bullet$ Donc $\displaystyle f(9)=f(f(6))=18$.
$\displaystyle \bullet$ Donc $\displaystyle f(18)=f(f(9))=27$.
$\displaystyle \bullet$ Enfin on observe que $$18=f(9)<f(10)<f(11)<\dots<f(18)=27$$
donc nécessairement $\displaystyle (f(9),f(10),f(11),\dots,f(18))=(18,19,20,\dots,27)$. En particulier $\displaystyle f(16)=25$.

Quelles informations donnent les hypothèses sur les valeurs de $\displaystyle f(n)$ ? Pour commencer, que peut valoir $\displaystyle f(0)$ ? $\displaystyle f(1)$ ? Ensuite ?

Soit $\displaystyle f$ une application vérifiant ces conditions.
Montrons par récurrence forte que pour tout $\displaystyle n\in\N$, $\displaystyle f(n)=n$.
$\displaystyle \bullet$ Puisque $\displaystyle f$ est surjective, $\displaystyle 0$ doit avoir un antécédent par $\displaystyle f$.
Or pour $\displaystyle n\geq 1$, $\displaystyle f(n)\geq n\geq 1$ donc $\displaystyle f(n)\neq 0$. Donc nécessairement $\displaystyle f(0)=0$.
$\displaystyle \bullet$ Soit $\displaystyle n\in\N$. Supposons que pour tout $\displaystyle k\in[\![0,n]\!]$, $\displaystyle f(k)=k$.
Alors $\displaystyle n+1$ doit avoir un antécédent par $\displaystyle f$.
Or pour $\displaystyle k\leq n$ on a $\displaystyle f(k)=k$ donc $\displaystyle f(k)\neq n+1$. Par ailleurs pour $\displaystyle k\geq n+2$ on a $\displaystyle f(k)\geq k\geq n+2$ donc $\displaystyle f(k)\neq n+1$. Donc nécessairement $\displaystyle f(n+1)=n+1$.

Conclusion. Si $\displaystyle f$ vérifie les conditions de l’énoncé on a nécessairement $\displaystyle f=\mathrm{id}_\N$.
Réciproquement l’application $\displaystyle \mathrm{id}_\N$ vérifie ces conditions, et c’est donc la seule.

Quelles informations donnent les hypothèses sur les valeurs de $\displaystyle f(n)$ ? Pour commencer, que peut valoir $\displaystyle f(0)$ ? $\displaystyle f(1)$ ? Ensuite ?

Soit $\displaystyle f$ une application vérifiant ces conditions.
Montrons par récurrence forte que pour tout $\displaystyle n\in\N$, $\displaystyle f(n)=n$.
$\displaystyle \bullet$ Puisque $\displaystyle f$ est à valeurs dans $\displaystyle \N$, l’hypothèse $\displaystyle f(0)\leq 0$ entraîne $\displaystyle f(0)=0$.
$\displaystyle \bullet$ Soit $\displaystyle n\in\N$. Supposons que pour tout $\displaystyle k\in[\![0,n]\!]$, $\displaystyle f(k)=k$.
Alors d’une part $\displaystyle f(n+1)\leq n+1$, et d’autre part, $\displaystyle f$ étant injective, $\displaystyle f(n+1)\notin\{f(0),\dots,f(n)\}$.
Par hypothèse de récurrence, $\displaystyle f(n+1)\notin\{0,\dots,n\}$. Finalement $\displaystyle f(n+1)=n+1$.

Conclusion. Si $\displaystyle f$ vérifie les conditions de l’énoncé on a nécessairement $\displaystyle f=\mathrm{id}_\N$.
Réciproquement l’application $\displaystyle \mathrm{id}_\N$ vérifie ces conditions, et c’est donc la seule.

C’est un exercice de raisonnement.
👉 dérouler les réflexes de la logique. Traduire systématiquement les hypothèses en revenant aux définitions.

$\displaystyle \bullet$ Supposons $\displaystyle f$ injective.
Soit $\displaystyle x\in E$. On a $\displaystyle f(x)=f(f(f(x)))$. L’injectivité de $\displaystyle f$ donne donc $\displaystyle x=f(f(x))$. Donc $\displaystyle f(x)$ est un antécédent de $\displaystyle x$ par $\displaystyle f$. Ceci montre que $\displaystyle f$ est surjective.
$\displaystyle \bullet$ Supposons réciproquement $\displaystyle f$ surjective.
Soit $\displaystyle x,y\in E$ tels que $\displaystyle f(x)=f(y)$.
$\displaystyle f$ étant surjective, il existe $\displaystyle x',y'\in E$ tels que $\displaystyle x=f(x')$ et $\displaystyle y=f(y')$.
Pour la même raison, il existe $\displaystyle x'',y''\in E$ tels que $\displaystyle x'=f(x'')$ et $\displaystyle y'=f(y'')$.
Ainsi $\displaystyle f(f(f(x'')))=f(f(f(y'')))$. Or $\displaystyle f\circ f\circ f=f$ donc $\displaystyle f(x'')=f(y'')$.
Ainsi $\displaystyle x'=y'$ et par conséquent $\displaystyle x=f(x')=f(y')=y$. Ceci montre que $\displaystyle f$ est injective.

Examiner chaque situation méthodiquement :
$\displaystyle \to$ l’application peut-elle prendre toutes les valeurs de l’ensemble d’arrivée ?
$\displaystyle \to$ l’application peut-elle prendre plusieurs fois une même valeur ?

• $\displaystyle 1/2$ n’a pas d’antécédent par $\displaystyle f$ donc $\displaystyle f$ n’est pas surjective.
  $\displaystyle f(0)=f(1/2)$ donc $\displaystyle f$ n’est pas injective.
• Soit $\displaystyle (a,b)\in\R^2$.
  On a l’équivalence : $\displaystyle g(x,y)=(a,b)\Leftrightarrow\begin{cases}2x+y=a\\x-3y=b\end{cases}\Leftrightarrow\begin{cases}x=\frac{3a+b}{7}\\y=\frac{a-2b}{7}\end{cases}$.
  Donc $\displaystyle (a,b)$ a un unique antécédent par $\displaystyle g$. $\displaystyle g$ est surjective.
• $\displaystyle 2$ n’a pas d’antécédent par $\displaystyle u$. Donc $\displaystyle u$ n’est pas surjective.
  Soit $\displaystyle k,\ell\in\N$ tels que $\displaystyle u(k)=u(\ell)$. Alors $\displaystyle k^2=\ell^2$. En prenant la racine carrée on obtient $\displaystyle k=\ell$.
  Donc $\displaystyle u$ est injective.
• $\displaystyle \varnothing$ n’a pas d’antécédent par $\displaystyle v$. Donc $\displaystyle v$ n’est pas surjective.
  $\displaystyle v(\varnothing)=v(\{0\})=\{0\}$, donc $\displaystyle v$ n’est pas injective.

Examiner chaque situation méthodiquement :
$\displaystyle \to$ l’application peut-elle prendre toutes les valeurs de l’ensemble d’arrivée ?
$\displaystyle \to$ l’application peut-elle prendre plusieurs fois une même valeur ?

$\displaystyle \bullet$ Soit $\displaystyle x\in\R$. On a $\displaystyle f(x,0)=x$ donc $\displaystyle (x,0)$ est un antécédent de $\displaystyle x$. Ainsi $\displaystyle f$ est surjective.
$\displaystyle f(1,0)=f(0,1)$ donc $\displaystyle f$ n’est pas injective.
$\displaystyle \bullet$ $\displaystyle g$ est continue sur $\displaystyle \R$, avec $\displaystyle \lim_{x\to -\infty}g(x)=-\infty$ et $\displaystyle \lim_{x\to +\infty}g(x)=+\infty$. Ainsi d’après le théorème des valeurs intermédiaires, pour $\displaystyle y\in\R$ il existe $\displaystyle x\in\R$ tel que $\displaystyle g(x)=y$. Donc $\displaystyle g$ est surjective.
$\displaystyle g(0)=g(1)=0$ donc $\displaystyle g$ n’est pas injective.
$\displaystyle \bullet$ $\displaystyle u$ est continue, strictement croissante (somme de deux fonctions strictement croissantes), avec $\displaystyle \lim_{x\to -\infty}u(x)=-\infty$ et $\displaystyle \lim_{x\to +\infty}u(x)=+\infty$. Par théorème de la bijection monotone, $\displaystyle g$ est donc bijective.
$\displaystyle \bullet$ $\displaystyle v$ est surjective par définition de $\displaystyle \Q$ : pour $\displaystyle q\in\Q$ il existe $\displaystyle a\in\Z$, $\displaystyle b\in\N^*$ tels que $\displaystyle q=\frac ab$.
On a $\displaystyle v(0,1)=v(0,2)$ donc $\displaystyle v$ n’est pas injective.

Examiner chaque situation méthodiquement :
$\displaystyle \to$ l’application peut-elle prendre toutes les valeurs de l’ensemble d’arrivée ?
$\displaystyle \to$ l’application peut-elle prendre plusieurs fois une même valeur ?

$\displaystyle \bullet$ On remarque que $\displaystyle \forall A\in\mathcal P(\N),~f(f(A))=A$. Ainsi $\displaystyle f\circ f=\mathrm{id}_{\mathcal P(\N)}$, donc $\displaystyle f$ est bijective (et $\displaystyle f^{-1}=f$).
$\displaystyle \bullet$ Pour $\displaystyle a\in\N$, on a $\displaystyle g(a)=a$, donc $\displaystyle a$ est un antécédent de $\displaystyle a$. Ainsi $\displaystyle g$ est surjective.
On a $\displaystyle g(-1)=g(1)$, donc $\displaystyle g$ n’est pas surjective.
$\displaystyle \bullet$ Soit $\displaystyle k\in [\![0;11]\!]$. L’ensemble $\displaystyle A=\{0,1,\dots,k-1\}$ vérifie $\displaystyle u(A)=k$. Donc $\displaystyle u$ est surjective.
$\displaystyle u(\{0\})=u(\{1\})=1$, donc $\displaystyle u$ n’est pas injective.
$\displaystyle \bullet$ $\displaystyle \varnothing$ n’a pas d’antécédent par $\displaystyle v$, donc $\displaystyle v$ n’est pas surjective.
Soit $\displaystyle x,y\in\Z$ tels que $\displaystyle \{x\}=\{y\}$. On a alors évidemment $\displaystyle x=y$. Donc $\displaystyle v$ est injective.

Commencer par faire un dessin (patates) peut aider à comprendre la situation.

La première hypothèse entraîne : $$(A\cup B)\setminus A = (A\cup C)\setminus A,$$
autrement dit $$A^c\cap B = A^c\cap C.$$
Par ailleurs $\displaystyle B=(A\cap B)\cup (A^c\cap B)$, et de même $\displaystyle C=(A\cap C)\cup (A^c\cap C)$. Donc $\displaystyle B=C$.