Fiche de révision : Ensembles, applications et cardinalité

📋 Plan du Cours

1. Ensembles et appartenance
2. Inclusion et opérations ensemblistes
3. Parties et produits cartésiens
4. Applications et images
5. Injection, surjection et bijection
6. Cardinalité et dénombrement
7. Ensembles et applications en informatique

📖 1. Ensembles et appartenance

🔑 Notions clés & Définitions

• Ensemble : Une collection d’objets bien déterminés, appelés ses éléments.

★ À 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

📌 L’appartenance s’écrit x ∈ E, tandis que la non-appartenance s’écrit x ∉ E.

📌 Un ensemble peut être défini en extension en listant ses éléments ou en compréhension en indiquant la propriété qu’ils vérifient.

💡 Astuce mémo

Ensemble : sans ordre ni doublons ; liste : ordre et doublons conservés.

📖 2. Inclusion et opérations ensemblistes

🔑 Notions clés & Définitions

• Inclusion : L’inclusion A ⊂ B signifie que tout élément de A appartient aussi à B.
• Union : L’union A ∪ B est l’ensemble des éléments qui appartiennent à A ou à B.
• Intersection : L’intersection A ∩ B est l’ensemble des éléments qui appartiennent à la fois à A et à B.
• Complémentaire : Si A ⊂ E, le complémentaire de A dans E est l’ensemble des éléments de E qui n’appartiennent pas à A.
• Différence : La différence A \ B est l’ensemble des éléments qui appartiennent à A et n’appartiennent pas à B.

★ À maîtriser

• Pour démontrer A = B, on démontre séparément A ⊂ B et B ⊂ A.

Compléments

📌 Deux ensembles A et B sont disjoints si et seulement si A ∩ B = ∅.

📌 L’intersection, l’union, le complémentaire, l’inclusion et l’égalité correspondent respectivement aux connecteurs logiques ∧, ∨, ¬, ⇒ et ⇔ appliqués aux énoncés d’appartenance.

• Les lois de De Morgan donnent le complémentaire d’une intersection comme l’union des complémentaires, et le complémentaire d’une union comme l’intersection des complémentaires.

💡 Astuce mémo

∈ relie un élément à un ensemble ; ⊂ relie deux ensembles.

📖 3. Parties et produits cartésiens

🔑 Notions clés & Définitions

• Ensemble des parties : L’ensemble des parties P(E) contient exactement les sous-ensembles de E.
• Produit cartésien : Le produit cartésien E × F est l’ensemble des couples ordonnés (x, y) tels que x ∈ E et y ∈ F.

★ À maîtriser

📐 Formule - Si E est fini et contient n éléments, alors $\operatorname{Card}(\mathcal{P}(E))=2^n$.

Compléments

📌 En général, E × F ≠ F × E, car les couples ordonnés n’ont pas nécessairement les mêmes premiers et seconds termes.

💡 Astuce mémo

Une partie devient un mot binaire : chaque élément est dedans (1) ou dehors (0).

📖 4. Applications et images

🔑 Notions clés & Définitions

• Application : Une application f : E → F associe à chaque élément de E un unique élément de F.
• Image directe : Pour f : E → F et A ⊂ E, l’image directe f(A) est l’ensemble des images des éléments de A et est inclus dans F.
• Image réciproque : Pour f : E → F et B ⊂ F, l’image réciproque f⁻¹(B) est l’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

• Dans une application f : E → F, E est l’ensemble de départ, F l’ensemble d’arrivée, f(x) l’image de x et x un antécédent de f(x).

• La règle x ↦ √x ne définit pas une application de ℝ dans ℝ, car les réels négatifs n’y ont pas d’image réelle, mais elle définit une application de [0, +∞[ dans ℝ.

• La notation f⁻¹(B) désigne l’image réciproque d’un ensemble B et existe même lorsque f n’est pas bijective ; elle ne désigne pas nécessairement une fonction réciproque.

📖 5. Injection, surjection et bijection

🔑 Notions clés & Définitions

• Injection : Une application f : E → F est injective si f(x) = f(x′) implique x = x′ ; deux éléments distincts ne peuvent donc pas avoir la même image.
• Surjection : Une application f : E → F est surjective si chaque y ∈ F possède au moins un antécédent, ce qui équivaut à f(E) = F.
• Bijection : Une application est bijective si elle est à la fois injective et surjective, c’est-à-dire si chaque élément d’arrivée possède un unique antécédent.
• Application réciproque : Si f : E → F est bijective, sa réciproque f⁻¹ : F → E associe à chaque y son unique antécédent.

📝 Points essentiels

• Pour démontrer l’injectivité, on suppose f(x) = f(x′) pour des éléments quelconques et on établit x = x′.

• Pour réfuter l’injectivité, il suffit de trouver deux éléments distincts ayant la même image.

📌 Pour des ensembles finis E et F de même cardinal, une application f : E → F est injective si et seulement si elle est surjective, et ces propriétés équivalent à la bijectivité.

💡 Astuce mémo

Injective : au plus un antécédent ; surjective : au moins un ; bijective : exactement un.

📖 6. Cardinalité et dénombrement

🔑 Notions clés & Définitions

• Cardinal : Le cardinal d’un ensemble fini E, noté Card(E) ou |E|, est son nombre d’éléments.
• Principe des tiroirs : Si n objets sont rangés dans k tiroirs avec n > k, au moins un tiroir contient au moins deux objets.

★ À maîtriser

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

📐 Formule - Pour des 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$.

📌 Pour une application f : E → F entre ensembles finis, l’injectivité implique Card(E) ≤ Card(F), la surjectivité implique Card(E) ≥ Card(F), et la bijectivité implique l’égalité des cardinaux.

Compléments

📌 Si A ⊂ B et si A et B sont finis, alors Card(A) ≤ Card(B) et Card(B \ A) = Card(B) − Card(A).

📌 Si E et F sont finis et Card(E) > Card(F), aucune application de E vers F n’est injective.

💡 Astuce mémo

Plus d’objets que de tiroirs → au moins deux objets dans un même tiroir.

📖 7. Ensembles et applications en informatique

★ À maîtriser

• Dans un dictionnaire Python, chaque clé est associée à une seule valeur, mais plusieurs clés peuvent avoir la même valeur.

• Une fonction de hachage qui envoie un ensemble immense de fichiers vers un ensemble fini d’empreintes ne peut pas être injective, donc des collisions existent.

Compléments

• Un tableau Python peut être modélisé comme une application de ses indices vers ses valeurs.

• Une adresse IPv4 composée de quatre octets possède $2^{32}$ valeurs possibles, soit environ 4,3 × 10⁹.

• En SQL, UNION, INTERSECT et EXCEPT réalisent respectivement l’union, l’intersection et la différence ensemblistes, tandis que CROSS JOIN produit un produit cartésien.

📊 Tableaux de synthèse

Propriétés des applications