NOTIONS DE BASE
Inclusion
On dit que l’ensemble A est inclus dans l’ensemble B, ou que A est un sous-ensemble ou une partie de B et on note A ⊂ B si tout élément de A est un élément de B :
∀x ∈ A, x ∈ B
L’ensemble vide est inclus dans tout ensemble : ∅ ⊂ A.
E étant un ensemble, l’ensemble des parties de E est noté P(E).
Les opérations classiques sur P(E) sont :
- le complémentaire d’une partie A dans E noté CE(A) ou Ac s’il n’y a pas d’ambiguïté ;
- l’union de deux parties A et B, A ∪ B ;
- l’intersection de deux parties A et B, A ∩ B ;
- la différence de deux parties A \ B, qui vaut A ∩ CE(B).
Propriétés des opérations sur les parties d’un ensemble
Associativité : A ∪ (B ∪ C) = (A ∪ B) ∪ C et A ∩ (B ∩ C) = (A ∩ B) ∩ C .
Distributivité de ∩ par rapport ` ∪ : A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) .
Distributivité de ∪ par rapport ` ∩ : A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) .
Lois de Morgan : CE(A ∩ B) = CE(A) ∪ CE(B) et CE(A ∪ B) = CE(A) ∩ CE(B) .
Produit cartésien
A partir de deux ensembles A et B, on crée un nouvel ensemble noté A × B, dont les éléments sont les couples (a, b) constitués d’un élément a de A et d’un élément b de B dans cet ordre.
A × B = { (x, y), x ∈ A et y ∈ B } .
II. APPLICATIONS
E et F étant des ensembles, une application f de E vers F est un moyen d’associer à chaque
élément de E un élément unique de F . On note :
f : E → F
x → f(x)
f(x) s’appelle l’image de x par f.
Le graphe de f est l’ensemble des couples (x, f(x)), c’est une partie de E × F.
E s’appelle l’ensemble de départ de f. F s’appelle l’ensemble d’arrivée de f.
Image directe
Soit f : E → F et A une partie de E.
L’image (directe) de A par f est la partie de F notée f(A) formée des images de tous les éléments de A. Pour y ∈ F,
y ∈ f(A) ⇐⇒ ∃x ∈ A, y = f(x) .
Par exemple, si A = {a, b, c}, f(A) = {f(a), f(b), f(c)}.
Image réciproque
Composée de deux applications
f : E → F et g : F → G étant des applications, on définit la composée des applications f et g par :
g ◦ f : E → G
x → g ◦ f(x) = g(f(x))
Si h : G → H, alors h ◦ (g ◦ f) = (h ◦ g) ◦ f.
Injectivité
f : E → F est injective si chaque élément de F a au plus un antécédent dans E.
C’est équivalent à : ∀x, x’∈ E, (f(x) = f(x’)) ⇒ (x = x’).
La composée de deux applications injectives est injective.
Si g ◦ f est injective, alors f est injective.
Surjectivité
Une application f : E → F est surjective si chaque élément de F a au moins un antécédent
dans E :
∀y ∈ F, ∃x ∈ E, y = f(x).
C’est équivalent à : f(E) = F.
La composée de deux applications surjectives est surjective.
Si g ◦ f est surjective, alors g est surjective.
Bijectivité, application réciproque
f : E → F est bijective si chaque élément de F a exactement un antécédent dans E, ce qui revient à dire que f est injective et surjective.
∀y ∈ F, ∃!x ∈ E, y = f(x).
III. RELATIONS BINAIRES
Une relation binaire R est définie par un ensemble E et par une partie G de E × E. On dit alors que R est une relation binaire sur E. On dit que x est en relation avec y et on note xRy si et seulement si (x, y) ∈ G.
Une relation est en général définie par une propriété commune aux couples (x, y), par exemple la relation R sur IR telle que : ∀x ∈ IR, ∀y ∈ IR, xRy ⇐⇒ x − y = 1.
Relation d’équivalence
Une relation d’équivalence R vérifie les trois propriétés suivantes :
- réflexivité : pour tout x de E, xRx ; on dit que R est réflexive ;
- symétrie : pour tous x et y de E, si xRy alors yRx ; on dit que R est symétrique ;
- transitivité : pour tous x, y et z de E, si xRy et yRz, alors xRz ; on dit que R est transitive.
Une relation d’équivalence permet de regrouper les éléments d’un ensemble en classes d’équivalence ; la classe de l’élément a, notée C(a), est l’ensemble de tous les éléments x tels que xRa, ces éléments sont dits équivalents à a.
Partition d’un ensemble en classes d’équivalence
Lorsque R est une relation d’équivalence sur un ensemble E, l’ensemble des classes d’équivalences est appelé ensemble quotient de E par R, noté E/R.
L’ensemble E/R possède trois propriétés remarquables :
- aucune classe d’équivalence n’est vide,
- deux classes distinctes sont disjointes,
- l’union de toutes les classes d’équivalence est l’ensemble E.
La famille (C(x))C(x)∈E/R des classes d’équivalences est donc une partition de E.
Relation d’ordre
La relation binaire R sur E est dite antisymétrique si pour tous x et y de E :
xRy et yRx entraîne x = y .
R est une relation d’ordre si elle est réflexive, antisymétrique et transitive. On dit alors que
(E,R) est un ensemble ordonné.
Par exemple, l’inclusion entre parties d’un ensemble est une relation d’ordre.
Ordre total, ordre partiel
On note une relation d’ordre sur E ; x y se lit “x est plus petit que y” ou “y est plus grand que x”.
L’ordre est total si deux éléments quelconques de E sont toujours comparables :
∀(x, y) ∈ E × E, x y ou y x.
Dans le cas contraire, l’ordre est dit partiel.
Ainsi l’inclusion est une relation d’ordre partiel sur les parties d’un ensemble E fixé (si E a au moins 2 éléments), la relation ≤ est une relation d’ordre total sur IR.
Majorant, minorant
A étant une partie de E,
x ∈ E est un majorant de A si pour tout a ∈ A, a x.
y ∈ E est un minorant de A si pour tout a ∈ A, y a.
Une partie A de E est majorée lorsqu’elle admet un majorant, minorée lorsqu’elle admet un minorant. A est bornée si elle est `a la fois majorée et minorée.
Plus grand élément, plus petit élément
S’il existe un élément de A qui soit un majorant de A, cet élément est unique et on l’appelle le plus grand élément, ou le maximum, de A ; il se note : maxA.
De même, si A possède un élément minorant, il est unique et s’appelle le plus petit élément, ou le minimum, de A ; on le note : minA.
Borne supérieure, borne inférieure
On remarque que si M est un majorant d’une partie A, tout élément plus grand que M est également un majorant de A. Si l’ensemble des majorants de A possède un plus petit élément, c’est le plus petit majorant de A. Cet élément, lorsqu’il existe, s’appelle la borne supérieure de
A et se note : supA.
On retient : la borne supérieure de A est le plus petit des majorants de A.
On définit de même la borne inférieure de A, notée infA, comme étant le plus grand des minorants de A.
Pour toute partie A d’un ensemble ordonné,
si A a un maximum, alors A a une borne supérieure et maxA = supA.
si A a un minimum, alors A a une borne inférieure et minA = infA.
Cas particulier de l’ensemble ordonné (IR,≤)
Toute partie non vide et majorée de IR a une borne supérieure.
Toute partie non vide et minorée de IR a une borne inférieure.
On dit que l’ensemble A est inclus dans l’ensemble B, ou que A est un sous-ensemble ou une partie de B et on note A ⊂ B si tout élément de A est un élément de B :
∀x ∈ A, x ∈ B
L’ensemble vide est inclus dans tout ensemble : ∅ ⊂ A.
E étant un ensemble, l’ensemble des parties de E est noté P(E).
Les opérations classiques sur P(E) sont :
- le complémentaire d’une partie A dans E noté CE(A) ou Ac s’il n’y a pas d’ambiguïté ;
- l’union de deux parties A et B, A ∪ B ;
- l’intersection de deux parties A et B, A ∩ B ;
- la différence de deux parties A \ B, qui vaut A ∩ CE(B).
Propriétés des opérations sur les parties d’un ensemble
Associativité : A ∪ (B ∪ C) = (A ∪ B) ∪ C et A ∩ (B ∩ C) = (A ∩ B) ∩ C .
Distributivité de ∩ par rapport ` ∪ : A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) .
Distributivité de ∪ par rapport ` ∩ : A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) .
Lois de Morgan : CE(A ∩ B) = CE(A) ∪ CE(B) et CE(A ∪ B) = CE(A) ∩ CE(B) .
Produit cartésien
A partir de deux ensembles A et B, on crée un nouvel ensemble noté A × B, dont les éléments sont les couples (a, b) constitués d’un élément a de A et d’un élément b de B dans cet ordre.
A × B = { (x, y), x ∈ A et y ∈ B } .
II. APPLICATIONS
E et F étant des ensembles, une application f de E vers F est un moyen d’associer à chaque
élément de E un élément unique de F . On note :
f : E → F
x → f(x)
f(x) s’appelle l’image de x par f.
Le graphe de f est l’ensemble des couples (x, f(x)), c’est une partie de E × F.
E s’appelle l’ensemble de départ de f. F s’appelle l’ensemble d’arrivée de f.
Image directe
Soit f : E → F et A une partie de E.
L’image (directe) de A par f est la partie de F notée f(A) formée des images de tous les éléments de A. Pour y ∈ F,
y ∈ f(A) ⇐⇒ ∃x ∈ A, y = f(x) .
Par exemple, si A = {a, b, c}, f(A) = {f(a), f(b), f(c)}.
Image réciproque
Composée de deux applications
f : E → F et g : F → G étant des applications, on définit la composée des applications f et g par :
g ◦ f : E → G
x → g ◦ f(x) = g(f(x))
Si h : G → H, alors h ◦ (g ◦ f) = (h ◦ g) ◦ f.
Injectivité
f : E → F est injective si chaque élément de F a au plus un antécédent dans E.
C’est équivalent à : ∀x, x’∈ E, (f(x) = f(x’)) ⇒ (x = x’).
La composée de deux applications injectives est injective.
Si g ◦ f est injective, alors f est injective.
Surjectivité
Une application f : E → F est surjective si chaque élément de F a au moins un antécédent
dans E :
∀y ∈ F, ∃x ∈ E, y = f(x).
C’est équivalent à : f(E) = F.
La composée de deux applications surjectives est surjective.
Si g ◦ f est surjective, alors g est surjective.
Bijectivité, application réciproque
f : E → F est bijective si chaque élément de F a exactement un antécédent dans E, ce qui revient à dire que f est injective et surjective.
∀y ∈ F, ∃!x ∈ E, y = f(x).
III. RELATIONS BINAIRES
Une relation binaire R est définie par un ensemble E et par une partie G de E × E. On dit alors que R est une relation binaire sur E. On dit que x est en relation avec y et on note xRy si et seulement si (x, y) ∈ G.
Une relation est en général définie par une propriété commune aux couples (x, y), par exemple la relation R sur IR telle que : ∀x ∈ IR, ∀y ∈ IR, xRy ⇐⇒ x − y = 1.
Relation d’équivalence
Une relation d’équivalence R vérifie les trois propriétés suivantes :
- réflexivité : pour tout x de E, xRx ; on dit que R est réflexive ;
- symétrie : pour tous x et y de E, si xRy alors yRx ; on dit que R est symétrique ;
- transitivité : pour tous x, y et z de E, si xRy et yRz, alors xRz ; on dit que R est transitive.
Une relation d’équivalence permet de regrouper les éléments d’un ensemble en classes d’équivalence ; la classe de l’élément a, notée C(a), est l’ensemble de tous les éléments x tels que xRa, ces éléments sont dits équivalents à a.
Partition d’un ensemble en classes d’équivalence
Lorsque R est une relation d’équivalence sur un ensemble E, l’ensemble des classes d’équivalences est appelé ensemble quotient de E par R, noté E/R.
L’ensemble E/R possède trois propriétés remarquables :
- aucune classe d’équivalence n’est vide,
- deux classes distinctes sont disjointes,
- l’union de toutes les classes d’équivalence est l’ensemble E.
La famille (C(x))C(x)∈E/R des classes d’équivalences est donc une partition de E.
Relation d’ordre
La relation binaire R sur E est dite antisymétrique si pour tous x et y de E :
xRy et yRx entraîne x = y .
R est une relation d’ordre si elle est réflexive, antisymétrique et transitive. On dit alors que
(E,R) est un ensemble ordonné.
Par exemple, l’inclusion entre parties d’un ensemble est une relation d’ordre.
Ordre total, ordre partiel
On note une relation d’ordre sur E ; x y se lit “x est plus petit que y” ou “y est plus grand que x”.
L’ordre est total si deux éléments quelconques de E sont toujours comparables :
∀(x, y) ∈ E × E, x y ou y x.
Dans le cas contraire, l’ordre est dit partiel.
Ainsi l’inclusion est une relation d’ordre partiel sur les parties d’un ensemble E fixé (si E a au moins 2 éléments), la relation ≤ est une relation d’ordre total sur IR.
Majorant, minorant
A étant une partie de E,
x ∈ E est un majorant de A si pour tout a ∈ A, a x.
y ∈ E est un minorant de A si pour tout a ∈ A, y a.
Une partie A de E est majorée lorsqu’elle admet un majorant, minorée lorsqu’elle admet un minorant. A est bornée si elle est `a la fois majorée et minorée.
Plus grand élément, plus petit élément
S’il existe un élément de A qui soit un majorant de A, cet élément est unique et on l’appelle le plus grand élément, ou le maximum, de A ; il se note : maxA.
De même, si A possède un élément minorant, il est unique et s’appelle le plus petit élément, ou le minimum, de A ; on le note : minA.
Borne supérieure, borne inférieure
On remarque que si M est un majorant d’une partie A, tout élément plus grand que M est également un majorant de A. Si l’ensemble des majorants de A possède un plus petit élément, c’est le plus petit majorant de A. Cet élément, lorsqu’il existe, s’appelle la borne supérieure de
A et se note : supA.
On retient : la borne supérieure de A est le plus petit des majorants de A.
On définit de même la borne inférieure de A, notée infA, comme étant le plus grand des minorants de A.
Pour toute partie A d’un ensemble ordonné,
si A a un maximum, alors A a une borne supérieure et maxA = supA.
si A a un minimum, alors A a une borne inférieure et minA = infA.
Cas particulier de l’ensemble ordonné (IR,≤)
Toute partie non vide et majorée de IR a une borne supérieure.
Toute partie non vide et minorée de IR a une borne inférieure.