Relations Binaires et Applications Cours

Relations Binaires

Une relation binaire est une correspondance entre deux éléments d’un ou deux ensembles. Mathématiquement, une relation binaire sur un ensemble \( A \) est définie comme un sous-ensemble du produit cartésien \( A \times A \).

Définition

Soient \( A \) et \( B \) deux ensembles, une relation binaire \( R \) est un sous-ensemble de \( A \times B \), où :

\( R \subseteq A \times B \).

Cela signifie que pour tout couple \( (a, b) \), \( a \in A \) et \( b \in B \), \( (a, b) \in R \) si et seulement si \( a \) est en relation avec \( b \) selon \( R \).

Exemples

Sur l’ensemble des nombres réels \( \mathbb{R} \), la relation "<" est définie comme :

\( a < b \iff b - a > 0 \).

Sur un ensemble \( A = \{1, 2, 3\} \), une relation binaire \( R \) pourrait être définie par :

\( R = \{(1, 2), (2, 3)\} \).

Types de Relations Binaires

Réflexive : Une relation \( R \) sur un ensemble \( A \) est réflexive si pour tout \( a \in A \), \( (a, a) \in R \).

Symétrique : Une relation \( R \) est symétrique si pour tout \( a, b \in A \), \( (a, b) \in R \implies (b, a) \in R \).

Transitive : Une relation \( R \) est transitive si pour tout \( a, b, c \in A \), \( (a, b) \in R \) et \( (b, c) \in R \implies (a, c) \in R \).

Relations d’Équivalence

Une relation d’équivalence est une relation binaire spéciale qui divise un ensemble en sous-ensembles disjoints appelés classes d’équivalence. Elle satisfait trois propriétés fondamentales : réflexivité, symétrie et transitivité.

Définition

Une relation \( R \) sur un ensemble \( A \) est une relation d’équivalence si elle vérifie :

• Réflexivité : \( \forall a \in A, \; (a, a) \in R \).
• Symétrie : \( \forall a, b \in A, \; (a, b) \in R \implies (b, a) \in R \).
• Transitivité : \( \forall a, b, c \in A, \; (a, b) \in R \land (b, c) \in R \implies (a, c) \in R \).

Exemples

Sur l’ensemble des entiers relatifs \( \mathbb{Z} \), la relation "est congru à modulo \( n \)" est une relation d’équivalence. Elle est définie par :

\( a \equiv b \pmod{n} \iff n \text{ divise } (a - b) \).

La relation d’égalité \( = \) sur tout ensemble \( A \) est une relation d’équivalence car :

• \( a = a \) (réflexivité).
• Si \( a = b \), alors \( b = a \) (symétrie).
• Si \( a = b \) et \( b = c \), alors \( a = c \) (transitivité).

Classes d’Équivalence

Si \( R \) est une relation d’équivalence sur un ensemble \( A \), alors \( A \) peut être partitionné en sous-ensembles disjoints appelés classes d’équivalence. Pour un élément \( a \in A \), sa classe d’équivalence est notée :

\( [a]_R = \{x \in A \mid (a, x) \in R\} \).

Exemple de Classes d’Équivalence

Pour la relation \( a \equiv b \pmod{3} \) sur \( \mathbb{Z} \) :

La classe d’équivalence de \( 0 \) est \( [0] = \{\dots, -6, -3, 0, 3, 6, \dots\} \).

La classe d’équivalence de \( 1 \) est \( [1] = \{\dots, -5, -2, 1, 4, 7, \dots\} \).

La classe d’équivalence de \( 2 \) est \( [2] = \{\dots, -4, -1, 2, 5, 8, \dots\} \).

Relations d’Ordre

Une relation d’ordre est une relation binaire définissant une organisation ou une hiérarchie parmi les éléments d’un ensemble donné. Elle peut être un ordre partiel ou total.

Définition

Une relation \( R \) sur un ensemble \( A \) est une relation d’ordre si elle satisfait :

Réflexivité : \( \forall a \in A, \; (a, a) \in R \).

