Ficha de revisão: Raisonnement et vocabulaire ensembliste

📋 Plan du Cours

1. Propositions et connecteurs logiques
2. Quantificateurs et négation
3. Méthodes de démonstration
4. Récurrence et analyse-synthèse
5. Opérations sur les ensembles
6. Applications, dénombrement et relations
7. Schémas de démonstration et récurrence
8. Calculs sur les ensembles et applications
9. Formules et problèmes de dénombrement
10. Exemples de récurrence avancée
11. Applications aux partitions et sommes

📖 1. Propositions et connecteurs logiques

🔑 Notions clés & Définitions

• Table de vérité : Tableau indiquant si une proposition construite à partir de propositions élémentaires est vraie ou fausse selon leurs valeurs de vérité.
• Implication : L’implication A ⇒ B est définie par la proposition non A ou B.
• Équivalence : L’équivalence A ⇔ B est définie par (A ⇒ B) ∧ (B ⇒ A), et elle est vraie lorsque A et B sont simultanément vraies ou fausses.

📝 Points essentiels

📌 Dans l’implication A ⇒ B, A est une condition suffisante pour B, tandis que B est une condition nécessaire pour A.

• La contraposition vérifie $A \Rightarrow B \Longleftrightarrow \neg B \Rightarrow \neg A$.

💡 Astuce mémo

Implication : condition suffisante → condition nécessaire ; équivalence : nécessaire et suffisante

📖 2. Quantificateurs et négation

🔑 Notions clés & Définitions

• Quantificateur existentiel : Le quantificateur existentiel ∃x ∈ E, A(x) signifie qu’au moins un élément de E vérifie A(x).
• Quantificateur universel : Le quantificateur universel ∀x ∈ E, A(x) signifie que tous les éléments de E vérifient A(x).

📝 Points essentiels

📌 Les propositions ∃x ∀y A(x,y) et ∀y ∃x A(x,y) ne signifient pas la même chose, car l’élément x peut dépendre de y dans la seconde.

• La négation d’un énoncé universel vérifie $\neg(\forall x\,A(x))\Longleftrightarrow\exists x\,\neg A(x)$ et la négation d’un énoncé existentiel vérifie $\neg(\exists x\,A(x))\Longleftrightarrow\forall x\,\neg A(x)$.

💡 Astuce mémo

Existence : au moins un ; universalité : tous

📖 3. Méthodes de démonstration

📝 Points essentiels

• Pour démontrer une proposition A directement, on établit une condition suffisante B puis on démontre B ⇒ A.

• Pour démontrer une proposition par l’absurde, on suppose A fausse et on en déduit une contradiction.

📌 Pour prouver une implication P ⇒ Q, on peut démontrer sa contraposée ¬Q ⇒ ¬P, qui lui est équivalente.

• Pour prouver une équivalence P ⇔ Q par double implication, il faut démontrer séparément P ⇒ Q et Q ⇒ P.

💡 Astuce mémo

Directe, absurde, contraposition, double implication

📖 4. Récurrence et analyse-synthèse

📝 Points essentiels

📌 Le principe de récurrence affirme qu’une partie A de N contenant 0 et stable par passage de n à n+1 est égale à N.

• Pour démontrer P(n) pour tout n ≥ n₀ par récurrence simple, il faut établir P(n₀), puis P(n) ⇒ P(n+1) pour tout n ≥ n₀.

📌 Dans une analyse-synthèse, l’analyse suppose le problème résolu et recherche des conditions nécessaires, tandis que la synthèse vérifie si ces conditions sont suffisantes.

💡 Astuce mémo

Initialisation → hérédité → conclusion

📖 5. Opérations sur les ensembles

🔑 Notions clés & Définitions

• Réunion : Ensemble des éléments qui appartiennent à A ou à B, le « ou » étant inclusif.
• Intersection : Ensemble des éléments qui appartiennent à la fois à A et à B.
• Complémentaire : Ensemble des éléments de E qui n’appartiennent pas à A.
• Inclusion : Lorsque tout élément de A est un élément de B.
• Partition : Une famille (Xᵢ)ᵢ∈I est une partition de E lorsque sa réunion est E, que deux ensembles distincts sont disjoints et qu’aucun Xᵢ n’est vide.

📝 Points essentiels

📐 Formule — Les lois de De Morgan donnent $\complement(A\cap B)=\complement A\cup\complement B$ et $\complement(A\cup B)=\complement A\cap\complement B$.

💡 Astuce mémo

RIC : réunion, intersection, complémentaire

📖 6. Applications, dénombrement et relations

🔑 Notions clés & Définitions

• Application : Procédé qui associe à tout élément x de E un unique élément f(x) de F.
• Fonction caractéristique : La fonction caractéristique 1_A d’un sous-ensemble A de E vaut 1 sur A et 0 sur E \ A.
• Relation d’équivalence : Une relation binaire est une relation d’équivalence lorsqu’elle est réflexive, symétrique et transitive.
• Relation d’ordre : Une relation binaire est une relation d’ordre lorsqu’elle est réflexive, antisymétrique et transitive.

📝 Points essentiels

📐 Formule — La composition de f : E → F et g : F → G est définie par $g\circ f(x)=g(f(x))$.

📌 Une application est injective si deux images égales impliquent l’égalité des antécédents, surjective si tout élément du codomaine possède un antécédent, et bijective si elle est à la fois injective et surjective.

📐 Formule — Si E et F sont finis, le nombre d’applications de E dans F est $\operatorname{Card}(F^E)=(\operatorname{Card}F)^{\operatorname{Card}E}$.

