Fiche de révision : Ensembles et applications

📋 Plan du Cours

1. Ensembles et opérations
2. Produits cartésiens et applications
3. Images et composition
4. Injection et surjection
5. Bijection et application réciproque
6. Bijections et applications réciproques
7. Cardinal des ensembles finis
8. Formules de dénombrement
9. Cardinalité et principe des tiroirs
10. Ensembles en Python et SQL

📖 1. Ensembles et opérations

🔑 Notions clés & Définitions

• Inclusion : A est inclus dans B si tout élément de A appartient à B.
• Ensemble des parties : L’ensemble de tous les sous-ensembles de E.
• Ensemble : Collection d’objets bien déterminés, appelés ses éléments.
• Union : L’union A ∪ B contient les éléments qui appartiennent à A ou à B.
• Intersection : L’intersection A ∩ B contient les é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 ensembliste : La différence A \ B est l’ensemble des éléments de A qui n’appartiennent pas à B.

★ À maîtriser

📌 Deux ensembles sont égaux si chacun est inclus dans l’autre, ce qui se démontre par double inclusion.

📐 Formule - Si E possède n éléments, alors $|P(E)|=2^n$.

Compléments

📌 Dans un ensemble, l’ordre et les répétitions ne comptent pas, contrairement à une liste Python où l’ordre et les doublons sont conservés.

• Un ensemble peut être défini en extension en listant ses éléments ou en compréhension en donnant une propriété vérifiée par ses éléments.

• Deux ensembles A et B sont disjoints si leur intersection est l’ensemble vide.

• Les correspondances entre logique et ensembles sont :

  • ∧ avec ∩
  • ∨ avec ∪
  • ¬ avec le complémentaire
  • P ∧ ¬Q avec A \ B
  • ⇒ avec l’inclusion
  • ⇔ avec l’égalité des ensembles

• L’union et l’intersection sont commutatives et distributives l’une par rapport à l’autre.

📌 Les lois de De Morgan donnent le complémentaire de A ∩ B comme l’union des complémentaires de A et B, et le complémentaire de A ∪ B comme l’intersection de ces complémentaires.

📖 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

• Dans une application, chaque élément de l’ensemble de départ a exactement une image, tandis qu’un élément de l’ensemble d’arrivée peut avoir zéro, un ou plusieurs antécédents.

Compléments

• E² désigne E × E et Eᵏ désigne l’ensemble des k-uplets d’éléments de E.