Antisymétrie : \( \forall a, b \in A, \; (a, b) \in R \land (b, a) \in R \implies a = b \).

Transitivité : \( \forall a, b, c \in A, \; (a, b) \in R \land (b, c) \in R \implies (a, c) \in R \).

Types de Relations d’Ordre

• Ordre Partiel : Si tous les éléments ne sont pas nécessairement comparables.
• Ordre Total : Si tous les éléments sont comparables, c’est-à-dire que pour tout \( a, b \in A \), on a \( (a, b) \in R \) ou \( (b, a) \in R \).

Exemples

L’ordre \( \leq \) sur les nombres réels \( \mathbb{R} \) est un ordre total.

La relation "est un sous-ensemble de" (\( \subseteq \)) sur l’ensemble des parties d’un ensemble \( A \) est un ordre partiel.

Fonctions

Une fonction est une relation particulière entre deux ensembles \( A \) (ensemble de départ) et \( B \) (ensemble d’arrivée) qui associe à chaque élément de \( A \) un unique élément de \( B \).

Définition

Une fonction \( f \) est une relation telle que :

\( \forall a \in A, \; \exists! b \in B \; \text{tel que} \; (a, b) \in f \).

Elle est notée :

\( f : A \to B \), où \( f(a) = b \).

Propriétés d’une Fonction

Injectivité : \( f \) est injective si :

\( \forall a_1, a_2 \in A, \; f(a_1) = f(a_2) \implies a_1 = a_2 \).

Surjectivité : \( f \) est surjective si :

\( \forall b \in B, \; \exists a \in A \; \text{tel que} \; f(a) = b \).

Bijection : \( f \) est bijective si elle est à la fois injective et surjective.

Exemples

La fonction \( f(x) = 2x + 1 \) sur \( \mathbb{R} \) est une bijection.

La fonction \( f(x) = x^2 \) sur \( \mathbb{R} \) n’est pas injective (car \( f(-x) = f(x) \)).

Fonctions Composées

La composition de deux fonctions \( f : A \to B \) et \( g : B \to C \) est une nouvelle fonction \( g \circ f : A \to C \), définie par :

\( (g \circ f)(x) = g(f(x)) \).

Propriétés de la Composition

La composition de fonctions est associative :

\( h \circ (g \circ f) = (h \circ g) \circ f \).

La composition d’une fonction avec l’identité \( \text{Id}_A \) laisse la fonction inchangée :

\( f \circ \text{Id}_A = \text{Id}_B \circ f = f \).

Exemple

Soit \( f(x) = 2x + 1 \) et \( g(x) = x^2 \). La composition \( g \circ f \) est définie par :

\( (g \circ f)(x) = g(f(x)) = (2x + 1)^2 \).

Images Directes

L’image directe d’un sous-ensemble \( A \) par une fonction \( f \) est l’ensemble des valeurs correspondantes dans l’ensemble d’arrivée \( B \). Elle décrit la manière dont \( f \) "transforme" \( A \).

Définition

Soit \( f : A \to B \) une fonction, et \( X \subseteq A \). L’image directe de \( X \) par \( f \) est définie comme :

\[ f(X) = \{f(x) \mid x \in X\}. \]

Propriétés

• Si \( X \subseteq Y \subseteq A \), alors \( f(X) \subseteq f(Y) \).
• L’image directe de l’ensemble vide est vide :

  \[ f(\emptyset) = \emptyset. \]

Exemples

• Soit \( f(x) = x^2 \) et \( A = \mathbb{R} \). L’image directe de \( X = [-2, 2] \) est :

  \[ f([-2, 2]) = [0, 4]. \]

• Pour \( f(x) = x + 1 \) et \( X = \{1, 2, 3\} \), on a :

  \[ f(X) = \{2, 3, 4\}. \]

Images Réciproques

L’image réciproque d’un sous-ensemble \( B \subseteq Y \) par une fonction \( f : X \to Y \) est l’ensemble des éléments de \( X \) qui sont envoyés dans \( B \) par \( f \).

Définition

