Ensembles et applications

1Ensembles, appartenance, inclusion

Définition. Un ensemble $E$ est une collection d’objets, appelés ses éléments ; on écrit $x\in E$ si $x$ est un élément de $E$, et $x\notin E$ sinon. L’ensemble vide, noté $\varnothing$, est l’ensemble n’ayant aucun élément. Toute étude systématique de la théorie des ensembles est hors programme : on se contente de ce vocabulaire.

Notation. Un ensemble se décrit en extension, par la liste de ses éléments (l’ordre et les répétitions n’y jouent aucun rôle : $\ens{2\,;3\,;3}=\ens{3\,;2}$), ou en compréhension, par une propriété : $\ens{x\in\R,\ x^{2}<4}=\intoo{-2}{2}$.

Définition. Soient $A$ et $B$ deux ensembles. On dit que $A$ est inclus dans $B$, ou que $A$ est une partie (ou un sous-ensemble) de $B$, et l’on note $A\subset B$, lorsque

On note $A\not\subset B$ la négation : il existe $x\in A$ tel que $x\notin B$.

Propriété. Si $A\subset B$ et $B\subset C$, alors $A\subset C$ (transitivité) ; de plus $\varnothing\subset A$ et $A\subset A$.

Théorème — double inclusion. Pour deux ensembles $A$ et $B$ : $\ A=B\iff\bigl(A\subset B\ \text{ et }\ B\subset A\bigr)$.

Méthode — montrer une égalité d’ensembles. deux stratégies, et deux seulement. (i) Double inclusion : « soit $x\in A$ ; montrons $x\in B$ », puis la réciproque. (ii) Chaîne d’équivalences : « $x\in A\iff\dots\iff x\in B$ », ce qui traite les deux inclusions d’un coup, mais n’est possible que si chaque étape est bien une équivalence.

Définition. L’ensemble des parties de $E$ est $\ \mathcal{P}(E)=\ens{A,\ A\subset E}$. Ses éléments sont des ensembles : $\ A\in\mathcal{P}(E)\iff A\subset E$.

2Opérations sur les parties d’un ensemble

Définition. Soient $A$ et $B$ deux parties d’un ensemble $E$.

Propriété — règles de calcul. Pour $A$, $B$, $C$ parties de $E$ :

Idée de preuve. Chaque ligne traduit une règle de logique du chapitre 1 (distributivité de « et » sur « ou », négation d’une conjonction, contraposition) ; on la démontre par équivalences sur l’appartenance d’un $x$ quelconque.

Définition. Soit $E$ un ensemble. Une famille $(A_{i})_{i\in I}$ de parties de $E$ est un recouvrement de $E$ si $\bigcup_{i\in I}A_{i}=E$. C’est une partition de $E$ si, de plus, les $A_{i}$ sont non vides et deux à deux disjointes :

Autrement dit : tout élément de $E$ appartient à un et un seul des $A_{i}$.

Définition. Le produit cartésien de $E$ et $F$ est $\ E\times F=\ens{(x,y),\ x\in E\ \text{et}\ y\in F}$, ensemble des couples. On note $E^{2}=E\times E$ et, plus généralement, $E_{1}\times\dots\times E_{n}$ l’ensemble des $n$-uplets $(x_{1},\dots,x_{n})$ avec $x_{i}\in E_{i}$.

Propriété. $(x,y)=(x',y')\iff\bigl(x=x'\ \text{et}\ y=y'\bigr)$ : dans un couple, l’ordre compte. On a $E\times F=\varnothing\iff\bigl(E=\varnothing\ \text{ou}\ F=\varnothing\bigr)$, et $(A\times B)\cap(C\times D)=(A\cap C)\times(B\cap D)$.

3Applications

Définition. Une application $f$ de $E$ dans $F$ associe à chaque $x\in E$ un unique $f(x)\in F$ ; $E$ est l’ensemble de départ, $F$ l’ensemble d’arrivée, $\Gamma_{f}=\ens{\bigl(x,f(x)\bigr),\ x\in E}\subset E\times F$ le graphe de $f$, et $\mathcal{F}(E,F)=F^{E}$ l’ensemble de ces applications. Le programme ne distingue pas fonction et application. Une famille $(u_{i})_{i\in I}$ d’éléments de $F$ est une application $I\to F$ ; une suite est une famille indexée par $\N$.

