Fiche de révision : Ensembles et applications

📋 Plan du Cours

1. Ensembles et opérations ensemblistes
2. Produits cartésiens et applications
3. Images et composition des applications
4. Injection et preuve d’injectivité
5. Surjection et bijection
6. Cardinal des ensembles finis
7. Cardinalité des applications
8. Ensembles en Python et SQL

📖 1. Ensembles et opérations ensemblistes

🔑 Notions clés & Définitions

• Ensemble : Collection d’objets bien déterminés, appelés ses éléments.
• Inclusion : Tout élément de A appartient à B.
• Ensemble des parties : Ensemble de tous les sous-ensembles de E, de sorte que A ∈ P(E) équivaut à A ⊂ E.
• Union : Contient les éléments qui appartiennent à A ou à B.
• Intersection : Contient les éléments qui appartiennent à la fois à A et à B.
• Complémentaire : Si A ⊂ E, ensemble des éléments de E qui n’appartiennent pas à A.
• Différence ensembliste : Ensemble des éléments de A qui n’appartiennent pas à B.

★ À maîtriser

📌 Dans un ensemble, l’ordre et les répétitions ne comptent pas, contrairement à une liste Python qui conserve l’ordre et les doublons.

Compléments

📌 Deux ensembles A et B sont égaux si et seulement si A ⊂ B et B ⊂ A.

• L’ensemble vide ∅ est inclus dans tout ensemble A.

📐 Formule - Si E est un ensemble fini de cardinal n, alors $|P(E)| = 2^n$.

• A et B sont disjoints si A ∩ B = ∅.

• Les lois de De Morgan donnent le complémentaire de A ∩ B égal à A complémentaire ∪ B complémentaire, et le complémentaire de A ∪ B égal à A complémentaire ∩ B complémentaire.

💡 Astuce mémo

Un ensemble ignore l’ordre et les répétitions ; une liste les conserve.

📖 2. Produits cartésiens et applications

🔑 Notions clés & Définitions

• Produit cartésien : Ensemble des couples (x, y) tels que x ∈ E et y ∈ F.
• Application : Associe à chaque élément x de E un unique élément f(x) de F.

★ À maîtriser

📌 Pour qu’une relation soit une application de E vers F, chaque élément de E doit avoir exactement une image, tandis qu’un élément de F peut recevoir zéro, une ou plusieurs flèches.

Compléments

📌 Dans un couple, l’ordre compte : (1, 2) ≠ (2, 1), alors que {1, 2} = {2, 1}.

