Fiche de révision : Logique Ensembles et Applications

📋 Plan du Cours

1. Propositions et quantificateurs
2. Méthodes de démonstration
3. Ensembles et opérations
4. Applications et opérations associées
5. Injections surjections et bijections
6. Équivalences et ordres

📖 1. Propositions et quantificateurs

🔑 Notions clés & Définitions

• Proposition : Énoncé qui est soit vrai, soit faux.

★ À maîtriser

📌 Une implication est fausse uniquement lorsque son hypothèse est vraie et sa conclusion fausse, tandis qu’elle est vraie dès que son hypothèse est fausse.

• Une implication équivaut à sa contraposée, mais pas nécessairement à sa réciproque.

• Pour nier une proposition quantifiée, on remplace chaque quantificateur universel par un quantificateur existentiel et inversement, sans changer leur ordre ni les ensembles associés, puis on nie la propriété finale.

Compléments

• Le quantificateur existentiel unique signifie qu’il existe exactement un élément satisfaisant la propriété.

💡 Astuce mémo

Implication ≠ réciproque

📖 2. Méthodes de démonstration

★ À maîtriser

• Un raisonnement par analyse-synthèse détermine d’abord les conditions nécessaires d’une solution supposée, puis vérifie que les candidats obtenus sont effectivement solutions.

• Pour prouver une implication par contraposition, on prouve que la négation de la conclusion entraîne la négation de l’hypothèse.

• Un raisonnement par l’absurde suppose la conclusion fausse et déduit une contradiction.

• La récurrence simple s’appuie sur une initialisation et sur l’hérédité, qui fait passer d’un rang au suivant.

📌 La récurrence double initialise deux rangs, tandis que la récurrence forte permet d’utiliser tous les rangs précédents.

Compléments

📌 Une preuve par disjonction des cas traite séparément des situations qui couvrent toutes les possibilités.

💡 Astuce mémo

Analyse puis synthèse : trouver, puis vérifier

📖 3. Ensembles et opérations

🔑 Notions clés & Définitions

• Inclusion : Ensemble A dont tout élément appartient à l’ensemble B.
• Partition : Famille de parties deux à deux disjointes et non vides, dont la réunion est l’ensemble entier.

• Ensemble des parties : Ensemble dont les éléments sont toutes les parties de E.
• Produit cartésien : Ensemble des couples dont le premier élément appartient au premier ensemble et le second au deuxième.

📝 Points essentiels

• Deux ensembles sont égaux si et seulement si chacun est inclus dans l’autre.

• Pour démontrer une inclusion, on prend un élément du premier ensemble et on montre qu’il appartient au second ; pour démontrer une égalité, on prouve les deux inclusions ou on établit des équivalences successives.

📖 4. Applications et opérations associées

🔑 Notions clés & Définitions

• Application : Correspondance qui associe à chaque élément de E un unique élément de F.

• Image réciproque : Ensemble des éléments du domaine dont l’image appartient à la partie considérée de l’ensemble d’arrivée.
• Fonction indicatrice : Fonction qui vaut 1 sur la partie considérée et 0 en dehors.
• Composition : Application qui applique d’abord la première fonction, puis la seconde au résultat obtenu.

★ À maîtriser

📌 L’image directe d’une partie rassemble ses images dans l’ensemble d’arrivée, tandis que son image réciproque rassemble les antécédents d’une partie de l’ensemble d’arrivée.

Compléments

• La composition des applications est associative, mais elle n’est pas commutative en général.

💡 Astuce mémo

Image directe : éléments atteints ; image réciproque : antécédents

📖 5. Injections surjections et bijections

🔑 Notions clés & Définitions

• Injection : Une application est injective lorsque chaque élément de l’ensemble d’arrivée a au plus un antécédent.
• Surjection : Une application est surjective lorsque chaque élément de l’ensemble d’arrivée a au moins un antécédent.
• Bijection : Application à la fois injective et surjective, pour laquelle chaque élément de l’ensemble d’arrivée a exactement un antécédent.

★ À maîtriser

• Une application est bijective si et seulement si elle admet une application réciproque dont les compositions dans les deux ordres donnent les identités sur les ensembles concernés.

Compléments

• La composée de deux applications injectives est injective, celle de deux applications surjectives est surjective, et celle de deux applications bijectives est bijective.

• Pour établir qu’une application est bijective et déterminer sa réciproque, on résout l’équation qui fixe son image et on vérifie qu’elle possède exactement une solution pour chaque élément de l’ensemble d’arrivée.

💡 Astuce mémo

Une flèche par élément pour la bijection : chaque arrivée est atteinte une seule fois

📖 6. Équivalences et ordres

🔑 Notions clés & Définitions

• Relation d’équivalence : Relation réflexive, symétrique et transitive.
• Relation d’ordre : Relation réflexive, antisymétrique et transitive.

★ À maîtriser

• Les classes d’équivalence d’une relation d’équivalence forment une partition de l’ensemble, et deux éléments sont équivalents si et seulement s’ils appartiennent à la même classe.

📌 Un ordre est total si deux éléments quelconques sont toujours comparables ; sinon, il est partiel.

Compléments

• La congruence modulo un entier définit une relation d’équivalence ; les congruences sont compatibles avec l’addition et la multiplication.

• Pour vérifier qu’une relation est une équivalence ou un ordre, on contrôle une à une les trois propriétés requises ; pour montrer qu’une propriété échoue, un seul contre-exemple explicite suffit.

💡 Astuce mémo

Équivalence : réflexive, symétrique, transitive ; ordre : réflexive, antisymétrique, transitive