Définition. L’identité de $E$ est $\mathrm{id}_{E}:E\to E$, $x\mapsto x$. La fonction indicatrice d’une partie $A$ de $E$ est

Propriété. Pour $A,B\in\mathcal{P}(E)$ : $\ \mathbf{1}_{A\cap B}=\mathbf{1}_{A}\mathbf{1}_{B}$, $\ \mathbf{1}_{\overline{A}}=1-\mathbf{1}_{A}$, $\ \mathbf{1}_{A\cup B}=\mathbf{1}_{A}+\mathbf{1}_{B}-\mathbf{1}_{A}\mathbf{1}_{B}$, et $\ A=B\iff\mathbf{1}_{A}=\mathbf{1}_{B}$. L’application $A\mapsto\mathbf{1}_{A}$ est donc une injection de $\mathcal{P}(E)$ dans $\mathcal{F}\bigl(E,\ens{0\,;1}\bigr)$ ; c’est même une bijection.

Méthode — identité ensembliste par les indicatrices. traduire chaque membre en expression polynomiale en $\mathbf{1}_{A},\mathbf{1}_{B},\dots$, puis identifier les deux polynômes en tenant compte de $\mathbf{1}_{A}^{2}=\mathbf{1}_{A}$.

Définition. Soient $f:E\to F$ et $A\subset E$. La restriction de $f$ à $A$ est $f_{|A}:A\to F$, $x\mapsto f(x)$. Si $g:A\to F$ et $f:E\to F$ vérifient $f_{|A}=g$, on dit que $f$ est un prolongement de $g$ à $E$.

4Image directe, image réciproque

Définition. Soit $f:E\to F$. Pour $A\subset E$ et $B\subset F$, on pose

On appelle image de $f$ l’ensemble $\operatorname{Im} f=f(E)\subset F$.

Théorème — image réciproque : elle commute avec tout. Soient $f:E\to F$ et $B,B'\subset F$. Alors

et $B\subset B'\implies f^{-1}(B)\subset f^{-1}(B')$.

