Maths Sup (MPSI) — chapitre 1 sur 13

Logique, ensembles et applications

Q: Comment nier une proposition avec des quantificateurs ?

On échange ∀ et ∃ et on nie la propriété finale : la négation de « ∀ x, ∃ y, P(x,y) » est « ∃ x, ∀ y, non P(x,y) ».

Q: Quand utiliser la contraposée plutôt que l'absurde ?

Pour prouver P⇒ Q, la contraposée démontre non Q⇒non P ; l'absurde suppose P et non Q pour aboutir à une contradiction. La contraposée est souvent plus propre quand non Q est facile à exploiter.

Savoir nier une proposition avec quantificateurs et reconnaître injection, surjection, bijection : les réflexes de toute l'année.

Propriété — négation

$\text{non}(\forall x,\ P(x)) \equiv \exists x,\ \text{non}\,P(x)$ ; $\text{non}(\exists x,\ P(x))\equiv\forall x,\ \text{non}\,P(x)$ ; $\text{non}(P\Rightarrow Q)\equiv P\ \text{et non}\,Q$. L'ordre des quantificateurs compte : $\forall x\,\exists y$ n'est pas $\exists y\,\forall x$.

Méthode — raisonnements

Contraposée : $P\Rightarrow Q$ équivaut à $\text{non}\,Q\Rightarrow\text{non}\,P$.
Absurde : supposer $\text{non}\,Q$ et aboutir à une contradiction.
Récurrence simple, forte ($P(0),\ldots,P(n)\Rightarrow P(n+1)$), double.
Analyse-synthèse : on suppose une solution et on trouve ses propriétés nécessaires, puis on vérifie qu'elles conviennent.

Définition — opérations sur les ensembles

$A\cap B$, $A\cup B$, $A\setminus B$, complémentaire $\bar A$, produit $A\times B$, ensemble des parties $\mathcal P(E)$. Lois de De Morgan : $\overline{A\cup B} = \bar A\cap\bar B$, $\overline{A\cap B} = \bar A\cup\bar B$.

Définition — application

$f : E\to F$ associe à tout $x\in E$ un unique $f(x)\in F$. Image directe $f(A) = \{f(x),\ x\in A\}$ ; image réciproque $f^{-1}(B) = \{x\in E,\ f(x)\in B\}$. Composée $g\circ f$.

Définition — injection, surjection, bijection

$f$ est injective si $f(x) = f(y)\Rightarrow x = y$ ; surjective si tout $y\in F$ a au moins un antécédent ; bijective si les deux (tout $y$ a un unique antécédent). Alors $f^{-1} : F\to E$ existe et $f^{-1}\circ f = \text{id}_E$.

Propriété — composition

La composée de deux injections (resp. surjections, bijections) est une injection (resp. …). Si $g\circ f$ est injective, $f$ l'est ; si $g\circ f$ est surjective, $g$ l'est. $(g\circ f)^{-1} = f^{-1}\circ g^{-1}$.

Définition — relations

Relation d'équivalence : réflexive, symétrique, transitive (classes d'équivalence, partition). Relation d'ordre : réflexive, antisymétrique, transitive ; ordre total si deux éléments sont toujours comparables. Majorant, borne supérieure (plus petit des majorants).

Questions fréquentes sur ce chapitre

Comment nier une proposition avec des quantificateurs ?

On échange $\forall$ et $\exists$ et on nie la propriété finale : la négation de « $\forall x,\ \exists y,\ P(x,y)$ » est « $\exists x,\ \forall y,\ \text{non}\,P(x,y)$ ».

Quelle est la différence entre injection et surjection ?

Injective : deux éléments distincts ont des images distinctes. Surjective : tout élément de l'ensemble d'arrivée a au moins un antécédent. Bijective : les deux, chaque élément a exactement un antécédent.

Qu'est-ce qu'un raisonnement par analyse-synthèse ?

On suppose qu'une solution existe et on en déduit sa forme nécessaire (analyse), puis on vérifie que les candidats trouvés conviennent effectivement (synthèse).

Quand utiliser la contraposée plutôt que l'absurde ?

Pour prouver $P\Rightarrow Q$, la contraposée démontre $\text{non}\,Q\Rightarrow\text{non}\,P$ ; l'absurde suppose $P$ et $\text{non}\,Q$ pour aboutir à une contradiction. La contraposée est souvent plus propre quand $\text{non}\,Q$ est facile à exploiter.

Télécharger cette synthèse en PDF Fiche imprimable, définitions et théorèmes sans la figure interactive.