• La fonction x ↦ √x n’est pas une application de ℝ dans ℝ, car −1 n’a pas d’image réelle, mais elle est une application de [0, +∞[ dans ℝ.

• Un dictionnaire Python associe à chaque clé une seule valeur, mais plusieurs clés peuvent avoir la même valeur.

📖 3. Images et composition des applications

🔑 Notions clés & Définitions

• Image directe : Pour f : E → F et A ⊂ E, ensemble des images des éléments de A : f(A) = {f(x) | x ∈ A} ⊂ F.
• Image réciproque : Pour f : E → F et B ⊂ F, ensemble des x ∈ E tels que f(x) ∈ B.
• Composition : Pour f : E → F et g : F → G, la composée g ◦ f : E → G est définie par (g ◦ f)(x) = g(f(x)).

📝 Points essentiels

• Pour f : ℝ → ℝ définie par f(x) = x², l’image directe de [−1, 2] est [0, 4].

📌 La composition n’est généralement pas commutative : pour f(x) = x + 1 et g(x) = x², (g ◦ f)(x) = (x + 1)² alors que (f ◦ g)(x) = x² + 1.

📖 4. Injection et preuve d’injectivité

🔑 Notions clés & Définitions

• Injection : Application f : E → F telle que, pour tous x, x′ ∈ E, f(x) = f(x′) implique x = x′.

📝 Points essentiels

📌 Une application est injective si et seulement si chaque élément de F a au plus un antécédent.

• Pour prouver l’injectivité de f, on suppose f(x) = f(x′) pour des éléments quelconques du domaine, puis on démontre que x = x′.

• L’application f : ℝ → ℝ définie par f(x) = 3x + 2 est injective.

• L’application g : ℝ → ℝ définie par g(x) = x² n’est pas injective, car g(−1) = g(1) = 1 alors que −1 ≠ 1.

💡 Astuce mémo

Une injection ressemble à un entonnoir sans collision : chaque arrivée reçoit au plus une flèche.

📖 5. Surjection et bijection

🔑 Notions clés & Définitions

• Surjection : Application f : E → F telle que tout y ∈ F possède au moins un antécédent x ∈ E tel que f(x) = y.
• Bijection : Application f : E → F à la fois injective et surjective, c’est-à-dire telle que chaque y ∈ F possède un unique antécédent x ∈ E.
• Bijection : Application à la fois injective et surjective, ce qui signifie que chaque élément de l’ensemble d’arrivée possède exactement un antécédent.
• Application réciproque : Si f est bijective de E vers F, son application réciproque f⁻¹ de F vers E associe à chaque y son unique antécédent et vérifie f⁻¹ ∘ f = idE et f ∘ f⁻¹ = idF.

★ À maîtriser

📌 Une même formule peut définir une application injective ou non, et surjective ou non, selon les ensembles de départ et d’arrivée.

Compléments

📌 Une application f : E → F est surjective si et seulement si f(E) = F.

• Pour prouver qu’une application est surjective, on fixe un y ∈ F quelconque et on trouve un x ∈ E tel que f(x) = y.

• L’application f : ℝ → ℝ définie par f(x) = 3x + 2 est surjective, car pour tout y ∈ ℝ, x = (y − 2)/3 vérifie f(x) = y.

• L’application g : ℝ → ℝ définie par g(x) = x² n’est pas surjective, car −1 n’a pas d’antécédent dans ℝ.

• Pour f(x) = 3x + 2 de ℝ vers ℝ, l’application est bijective et son application réciproque est f⁻¹(y) = (y − 2)/3.

• Le chiffrement de César sur E = {0, …, 25} associe à x la valeur c(x) = (x + 3) mod 26, et le déchiffrement utilise c⁻¹(y) = (y − 3) mod 26.

📌 Un codage réversible, comme une compression sans perte ou un chiffrement, doit être injectif.

• La fonction n ↦ n² de ℕ vers ℕ est injective mais non surjective, tandis que la fonction n ↦ n − 7 de ℤ vers ℤ est bijective et a pour réciproque m ↦ m + 7.

💡 Astuce mémo

Injection : au plus un antécédent ; surjection : au moins un antécédent.

📖 6. Cardinal des ensembles finis

🔑 Notions clés & Définitions

• Cardinal : Nombre d’éléments d’un ensemble fini.

★ À maîtriser

📐 Formule - Pour deux ensembles finis A et B, la formule du crible est $\operatorname{Card}(A \cup B) = \operatorname{Card}(A) + \operatorname{Card}(B) - \operatorname{Card}(A \cap B)$.

📐 Formule - Pour deux ensembles finis E et F, $\operatorname{Card}(E \times F) = \operatorname{Card}(E) \times \operatorname{Card}(F)$ et $\operatorname{Card}(E^k) = \operatorname{Card}(E)^k$.

Compléments

📌 Si A est inclus dans un ensemble fini B, alors $\operatorname{Card}(A) \leq \operatorname{Card}(B)$ et $\operatorname{Card}(B \setminus A) = \operatorname{Card}(B) - \operatorname{Card}(A)$.

📌 Si deux ensembles finis A et B sont disjoints, alors $\operatorname{Card}(A \cup B) = \operatorname{Card}(A) + \operatorname{Card}(B)$.

📐 Formule - Si E a n éléments, son ensemble des parties a $\operatorname{Card}(\mathcal{P}(E)) = 2^n$ éléments.

• Un code PIN de 4 chiffres possède 10⁴, soit 10 000, possibilités, et un octet possède 2⁸, soit 256, valeurs possibles.

📖 7. Cardinalité des applications

🔑 Notions clés & Définitions

• Principe des tiroirs : Si l’on range n objets dans k tiroirs avec n > k, au moins un tiroir contient au moins deux objets.

★ À maîtriser

📌 Pour une application f entre deux ensembles finis E et F, l’injectivité implique Card(E) ≤ Card(F), la surjectivité implique Card(E) ≥ Card(F), et la bijectivité implique Card(E) = Card(F).

📌 Pour deux ensembles finis de même cardinal, une application de l’un vers l’autre est injective si et seulement si elle est surjective, et ces propriétés équivalent à la bijectivité.

Compléments

📌 Si Card(E) > Card(F), aucune application de E vers F ne peut être injective.

• Parmi 367 personnes, au moins deux ont la même date d’anniversaire, définie par le jour et le mois.

• Une fonction de hachage envoyant l’ensemble immense des fichiers vers un ensemble fini d’empreintes de 256 bits ne peut pas être injective, donc des collisions existent forcément.

• Un identifiant composé de 3 chiffres offre 10³, soit 1000, possibilités ; 1001 utilisateurs entraînent donc une collision par le principe des tiroirs.

💡 Astuce mémo

L’injection évite les collisions ; la surjection atteint toutes les cibles.

📖 8. Ensembles en Python et SQL

📝 Points essentiels

• En Python, l’union, l’intersection et la différence de deux ensembles A et B s’écrivent respectivement A | B, A & B et A - B.

• En SQL, UNION, INTERSECT et EXCEPT réalisent respectivement l’union, l’intersection et la différence des résultats de deux requêtes.

• En SQL, CROSS JOIN construit le produit cartésien de deux tables ; avec 30 étudiants et 8 modules, il produit 240 lignes.

• En SQL, la clause WHERE permet de définir un ensemble par propriété, à la manière de {x ∈ E | P(x)}.