Ensembles, relations et applications

Ensembles, relations et applications

### 1. Appartenance, inclusion, égalité

Soit $E$ un ensemble. Pour $x$ un objet et $A, B$ des sous-ensembles (parties) de $E$ :

- $x \in A$ : "$x$ appartient à $A$" ; $x \notin A$ : "$x$ n'appartient pas à $A$".
- $A \subset B$ (inclusion) : $\forall x \in E,\ x \in A \Rightarrow x \in B$.
- $A = B$ : $A \subset B$ et $B \subset A$ (c'est la méthode standard pour prouver une égalité d'ensembles : double inclusion).
- $\emptyset$ : l'ensemble vide, sous-ensemble de tout ensemble.

### 2. Opérations sur les ensembles

Pour $A, B$ parties de $E$ :

| Opération | Notation | Définition |
|---|---|---|
| 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\}$ |
| Complémentaire | $\complement_E A$ ou $A^c$ | $\{x \in E \mid x \notin A\}$ |
| Différence | $A \setminus B$ | $\{x \in E \mid x \in A \text{ et } x \notin B\} = A \cap B^c$ |

Lois de De Morgan pour les ensembles :

Produit cartésien : $A \times B = \{(a,b) \mid a \in A,\ b \in B\}$ (couples ordonnés).

Ensemble des parties : $\mathcal{P}(E)$ est l'ensemble de toutes les parties de $E$ (y compris $\emptyset$ et $E$ lui-même). Si $E$ a $n$ éléments, $\mathcal{P}(E)$ a $2^n$ éléments.

Exemple : $E = \{1,2,3\}$. $\mathcal{P}(E) = \big\{ \emptyset,\ \{1\},\ \{2\},\ \{3\},\ \{1,2\},\ \{1,3\},\ \{2,3\},\ \{1,2,3\} \big\}$, soit $2^3 = 8$ éléments.

### 3. Relations binaires

Une relation binaire $\mathcal{R}$ sur un ensemble $E$ est une partie de $E \times E$ : on note $x\,\mathcal{R}\,y$ si $(x,y)$ appartient à cette partie. On dit que $\mathcal{R}$ est :

- réflexive si $\forall x \in E,\ x\,\mathcal{R}\,x$ ;
- symétrique si $\forall x,y \in E,\ x\,\mathcal{R}\,y \Rightarrow y\,\mathcal{R}\,x$ ;
- antisymétrique si $\forall x,y \in E,\ (x\,\mathcal{R}\,y \wedge y\,\mathcal{R}\,x) \Rightarrow x = y$ ;
- transitive si $\forall x,y,z \in E,\ (x\,\mathcal{R}\,y \wedge y\,\mathcal{R}\,z) \Rightarrow x\,\mathcal{R}\,z$.

### 4. Relations d'équivalence

$\mathcal{R}$ est une relation d'équivalence si elle est réflexive, symétrique et transitive.

Pour $x \in E$, la classe d'équivalence de $x$ est $\overline{x} = \{y \in E \mid x\,\mathcal{R}\,y\}$. Les classes d'équivalence forment une partition de $E$ : elles sont non vides, deux à deux disjointes (ou confondues), et leur union vaut $E$.

Exemple classique : sur $\mathbb{Z}$, la relation "$x \equiv y \pmod{n}$" (i.e. $n \mid (x-y)$) est une relation d'équivalence. Ses classes d'équivalence sont les $n$ classes de congruence modulo $n$.

### 5. Relations d'ordre

$\mathcal{R}$ est une relation d'ordre si elle est réflexive, antisymétrique et transitive. L'ordre est total si $\forall x,y \in E,\ x\,\mathcal{R}\,y \vee y\,\mathcal{R}\,x$ (deux éléments sont toujours comparables) ; sinon il est partiel.

Exemples : $(\mathbb{R}, \leq)$ est un ordre total. $(\mathcal{P}(E), \subset)$ est un ordre partiel dès que $E$ a au moins $2$ éléments (deux parties disjointes non vides ne sont pas comparables par inclusion).

### 6. Applications : définitions de base

Une application $f : E \to F$ associe à chaque élément $x \in E$ un unique élément $f(x) \in F$. On définit :

- image directe d'une partie $A \subset E$ : $f(A) = \{f(x) \mid x \in A\}$ ;
- image réciproque d'une partie $B \subset F$ : $f^{-1}(B) = \{x \in E \mid f(x) \in B\}$ (définie même si $f$ n'est pas bijective).

### 7. Injection, surjection, bijection

- $f$ est injective si $\forall x_1, x_2 \in E,\ f(x_1) = f(x_2) \Rightarrow x_1 = x_2$ (équivalent à la contraposée : $x_1 \neq x_2 \Rightarrow f(x_1) \neq f(x_2)$). Deux éléments distincts ont des images distinctes.
- $f$ est surjective si $\forall y \in F,\ \exists x \in E,\ f(x) = y$. Tout élément de $F$ est atteint.
- $f$ est bijective si elle est injective et surjective : $\forall y \in F,\ \exists! x \in E,\ f(x) = y$ (existence et unicité).

Méthode pratique pour l'injectivité : on suppose $f(x_1) = f(x_2)$ et on montre $x_1 = x_2$ par calcul direct.

Exemple : $f : \mathbb{R} \to \mathbb{R}$, $f(x) = 2x+1$. Injective : $f(x_1)=f(x_2) \Rightarrow 2x_1+1=2x_2+1 \Rightarrow x_1=x_2$. Surjective : pour $y \in \mathbb{R}$, on résout $2x+1=y$, soit $x = (y-1)/2 \in \mathbb{R}$. Donc $f$ est bijective.

Contre-exemple : $g : \mathbb{R} \to \mathbb{R}$, $g(x) = x^2$ n'est ni injective ($g(1)=g(-1)=1$) ni surjective (aucun $x$ ne donne $g(x)=-1$).

### 8. Composition et bijection réciproque

Si $f : E \to F$ et $g : F \to G$, on définit $g \circ f : E \to G$ par $(g\circ f)(x) = g(f(x))$.

Propriétés de composition :
- Si $f$ et $g$ sont injectives, $g \circ f$ est injective.
- Si $f$ et $g$ sont surjectives, $g \circ f$ est surjective.
- Si $f$ et $g$ sont bijectives, $g \circ f$ est bijective.

Si $f : E \to F$ est bijective, il existe une unique application $f^{-1} : F \to E$, la bijection réciproque, caractérisée par :

Exemple : pour $f(x) = 2x+1$ ci-dessus, $f^{-1}(y) = \frac{y-1}{2}$. Vérification : $f^{-1}(f(x)) = f^{-1}(2x+1) = \frac{(2x+1)-1}{2} = x$.