Soit \( f : A \to B \), et \( Y \subseteq B \). L’image réciproque de \( Y \) par \( f \) est définie comme :

\[ f^{-1}(Y) = \{x \in A \mid f(x) \in Y\}. \]

Propriétés

Si \( Y_1 \subseteq Y_2 \subseteq B \), alors \( f^{-1}(Y_1) \subseteq f^{-1}(Y_2) \).

L’image réciproque de l’ensemble vide est vide :

\[ f^{-1}(\emptyset) = \emptyset. \]

L’image réciproque de l’ensemble \( B \) est \( A \) :

\[ f^{-1}(B) = A. \]

Différence entre Image Directe et Image Réciproque

- L’image directe part d’un sous-ensemble de l’ensemble de départ \( A \) et retourne un sous-ensemble de l’ensemble d’arrivée \( B \). - L’image réciproque part d’un sous-ensemble de \( B \) et retourne un sous-ensemble de \( A \).

Injections

Une fonction \( f : A \to B \) est dite *injective* si chaque élément de l’ensemble \( B \) est l’image d’au plus un élément de \( A \). Autrement dit, des éléments distincts de \( A \) ont des images distinctes dans \( B \).

Définition

\( f \) est injective si et seulement si :

\[ \forall a_1, a_2 \in A, \; f(a_1) = f(a_2) \implies a_1 = a_2. \]

Propriétés

• Une fonction injective peut ne pas couvrir tout l’ensemble \( B \).
• Si \( f \) est injective, alors l’image réciproque de chaque élément de \( B \) contient au plus un élément.

Exemples

La fonction \( f(x) = 2x \) sur \( \mathbb{R} \) est injective, car \( f(a) = f(b) \implies a = b \).

La fonction \( f(x) = x^2 \) sur \( \mathbb{R}^+ \) (ensemble des réels positifs) est injective.

Surjections

Une fonction \( f : A \to B \) est dite *surjective* si chaque élément de \( B \) est l’image d’au moins un élément de \( A \). Cela signifie que \( f \) "couvre" tout \( B \).

Définition

\( f \) est surjective si et seulement si :

\[ \forall b \in B, \; \exists a \in A \; \text{tel que} \; f(a) = b. \]

Propriétés

Une fonction surjective peut avoir plusieurs éléments de \( A \) ayant la même image dans \( B \).

L’ensemble d’arrivée \( B \) est égal à l’image directe \( f(A) \).

Exemples

La fonction \( f(x) = x^3 \) sur \( \mathbb{R} \) est surjective, car tout \( y \in \mathbb{R} \) a une préimage \( x = \sqrt[3]{y} \).

La fonction \( f(x) = \sin(x) \) sur \( \mathbb{R} \) n’est pas surjective sur \( \mathbb{R} \), mais elle l’est sur l’intervalle \( [-1, 1] \).

Bijections

Une fonction \( f : A \to B \) est dite *bijective* si elle est à la fois injective et surjective. Cela signifie que chaque élément de \( B \) est l’image d’un et d’un seul élément de \( A \).

Définition

\( f \) est bijective si et seulement si :

\[ \forall b \in B, \; \exists ! a \in A \; \text{tel que} \; f(a) = b. \]

Une fonction bijective établit une correspondance biunivoque entre \( A \) et \( B \).

Propriétés

Une fonction bijective a une fonction réciproque \( f^{-1} : B \to A \), définie par :

\[ f^{-1}(b) = a \; \text{tel que} \; f(a) = b. \]

La composition de deux fonctions bijectives est également bijective.

Résumé des Différences

Type	Injective	Surjective	Bijection
Définition	Chaque élément de \( B \) a au plus une préimage.	Chaque élément de \( B \) a au moins une préimage.	Chaque élément de \( B \) a exactement une préimage.
Propriété	Pas forcément tout \( B \) couvert.	Tout \( B \) est couvert.	Correspondance biunivoque.

Admin Control Panel

Theme CustomizerEdit Theme HTMLStaticsLayoutCommentsPagesPostsSettingsEdit This Post