• La fonction réelle x ↦ √x n’est pas une application de ℝ dans ℝ, mais elle en est une de [0, +∞[ dans ℝ.

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

📖 3. Images et composition

🔑 Notions clés & Définitions

• Image directe : Pour f : E → F et A ⊂ E, ensemble des images f(x) des éléments x de A.
• 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 est définie par (g ◦ f)(x)=g(f(x)) : on applique d’abord f, puis g.

📝 Points essentiels

• Pour f(x)=x² sur ℝ, l’image directe de [−1, 2] est [0, 4], et non [f(−1), f(2)] = [1, 4], car le minimum est atteint en 0.

• En général, g ◦ f n’est pas égal à f ◦ g.

💡 Astuce mémo

Pour composer, on suit d’abord f, puis g.

📖 4. Injection et surjection

🔑 Notions clés & Définitions

• Injection : Une application f : E → F est injective si f(x)=f(x′) implique x=x′ pour tous x,x′ ∈ E.
• Surjection : Une application f : E → F est surjective si tout y ∈ F possède au moins un antécédent x ∈ E, ce qui équivaut à f(E)=F.

📝 Points essentiels

• Une application injective équivaut à une application où chaque élément de F a au plus un antécédent.

• Pour établir l’injectivité, on suppose f(x)=f(x′) et on démontre x=x′ ; pour la réfuter, on donne deux éléments distincts ayant la même image.

• Pour établir la surjectivité, on fixe y ∈ F et on résout f(x)=y en trouvant x ∈ E ; pour la réfuter, on exhibe un élément de F sans antécédent.

💡 Astuce mémo

Injective : pas de collision ; surjective : aucune cible oubliée.

📖 5. Bijection et application réciproque

🔑 Notions clés & Définitions

• Bijection : Une application f : E → F est bijective si elle est à la fois injective et surjective, c’est-à-dire si chaque y ∈ F possède un unique antécédent dans E.
• Application réciproque : Si f : E → F est bijective, f⁻¹ : F → E associe à chaque y son unique antécédent et vérifie f⁻¹ ◦ f = idE et f ◦ f⁻¹ = idF.

💡 Astuce mémo

Une bijection est un aller-retour où chaque flèche peut être inversée.

📖 6. Bijections et applications réciproques

🔑 Notions clés & Définitions

• Application réciproque : Application de F vers E qui associe à chaque y son unique antécédent x, avec y = f(x) si et seulement si x = f⁻¹(y).

★ À maîtriser

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

📌 Une même formule peut définir des applications injectives ou non, surjectives ou non, selon les ensembles de départ et d’arrivée.

Compléments

📐 Formule - Pour une bijection f : E → F, $f^{-1}\circ f=\mathrm{id}_E$ et $f\circ f^{-1}=\mathrm{id}_F$.

• Pour f : ℝ → ℝ définie par f(x) = 3x + 2, l’application est bijective et sa réciproque est f⁻¹(y) = (y − 2)/3.

• Le chiffrement de César sur E = {0, 1, …, 25} est défini par c(x) = (x + 3) mod 26 et se déchiffre par c⁻¹(y) = (y − 3) mod 26.

💡 Astuce mémo

Injective : pas de collision ; surjective : aucune arrivée oubliée.

📖 7. Cardinal des ensembles finis

🔑 Notions clés & Définitions

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

📝 Points essentiels

• Le cardinal de l’ensemble vide est 0, et Card({a, b, c}) = 3.

• Dans un ensemble, les répétitions ne comptent pas : Card({1, 1, 2}) = 2.

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

📖 8. Formules de dénombrement

★ À 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 - Si Card(E) = n, alors $\operatorname{Card}(E^k)=n^k$ et $\operatorname{Card}(\mathcal{P}(E))=2^n$.

Compléments

📌 Si A et B sont disjoints, alors Card(A ∪ B) = Card(A) + Card(B).

• Les codes PIN à 4 chiffres ont 10⁴ = 10 000 possibilités, car chaque chiffre peut prendre 10 valeurs.

💡 Astuce mémo

Dans le crible, la zone commune est comptée deux fois : on la retranche une fois.

📖 9. Cardinalité et principe des tiroirs

★ À maîtriser

• 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 Card(E) = Card(F).

• Si E et F sont finis et ont le même cardinal, alors f : E → F est injective si et seulement si elle est surjective, et ces propriétés équivalent à la bijectivité.

• Le principe des tiroirs affirme que ranger n objets dans k tiroirs avec n > k impose qu’au moins un tiroir contienne au moins deux objets.

• Si Card(E) > Card(F), aucune application de E vers F n’est injective.

Compléments

📌 La réciproque selon laquelle une application injective entre ensembles finis de même cardinal est surjective ne s’étend pas aux ensembles infinis : n ↦ 2n est injective de ℤ vers ℤ mais non surjective.

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

💡 Astuce mémo

Plus d’objets que de tiroirs → collision inévitable.

📖 10. Ensembles en Python et SQL

📝 Points essentiels

• En Python, les opérateurs |, &, -, <= et len correspondent respectivement à l’union, l’intersection, la différence, l’inclusion et au calcul du cardinal des ensembles.

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

• En SQL, CROSS JOIN construit le produit cartésien des lignes des deux tables.

📊 Tableaux de synthèse

Propriétés des applications finies