Tronc commun / Mathématiques / Ensembles, applications et relations

Ensembles, applications et relations

Éléments de la théorie des ensembles : cardinal et produit cartésien, applications (image, image réciproque, injection, surjection, bijection, composition), puis relations binaires, d'équivalence et d'ordre, avec l'écriture formelle à savoir justifier.

1. Cardinal d'un ensemble fini

Le cardinal d'un ensemble fini E, noté Card E ou |E|, est son nombre d'éléments.

Pour deux parties A et B de E : Card(A ∪ B) = Card A + Card B − Card(A ∩ B). On retire l'intersection car ses éléments ont été comptés deux fois.

Exemple : 18 élèves font du sport, 12 de la musique, 5 les deux. Card(S ∪ M) = 18 + 12 − 5 = 25 élèves font au moins une des deux activités.

2. Produit cartésien

Le produit cartésien E₁ × E₂ est l'ensemble de tous les couples (x₁ ; x₂) avec x₁ ∈ E₁ et x₂ ∈ E₂ :

E1 × E2 = { (x1 ; x2) | (x1 ∈ E1) ∧ (x2 ∈ E2) }

• Les éléments d'un couple sont ordonnés : (a ; b) n'est pas (b ; a). On ne prend pas le dessert avant l'entrée.
• Lorsque E₁ = E₂ = E, on note E × E = E².
• Si E₁ et E₂ sont finis : Card(E1 × E2) = Card E1 × Card E2.

Exemple du menu de la cantine : 5 entrées, 2 plats, 2 garnitures, 3 fromages, 6 desserts. Un menu est un élément de E × P × G × F × D, donc il y a 5 × 2 × 2 × 3 × 6 = 360 menus possibles.

3. Les symboles à savoir lire et écrire

Nier une phrase : ∀ devient ∃, ∃ devient ∀, et la propriété finale est niée. La négation de « tous les éléments de F ont un antécédent » est « il existe un élément de F qui n'a pas d'antécédent ».

4. Application d'un ensemble dans un autre

Une application f d'un ensemble E dans un ensemble F associe à tout élément de E un et un seul élément de F, appelé son image. On note f : E → F, x ↦ y = f(x).

• Si f(x) = y, y est l'image de x et x est un antécédent de y.
• Chaque élément de E a exactement une image ; un élément de F peut avoir 0, 1 ou plusieurs antécédents.

Exemple du cours : f associe à chaque fichier son dossier d'origine. Un dossier vide n'a aucun antécédent, un dossier qui contient un fichier en a un, un dossier qui en contient deux en a deux.

5. Image directe et image réciproque

Soit f : E → F, A ⊂ E et B ⊂ F.

• Image directe de A : f(A) = { y ∈ F | ∃x ∈ A ; f(x) = y }, l'ensemble des images des éléments de A. Exemple : les dates de naissance des élèves d'une classe A.
• Image réciproque de B : f⁻¹(B) = { x ∈ E ; f(x) ∈ B }, l'ensemble des éléments de E dont l'image est dans B. Exemple : f⁻¹(mai) = les élèves nés en mai.

Propriétés, pour A, B ∈ P(E) puis A, B ∈ P(F) :

• f(A ∪ B) = f(A) ∪ f(B), mais seulement f(A ∩ B) ⊂ f(A) ∩ f(B) ;
• f⁻¹(A ∪ B) = f⁻¹(A) ∪ f⁻¹(B) et f⁻¹(A ∩ B) = f⁻¹(A) ∩ f⁻¹(B).

La notation f⁻¹(B) existe pour toute application, même non bijective, et peut être vide. Pourquoi seulement une inclusion pour f(A ∩ B) ? Deux éléments différents, l'un dans A seul et l'autre dans B seul, peuvent avoir la même image : elle est dans f(A) ∩ f(B) sans être dans f(A ∩ B).

6. Injection

f : E → F est injective si deux éléments différents de E ont toujours deux images différentes :

∀x, x′ ∈ E ; x ≠ x′ ⇒ f(x) ≠ f(x′)  (ou, ce qui revient au même : f(x) = f(x′) ⇒ x = x′)

• Autrement dit, tout élément de F a au plus un antécédent : ∀y ∈ F, Card f⁻¹(y) ≤ 1.
• Négation : f n'est pas injective s'il existe deux éléments distincts qui ont la même image : ∃x, x′ ∈ E ; (x ≠ x′) ∧ (f(x) = f(x′)).

Exemple : le numéro de carte attribué à chaque élève du lycée. Deux élèves ne peuvent pas avoir le même numéro : l'application est injective.

7. Surjection

f : E → F est surjective si tous les éléments de F possèdent un antécédent :

∀y ∈ F ; ∃x ∈ E tq f(x) = y

• Autrement dit : ∀y ∈ F, Card f⁻¹(y) ≥ 1, ou encore f(E) = F.
• Négation : f n'est pas surjective si un élément de F n'a pas d'antécédent : ∃y ∈ F ; ∀x ∈ E, f(x) ≠ y.

Exemple : fichiers → dossiers, quand aucun dossier n'est vide. Chaque dossier contient au moins un fichier, donc a au moins un antécédent.

8. Bijection

f : E → F est bijective si elle est à la fois injective et surjective : tous les éléments de F ont un unique antécédent.

