Ensembles et applications

Un ensemble est une collection d'objets appelés ses éléments. On note $x \in E$ lorsque $x$ est un élément de $E$, et $x \notin E$ sinon.

• L'ensemble vide, noté $\varnothing$, ne contient aucun élément.
• Un ensemble peut être décrit en extension, en listant ses éléments : $\{1, 2, 3\}$.
• Il peut être décrit en compréhension, par une propriété $P$ : $\{x \in E \mid P(x)\}$ est l'ensemble des éléments de $E$ qui vérifient $P$.
• Un ensemble à un seul élément $\{a\}$ est un singleton.

Soit $A$ et $E$ deux ensembles. On dit que $A$ est inclus dans $E$, ou que $A$ est une partie de $E$, et on note $A \subset E$, si tout élément de $A$ est élément de $E$ : $$A \subset E \iff \forall x,\ (x \in A \Rightarrow x \in E).$$ Deux ensembles sont égaux lorsqu'ils ont les mêmes éléments, c'est-à-dire : $$A = B \iff (A \subset B \text{ et } B \subset A).$$ Pour tout ensemble $E$, on a $\varnothing \subset E$ et $E \subset E$.

Les parties d'un ensemble $E$ forment un ensemble, noté $\mathcal{P}(E)$ : $$A \in \mathcal{P}(E) \iff A \subset E.$$ Par exemple, si $E = \{a, b\}$, alors $\mathcal{P}(E) = \{\varnothing, \{a\}, \{b\}, \{a, b\}\}$. Pour tout $E$, $\varnothing \in \mathcal{P}(E)$ et $E \in \mathcal{P}(E)$ ; en particulier $\mathcal{P}(\varnothing) = \{\varnothing\}$ n'est pas vide.

Soit $E$ un ensemble et $A, B \in \mathcal{P}(E)$.

• Réunion : $A \cup B = \{x \in E \mid x \in A \text{ ou } x \in B\}$.
• Intersection : $A \cap B = \{x \in E \mid x \in A \text{ et } x \in B\}$.
• Différence : $A \setminus B = \{x \in E \mid x \in A \text{ et } x \notin B\}$.
• Complémentaire de $A$ dans $E$ : $\overline{A} = E \setminus A = \{x \in E \mid x \notin A\}$.

On dit que $A$ et $B$ sont disjointes si $A \cap B = \varnothing$. Le « ou » est inclusif : un élément de $A \cap B$ appartient à $A \cup B$.

Soit $I$ un ensemble et $(A_i)_{i \in I}$ une famille de parties de $E$. $$\bigcup_{i \in I} A_i = \{x \in E \mid \exists i \in I,\ x \in A_i\}, \qquad \bigcap_{i \in I} A_i = \{x \in E \mid \forall i \in I,\ x \in A_i\}.$$ Les lois de De Morgan restent vraies : $\overline{\bigcup_{i \in I} A_i} = \bigcap_{i \in I} \overline{A_i}$ et $\overline{\bigcap_{i \in I} A_i} = \bigcup_{i \in I} \overline{A_i}$ ; elles traduisent la négation d'un $\exists$ en $\forall$ et inversement.

Le produit cartésien de deux ensembles $E$ et $F$ est l'ensemble des couples : $$E \times F = \{(x, y) \mid x \in E,\ y \in F\}.$$ Deux couples sont égaux si et seulement si leurs composantes le sont : $(x, y) = (x', y') \iff (x = x' \text{ et } y = y')$.

Plus généralement, $E_1 \times \dots \times E_n$ est l'ensemble des $n$-uplets $(x_1, \dots, x_n)$ avec $x_k \in E_k$ pour tout $k$. On note $E^n = E \times \dots \times E$ ($n$ facteurs).

Une famille $(A_i)_{i \in I}$ de parties de $E$ est un recouvrement disjoint de $E$ si les $A_i$ sont deux à deux disjointes ($A_i \cap A_j = \varnothing$ pour $i \neq j$) et si $\bigcup_{i \in I} A_i = E$.

C'est une partition de $E$ si, de plus, chaque $A_i$ est non vide. Tout élément de $E$ appartient alors à une et une seule partie $A_i$.

Exemple : $\{2\mathbb{Z}, 2\mathbb{Z} + 1\}$ (entiers pairs, entiers impairs) est une partition de $\mathbb{Z}$.

Soit $E$ et $F$ deux ensembles. Une application $f$ de $E$ dans $F$ associe à chaque $x \in E$ un unique élément $f(x) \in F$, appelé image de $x$. On note $f : E \to F,\ x \mapsto f(x)$. L'ensemble $E$ est l'ensemble de départ, $F$ l'ensemble d'arrivée. Si $y = f(x)$, on dit que $x$ est un antécédent de $y$.

Le graphe de $f$ est $\Gamma_f = \{(x, f(x)) \mid x \in E\} \subset E \times F$. Formellement, une application est la donnée de $E$, $F$ et d'une partie $\Gamma$ de $E \times F$ telle que pour tout $x \in E$, il existe un unique $y \in F$ avec $(x, y) \in \Gamma$.