📐 Formule — Le nombre de p-combinaisons d’un ensemble de cardinal n est $\binom{n}{p}=\frac{n!}{p!(n-p)!}$ pour 0 ≤ p ≤ n, et il vaut 0 pour p > n.

• Les classes d’équivalence d’une relation d’équivalence forment une partition de l’ensemble.

📌 Un ordre est total lorsque deux éléments quelconques sont comparables, et il est partiel lorsqu’au moins une paire d’éléments ne l’est pas.

💡 Astuce mémo

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

📖 7. Schémas de démonstration et récurrence

📝 Points essentiels

• Pour exploiter un schéma logique de la forme $A\Rightarrow(B\Rightarrow C)$, il est souvent efficace de partir de l’hypothèse B, puis d’utiliser A au moment nécessaire pour établir C.

📌 Une implication $A\Rightarrow B$ est une proposition qui peut être vraie ou fausse, indépendamment de la vérité de A et de B prises séparément.

• Pour démontrer une propriété par récurrence simple, on démontre l’initialisation puis, pour tout $n\ge n_0$, on établit $P(n)\Rightarrow P(n+1)$.

💡 Astuce mémo

Départ B, puis implication vers C

📖 8. Calculs sur les ensembles et applications

🔑 Notions clés & Définitions

• Différence symétrique : La différence symétrique de deux sous-ensembles A et B est $A\triangle B=(A\setminus B)\cup(B\setminus A)$.

📝 Points essentiels

• Pour montrer l’égalité de deux ensembles A et B, on peut établir les deux inclusions $A\subset B$ et $B\subset A$, raisonner élément par élément, combiner ces méthodes, comparer des propriétés caractérisantes ou montrer l’égalité de leurs fonctions caractéristiques.

📐 Formule — La fonction caractéristique transforme les opérations ensemblistes en calculs algébriques, notamment $\mathbf{1}_{A\cap B}=\mathbf{1}_A\mathbf{1}_B$ et $\mathbf{1}_{A\cup B}=\mathbf{1}_A+\mathbf{1}_B-\mathbf{1}_A\mathbf{1}_B$.

💡 Astuce mémo

Inclusion globale ou preuve élément par élément

📖 9. Formules et problèmes de dénombrement

📝 Points essentiels

📐 Formule — Pour deux ensembles finis A et B, la formule d’inclusion-exclusion à deux ensembles est $\operatorname{Card}(A\cap B)+\operatorname{Card}(A\cup B)=\operatorname{Card}(A)+\operatorname{Card}(B)$.

📌 Deux ensembles finis qui sont en bijection ont le même cardinal.

📌 Pour une application entre deux ensembles finis de même cardinal, l’injectivité, la surjectivité et la bijectivité sont des propriétés équivalentes.

📐 Formule — Le coefficient binomial $\binom{n}{p}$ compte les parties de cardinal p d’un ensemble de cardinal n et vérifie $\binom{n}{p}+\binom{n}{p-1}=\binom{n+1}{p}$.

📐 Formule — Pour $0<p<n$, le coefficient binomial vérifie $\binom{n}{p}=\frac{n!}{p!(n-p)!}$.

💡 Astuce mémo

Bijection → égalité des cardinaux

📖 10. Exemples de récurrence avancée

🔑 Notions clés & Définitions

• Suite de Fibonacci : Suite définie par $F_0=0$, $F_1=1$ et $F_{n+2}=F_{n+1}+F_n$ pour tout entier naturel n.

📝 Points essentiels

📐 Formule — Les sommes usuelles des carrés et des cubes sont $\sum_{k=0}^{n}k^2=\frac{n(n+1)(2n+1)}{6}$ et $\sum_{k=0}^{n}k^3=\left(\frac{n(n+1)}{2}\right)^2$.

📐 Formule — Pour des entiers $n>p\ge0$, la somme des coefficients binomiaux vérifie $\sum_{k=p}^{n}\binom{k}{p}=\binom{n+1}{p+1}$.

💡 Astuce mémo

Initialiser, transmettre, conclure

📖 11. Applications aux partitions et sommes

📝 Points essentiels

📐 Formule — Pour un ensemble E de cardinal n, le nombre de ses parties est $2^n$ et vérifie $\sum_{k=0}^{n}\binom{n}{k}=2^n$.

📐 Formule — Pour des entiers naturels n, p et q, la convolution des coefficients binomiaux vérifie $\sum_{k=0}^{n}\binom{p}{k}\binom{q}{n-k}=\binom{p+q}{n}$.

📐 Formule — Le nombre de partitions d’un ensemble de cardinal np en sous-ensembles non ordonnés de cardinal p est $\frac{(np)!}{(p!)^n n!}$.

• Pour une famille finie de p ensembles, la formule du crible alterne les sommes des cardinalités des intersections de 1, 2, jusqu’à p ensembles, avec un signe $(-1)^{r+1}$ pour les intersections de r ensembles.

📊 Tableaux de synthèse

Types d’applications

Type	Condition sur les images	Antécédents de chaque élément du codomaine
Injective	Deux antécédents distincts ont des images distinctes	Au plus un
Surjective	Tout élément du codomaine est atteint	Au moins un
Bijective	Injective et surjective	Exactement un

Méthodes de preuve

Problème	Méthodes principales	Outil caractéristique
Égalité d’ensembles	Deux inclusions ou raisonnement élément par élément	Fonctions caractéristiques
Récurrence simple	Initialisation puis P(n) ⇒ P(n+1)	Un rang précédent
Récurrence forte	Initialisation puis tous les rangs précédents	Plusieurs rangs précédents
Dénombrement	Bijection ou partition	Égalité des cardinaux