∀y ∈ F ; ∃! x ∈ E tq f(x) = y

• ∀y ∈ F, Card f⁻¹(y) = 1.
• Si E et F sont finis : Card E = Card F.
• Sa réciproque f⁻¹ : F → E existe et est elle-même bijective.

Exemple : un site de vente donne un identifiant à chaque client. Deux clients ne peuvent pas avoir le même (injective) et chaque identifiant correspond à un client de la base (surjective) : c'est une bijection.

9. Composition d'applications

La composée de f : E → F et de g : F → G est l'application g ∘ f de E dans G définie par (g ∘ f)(x) = g(f(x)) : on applique d'abord f, puis g.

• Attention : la composition n'est pas commutative, g ∘ f et f ∘ g sont en général différentes (et f ∘ g n'existe même pas toujours).
• Si f est bijective : f⁻¹ ∘ f = Id_E et f ∘ f⁻¹ = Id_F.
• Si f et g sont injectives, g ∘ f est injective ; si elles sont surjectives, g ∘ f est surjective.
• Si f et g sont bijectives, g ∘ f est bijective et (g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹ (l'ordre s'inverse).

Exemple : f associe à un élève sa date de naissance, g extrait l'année d'une date. g ∘ f associe directement à chaque élève son année de naissance.

10. Relations binaires : les cinq propriétés

Une relation binaire R relie deux éléments d'un même ensemble E non vide. On écrit xRy quand x est en relation avec y. Exemples dans ℕ : « est plus petit que », « est un diviseur de ».

• Réflexive : ∀x ∈ E, xRx (tout élément est en relation avec lui-même).
• Symétrique : ∀x ∈ E, ∀y ∈ E, xRy ⇒ yRx.
• Antisymétrique : ∀(x, y) ∈ E², (xRy ∧ yRx) ⇒ x = y.
• Transitive : ∀(x, y, z) ∈ E³, (xRy ∧ yRz) ⇒ xRz.
• Totale : ∀(x, y) ∈ E², xRy ∨ yRx (deux éléments sont toujours comparables).

Antisymétrique ne veut pas dire « pas symétrique » : c'est une propriété à part entière. Une relation peut n'être ni l'une ni l'autre.

11. Justifier une propriété : la rédaction attendue

• Pour montrer qu'une propriété est vraie : partir d'éléments quelconques. « Soit x ∈ E. x ≤ x, donc xRx : R est réflexive. »
• Pour montrer qu'elle est fausse : un seul contre-exemple suffit. « Pour x = 2 et y = 3 : 2 ≤ 3 mais 3 ≤ 2 est faux, donc R n'est pas symétrique. »

Exemple : la relation ≤ sur ℕ

• Réflexive : soit x ∈ ℕ, x ≤ x.
• Pas symétrique : 2 ≤ 3 mais pas 3 ≤ 2.
• Antisymétrique : soit x, y ∈ ℕ tq (x ≤ y) ∧ (y ≤ x), alors x = y.
• Transitive : soit x, y, z ∈ ℕ tq (x ≤ y) ∧ (y ≤ z), alors x ≤ z.
• Totale : soit x, y ∈ ℕ, on a toujours (x ≤ y) ∨ (y ≤ x).

Exemple : « est né la même année que » (élèves d'une classe) : réflexive, symétrique et transitive. Elle n'est pas antisymétrique (deux élèves différents peuvent être nés la même année) et pas totale : deux élèves nés des années différentes ne sont en relation dans aucun sens.

Exemple : « est strictement plus jeune que » : pas réflexive (personne n'est strictement plus jeune que soi-même), pas symétrique, transitive, et antisymétrique car on ne peut jamais avoir xRy et yRx en même temps.

Exemple : « a un facteur commun avec » (sur les entiers à partir de 2) : réflexive et symétrique, mais pas transitive. 2 et 6 ont 2 en commun, 6 et 3 ont 3 en commun, mais 2 et 3 n'ont aucun facteur commun.

12. Relations d'équivalence

Une relation R est une relation d'équivalence si elle est réflexive, symétrique et transitive.

• On écrit alors xRy sous la forme x ~ y ou x ≡ y [R] : x est équivalent à y, ou x est congru à y modulo R.
• La classe d'équivalence de x, notée x̄ (x barre), est l'ensemble des éléments équivalents à x : x̄ = { y ∈ E ; xRy }.
• L'ensemble des classes d'équivalence s'appelle l'ensemble quotient de E par R, noté E/R.

Exemple : « est né la même année que ». La classe d'un élève regroupe tous les élèves nés la même année que lui ; il y a autant de classes que d'années de naissance différentes dans la classe.

13. Relations d'ordre

Une relation R est une relation d'ordre si elle est réflexive, antisymétrique et transitive.

• Si elle est en plus totale, c'est un ordre total : elle permet d'ordonner tous les éléments de l'ensemble (exemple : ≤ sur ℕ).
• Sinon, c'est un ordre partiel : certains éléments ne sont pas comparables. Exemple : « divise » sur ℕ* est une relation d'ordre, mais ni 2 ne divise 3 ni 3 ne divise 2.

Équivalence et ordre ont en commun réflexive et transitive. Ce qui les distingue : symétrique pour l'équivalence, antisymétrique pour l'ordre.