Deux applications $f, g$ sont égales si elles ont mêmes ensembles de départ et d'arrivée et si $f(x) = g(x)$ pour tout $x \in E$. L'ensemble des applications de $E$ dans $F$ est noté $F^E$ ou $\mathcal{F}(E, F)$.

• L'identité de $E$ : $\mathrm{id}_E : E \to E,\ x \mapsto x$.
• La fonction indicatrice d'une partie $A$ de $E$ : $\mathbf{1}_A : E \to \{0, 1\}$, avec $\mathbf{1}_A(x) = 1$ si $x \in A$ et $\mathbf{1}_A(x) = 0$ sinon.
• La restriction de $f : E \to F$ à une partie $A$ de $E$ : $f_{|A} : A \to F,\ x \mapsto f(x)$.
• Un prolongement de $f : A \to F$ à $E \supset A$ est une application $g : E \to F$ telle que $g_{|A} = f$.
• Une famille $(x_i)_{i \in I}$ d'éléments de $E$ est une application de $I$ dans $E$, notée de façon indicielle. Une suite réelle est une famille indexée par $\mathbb{N}$.

Soit $f : E \to F$ et $g : F \to G$. La composée de $f$ par $g$ est l'application $$g \circ f : E \to G,\quad x \mapsto g(f(x)).$$ On applique d'abord $f$, puis $g$. Pour que $g \circ f$ ait un sens, l'ensemble d'arrivée de $f$ doit être inclus dans l'ensemble de départ de $g$.

Soit $f : E \to F$, $A \subset E$ et $B \subset F$.

• L'image directe de $A$ par $f$ est la partie de $F$ $$f(A) = \{f(x) \mid x \in A\} = \{y \in F \mid \exists x \in A,\ y = f(x)\}.$$
• L'image réciproque de $B$ par $f$ est la partie de $E$ $$f^{-1}(B) = \{x \in E \mid f(x) \in B\}.$$ L'ensemble $f(E)$ est l'image de $f$, noté aussi $\mathrm{Im}\, f$.

La notation $f^{-1}(B)$ a un sens pour toute application $f$, bijective ou non.

Soit $f : E \to F$.

• $f$ est injective si deux éléments distincts ont des images distinctes : $$\forall (x, x') \in E^2,\ f(x) = f(x') \Rightarrow x = x'.$$ Autrement dit, tout $y \in F$ a au plus un antécédent.
• $f$ est surjective si tout élément de $F$ a au moins un antécédent : $$\forall y \in F,\ \exists x \in E,\ y = f(x).$$ Autrement dit, $f(E) = F$.
• $f$ est bijective si elle est injective et surjective : tout $y \in F$ a exactement un antécédent.

Si $f : E \to F$ est bijective, l'application qui à tout $y \in F$ associe son unique antécédent par $f$ est la bijection réciproque de $f$, notée $f^{-1} : F \to E$. Par construction : $$\forall x \in E,\ \forall y \in F,\quad y = f(x) \iff x = f^{-1}(y),$$ $$f^{-1} \circ f = \mathrm{id}_E, \qquad f \circ f^{-1} = \mathrm{id}_F.$$

Une relation binaire $\mathcal{R}$ sur un ensemble $E$ est la donnée d'une partie $G$ de $E \times E$. On note $x \,\mathcal{R}\, y$ lorsque $(x, y) \in G$. Une relation binaire peut être :

• réflexive : $\forall x \in E,\ x \,\mathcal{R}\, x$ ;
• symétrique : $\forall (x, y) \in E^2,\ x \,\mathcal{R}\, y \Rightarrow y \,\mathcal{R}\, x$ ;
• antisymétrique : $\forall (x, y) \in E^2,\ (x \,\mathcal{R}\, y \text{ et } y \,\mathcal{R}\, x) \Rightarrow x = y$ ;
• transitive : $\forall (x, y, z) \in E^3,\ (x \,\mathcal{R}\, y \text{ et } y \,\mathcal{R}\, z) \Rightarrow x \,\mathcal{R}\, z$.

Une relation d'équivalence sur $E$ est une relation binaire réflexive, symétrique et transitive. On la note souvent $\sim$.

Pour $x \in E$, la classe d'équivalence de $x$ est $$\overline{x} = \{y \in E \mid x \sim y\}.$$ Tout élément d'une classe en est un représentant.

Une relation d'ordre sur $E$ est une relation binaire réflexive, antisymétrique et transitive. On la note souvent $\preccurlyeq$ et on dit que $(E, \preccurlyeq)$ est un ensemble ordonné.

Deux éléments $x, y$ sont comparables si $x \preccurlyeq y$ ou $y \preccurlyeq x$. L'ordre est total si deux éléments quelconques de $E$ sont toujours comparables ; sinon il est partiel.

Soit $(E, \preccurlyeq)$ un ensemble ordonné et $A \subset E$.

• $M \in E$ est un majorant de $A$ si $\forall a \in A,\ a \preccurlyeq M$.
• $M$ est le plus grand élément de $A$ si $M$ est un majorant de $A$ et $M \in A$.

On définit de même minorant et plus petit élément. Ces notions sont reprises en détail pour $(\mathbb{R}, \leq)$ dans le chapitre sur les nombres réels.