Idée de preuve (exigible). $x\in f^{-1}(B\cup B')\iff f(x)\in B\cup B'\iff\bigl(f(x)\in B$ ou $f(x)\in B'\bigr)\iff x\in f^{-1}(B)\cup f^{-1}(B')$ : la condition « $f(x)\in\cdot$ » se distribue sur les connecteurs logiques ; idem pour $\cap$ et pour le complémentaire.

Théorème — image directe : une seule inclusion pour $\cap$. Soient $f:E\to F$ et $A,A'\subset E$. Alors

L’inclusion encadrée peut être stricte.

Contre-exemple (exigible). Pour $f:\R\to\R$, $x\mapsto x^{2}$, $A=\ens{-1}$ et $A'=\ens{1}$ : $A\cap A'=\varnothing$ donc $f(A\cap A')=\varnothing$, alors que $f(A)\cap f(A')=\ens{1}$.

Théorème — aller-retour. Soient $f:E\to F$, $A\subset E$ et $B\subset F$. Alors

ces inclusions pouvant être strictes. De plus $f\bigl(f^{-1}(B)\bigr)=B\cap\operatorname{Im} f$.

5Composition, injections, surjections, bijections

Définition. Si $f:E\to F$ et $g:F\to G$, la composée est $g\circ f:E\to G$, $x\mapsto g\bigl(f(x)\bigr)$. La composition est associative ($h\circ(g\circ f)=(h\circ g)\circ f$) et admet les identités comme neutres ($f\circ\mathrm{id}_{E}=f=\mathrm{id}_{F}\circ f$), mais elle n’est pas commutative.

Définition. Soit $f:E\to F$.

Méthode — dans la pratique. pour l’injectivité, partir de $f(x)=f(x')$ et calculer jusqu’à $x=x'$. Sinon, fixer $y\in F$ et résoudre $f(x)=y$ d’inconnue $x\in E$ : le nombre de solutions donne les trois réponses d’un coup. Pour nier, exhiber $x\neq x'$ avec $f(x)=f(x')$, ou un $y$ sans antécédent.

Théorème — application réciproque. $f:E\to F$ est bijective si et seulement s’il existe $g:F\to E$ telle que $\ g\circ f=\mathrm{id}_{E}$ et $f\circ g=\mathrm{id}_{F}$. Une telle $g$ est alors unique : c’est l’application réciproque $f^{-1}$, elle-même bijective, avec $\bigl(f^{-1}\bigr)^{-1}=f$ ; pour $y\in F$, $f^{-1}(y)$ est l’unique antécédent de $y$.

Idée de preuve. Si $f$ est bijective, poser $g(y)=$ l’unique antécédent de $y$. Réciproquement $g\circ f=\mathrm{id}_{E}$ force l’injectivité (appliquer $g$ à $f(x)=f(x')$) et $f\circ g=\mathrm{id}_{F}$ la surjectivité ($y=f(g(y))$) ; l’unicité vient de $g'=g'\circ(f\circ g)=(g'\circ f)\circ g=g$.

Théorème — composition et injectivité / surjectivité. Soient $f:E\to F$ et $g:F\to G$.

Idée de preuve (exigible). Deuxième point : si $f(x)=f(x')$ alors $g(f(x))=g(f(x'))$, donc $x=x'$ par injectivité de $g\circ f$. Si $z\in G$, il existe $x\in E$ avec $g(f(x))=z$ : l’élément $f(x)$ de $F$ est un antécédent de $z$ par $g$.

Théorème — injectivité, surjectivité et images. Soit $f:E\to F$. Alors $f$ est injective $\iff\forall A\in\mathcal{P}(E),\ f^{-1}\bigl(f(A)\bigr)=A\iff\forall A,A'\in\mathcal{P}(E),\ f(A\cap A')=f(A)\cap f(A')$ ; et $f$ est surjective $\iff\forall B\in\mathcal{P}(F),\ f\bigl(f^{-1}(B)\bigr)=B$.

6Relations binaires : équivalence et ordre

Définition. Une relation binaire $\mathcal{R}$ sur $E$ est la donnée, pour tout $(x,y)\in E^{2}$, du fait que « $x\mathcal{R}y$ » est vraie ou fausse. Elle est réflexive si $\forall x,\ x\mathcal{R}x$ ; symétrique si $\forall x,y,\ x\mathcal{R}y\implies y\mathcal{R}x$ ; transitive si $\forall x,y,z,\ \bigl(x\mathcal{R}y$ et $y\mathcal{R}z\bigr)\implies x\mathcal{R}z$ ; antisymétrique si $\forall x,y,\ \bigl(x\mathcal{R}y$ et $y\mathcal{R}x\bigr)\implies x=y$.

Définition. Une relation d’équivalence est une relation réflexive, symétrique et transitive. Pour $x\in E$, la classe d’équivalence de $x$ est $\ \mathrm{cl}(x)=\ens{y\in E,\ x\mathcal{R}y}$.

Théorème — classes et partition. Soit $\mathcal{R}$ une relation d’équivalence sur $E$. Alors, pour tous $x,y\in E$ :

Les classes d’équivalence, deux à deux distinctes, forment donc une partition de $E$. La notion d’ensemble quotient est hors programme.

Idée de preuve (exigible). La réflexivité donne $x\in\mathrm{cl}(x)$ : les classes sont non vides et recouvrent $E$. Si $x\mathcal{R}y$ et $z\in\mathrm{cl}(y)$, la transitivité donne $x\mathcal{R}z$, d’où $\mathrm{cl}(y)\subset\mathrm{cl}(x)$, et la symétrie l’autre inclusion. Enfin $z\in\mathrm{cl}(x)\cap\mathrm{cl}(y)$ entraîne $\mathrm{cl}(x)=\mathrm{cl}(z)=\mathrm{cl}(y)$ : deux classes distinctes sont disjointes.

Notation — congruences. Soit $c\in\R$. Pour $a,b\in\R$ on écrit $\ a\equiv b\ [c]\iff\exists k\in\Z,\ a-b=kc$. Pour $n\in\N^{*}$ et $a,b\in\Z$, $\ a\equiv b\ [n]\iff n\mid(a-b)$. Dans les deux cas c’est une relation d’équivalence, compatible avec l’addition ; pour $a,b\in\Z$ elle l’est aussi avec la multiplication.

Définition. Une relation d’ordre sur $E$ est une relation réflexive, antisymétrique et transitive ; on la note $\preccurlyeq$, et $(E,\preccurlyeq)$ est un ensemble ordonné. L’ordre est total si $\forall(x,y)\in E^{2}$, $x\preccurlyeq y$ ou $y\preccurlyeq x$, et partiel sinon. Un $m\in A$ est le plus grand élément de $A\subset E$ si $\forall x\in A,\ x\preccurlyeq m$ : il est unique par antisymétrie, mais peut ne pas exister.