M1 — Raisonnement et vocabulaire ensembliste

Objectif du chapitre. Avant de faire des maths, il faut savoir écrire des maths. Ce chapitre pose le vocabulaire (propositions, quantificateurs, ensembles, applications) et les méthodes de démonstration (direct, contraposée, absurde, disjonction de cas, analyse-synthèse, récurrence) qui servent dans chaque chapitre du programme. Le niveau d'exigence est celui du B.O. : chaque affirmation doit être justifiée par une définition ou un théorème nommé.

Notions

1. Propositions et connecteurs logiques

Une proposition est un énoncé qui est vrai ou faux, jamais les deux. On note $P$, $Q$ deux propositions.

Connecteur	Notation	Lecture	Vraie si…
Négation	$\neg P$	non $P$	$P$ est fausse
Conjonction	$P \wedge Q$	$P$ et $Q$	$P$ et $Q$ sont toutes deux vraies
Disjonction	$P \vee Q$	$P$ ou $Q$	au moins une des deux est vraie
Implication	$P \Rightarrow Q$	si $P$ alors $Q$	$P$ fausse ou $Q$ vraie
Équivalence	$P \Leftrightarrow Q$	$P$ si et seulement si $Q$	$P$ et $Q$ de même valeur

Points d'attention.

• L'implication $P \Rightarrow Q$ est trivialement vraie dès que $P$ est fausse (prémisse fausse) : c'est la source de l'essentiel des confusions.
• La réciproque de $P \Rightarrow Q$ est $Q \Rightarrow P$ ; la contraposée est $\neg Q \Rightarrow \neg P$. La contraposée est équivalente à l'implication ; la réciproque ne l'est pas.
• La négation d'une implication : $\neg(P \Rightarrow Q) \equiv P \wedge \neg Q$.

2. Quantificateurs et leur négation

Deux quantificateurs structurent les énoncés : $\forall$ (« pour tout ») et $\exists$ (« il existe »).

$$\neg\, \forall x\, P(x) \;\Longleftrightarrow\; \exists x\, \neg P(x) \qquad \neg\, \exists x\, P(x) \;\Longleftrightarrow\; \forall x\, \neg P(x)$$

Règle pratique. Pour négater un énoncé quantifié : on inverse $\forall \leftrightarrow \exists$ et on négate la propriété à la fin. Exemples :

• $\neg\big(\forall x \in \mathbb{R},\, x^2 \geq 0\big)$ devient $\exists x \in \mathbb{R},\, x^2 < 0$.
• $\neg\big(\exists x \in \mathbb{R},\, x^2 + 1 = 0\big)$ devient $\forall x \in \mathbb{R},\, x^2 + 1 \neq 0$.

Le piège royal. $\forall x\, \exists y\, P(x,y)$ et $\exists y\, \forall x\, P(x,y)$ n'ont pas la même valeur : dans le premier, $y$ peut dépendre de $x$ ; dans le second, un seul $y$ doit servir pour tous les $x$. Exemple avec $P(x,y) : y \geq x$ sur $\mathbb{R}$ : $\forall x\, \exists y,\, y \geq x$ est vraie (prendre $y = x + 1$), mais $\exists y\, \forall x,\, y \geq x$ est fausse (pas de plus grand réel).

3. Les méthodes de démonstration

Démonstration directe. On part de l'hypothèse et on enchaîne des implications jusqu'à la conclusion, en citant les définitions et théorèmes utilisés.

Par contraposée. Pour montrer $P \Rightarrow Q$, on montre $\neg Q \Rightarrow \neg P$, ce qui est équivalent. Utile quand la conclusion est une négation.

Par l'absurde. On suppose $P$ et $\neg Q$, et on aboutit à une contradiction (une propriété fausse connue, par exemple $0 = 1$). C'est la méthode classique pour prouver l'irrationnalité : supposons $\sqrt{2} = p/q$ irréductible avec $p, q \in \mathbb{Z}$ ; on obtient $p$ et $q$ pairs, contradictoire avec l'irréductibilité.

Par disjonction de cas. On décompose en cas exhaustifs (par exemple $x \geq 0$ ou $x < 0$) et on traite chaque cas séparément. Chaque cas doit être traité complètement : un cas laissé en suspens invalide la démonstration.

Par analyse-synthèse. « Analyse » : on cherche les conditions nécessaires en partant de la conclusion ; « synthèse » : on vérifie que ces conditions sont suffisantes en partant de l'hypothèse. C'est la méthode de référence pour les équations et les systèmes.

Par récurrence. Voir la section dédiée ci-dessous.

4. La récurrence, en détail

On veut prouver une propriété $\mathscr{P}_n$ pour tout entier $n \geq n_0$.

1. Initialisation. On vérifie que $\mathscr{P}_{n_0}$ est vraie.
2. Hérédité. On montre $\mathscr{P}_n \Rightarrow \mathscr{P}_{n+1}$ : on suppose $\mathscr{P}_n$ vraie (hypothèse de récurrence) et on déduit $\mathscr{P}_{n+1}$.
3. Conclusion. Comme $\mathscr{P}_{n_0}$ est vraie et que $\mathscr{P}_n$ est héréditaire, $\mathscr{P}_n$ est vraie pour tout entier $n \geq n_0$.

Exemple type. Montrer que $\sum_{k=1}^{n} k = \dfrac{n(n+1)}{2}$ pour tout $n \geq 1$.

• Initialisation. Pour $n = 1$ : $1 = \dfrac{1 \cdot 2}{2}$. Vrai.
• Hérédité. Soit un entier $n \geq 1$ tel que $\sum_{k=1}^{n} k = \dfrac{n(n+1)}{2}$. Alors

$$\sum_{k=1}^{n+1} k = \sum_{k=1}^{n} k + (n+1) = \frac{n(n+1)}{2} + (n+1) = \frac{(n+1)(n+2)}{2},$$

c'est-à-dire $\mathscr{P}_{n+1}$.

• Conclusion. Par récurrence, la formule est vraie pour tout $n \geq 1$.

Variantes. La récurrence forte (ou complète) suppose $\mathscr{P}_0, \dots, \mathscr{P}_n$ pour prouver $\mathscr{P}_{n+1}$ ; la récurrence double suppose $\mathscr{P}_n$ et $\mathscr{P}_{n-1}$ (nécessaire pour les suites définies par $u_{n+1} = f(u_n, u_{n-1})$, par exemple Fibonacci).

5. Vocabulaire ensembliste

Soient $A$ et $B$ deux ensembles.

• Inclusion : $A \subset B \iff \forall x \in A,\, x \in B$.
• Réunion / intersection / complémentaire : $A \cup B$, $A \cap B$, $\overline{A}$ (par rapport à un univers fixé).
• Produit cartésien : $A \times B = \{(a, b) \mid a \in A,\, b \in B\}$.
• Parties : $\mathcal{P}(A)$ est l'ensemble des parties de $A$ ; si $A$ est fini de cardinal $n$, alors $\mathcal{P}(A)$ est de cardinal $2^n$.

Les lois utiles : distributivité, compléments de De Morgan : $\overline{A \cup B} = \overline{A} \cap \overline{B}$ et $\overline{A \cap B} = \overline{A} \cup \overline{B}$.

6. Applications

Soient $A, B$ deux ensembles et $f : A \to B$.

• Image directe : $f(A') = \{f(x) \mid x \in A'\}$ pour $A' \subset A$.
• Image réciproque : $f^{-1}(B') = \{x \in A \mid f(x) \in B'\}$ pour $B' \subset B$ (définie même si $f$ n'est pas bijective).
• Injection : $f$ est injective $\iff \forall x, y \in A,\, f(x) = f(y) \Rightarrow x = y$.
• Surjection : $f$ est surjective $\iff \forall y \in B,\, \exists x \in A,\, f(x) = y$.
• Bijection : $f$ est bijective $\iff$ injective et surjective. Une bijection admet une réciproque $f^{-1} : B \to A$.
• Composition : si $g : B \to C$, alors $g \circ f : A \to C$ est définie par $(g \circ f)(x) = g(f(x))$.

Stratégies de preuve.

• Pour prouver l'injectivité, on raisonne directement ($f(x) = f(y) \Rightarrow x = y$) ou par contraposée.
• Pour prouver la surjectivité, on « fixe » $y \in B$ et on construit un $x$ tel que $f(x) = y$ (c'est la lecture constructive de $\exists$).
• Pour prouver la bijectivité, soit on prouve les deux propriétés, soit on exhibe explicitement $f^{-1}$ et on vérifie $f^{-1} \circ f = \mathrm{id}_A$ et $f \circ f^{-1} = \mathrm{id}_B$.

7. Relations d'équivalence et d'ordre

Une relation $\sim$ sur $E$ est une relation d'équivalence si elle est réflexive, symétrique et transitive. Les classes d'équivalence $[x] = \{y \in E \mid y \sim x\}$ partagent $E$ en classes disjointes. Exemple canonique : la congruence $a \equiv b \pmod{m}$ sur $\mathbb{Z}$, dont les classes sont $\{0, \dots, m-1\}$.

Une relation $\leq$ est une relation d'ordre si elle est réflexive, antisymétrique et transitive. On parle d'ordre total si, en plus, $\forall x, y$, $x \leq y$ ou $y \leq x$ (c'est le cas de $\mathbb{R}$).

Démonstrations exigibles

Démonstration exigible — à savoir refaire : unicité de la limite. Soit $(u_n)$ convergente. Supposons qu'elle converge vers $\ell$ et vers $\ell' \neq \ell$. Prenons $\varepsilon = \frac{|\ell - \ell'|}{2} > 0$. Il existe $N_1$ tel que $n \geq N_1 \Rightarrow |u_n - \ell| \leq \varepsilon$ et $N_2$ tel que $n \geq N_2 \Rightarrow |u_n - \ell'| \leq \varepsilon$. Pour $n \geq \max(N_1, N_2)$, l'inégalité triangulaire donne $|\ell - \ell'| \leq |u_n - \ell| + |u_n - \ell'| \leq 2\varepsilon = |\ell - \ell'|$, donc $|\ell - \ell'| = 0$, contradiction. La limite est donc unique.

Capacités exigibles

• M1.bijection — Montrer qu'une application est bijective : savoir choisir la bonne stratégie (directe, par réciproque explicite, par composition de bijections) et rédiger la preuve complète.
• M1.negation-quantifiee — Écrire la négation d'un énoncé quantifié : inverser $\forall \leftrightarrow \exists$ et négater la propriété, sans confondre l'ordre des quantificateurs.
• M1.recurrence-complete — Rédiger une récurrence complète : initialisation au bon rang, hérédité avec l'hypothèse de récurrence explicitement nommée, conclusion citant le principe.

Pièges classiques

• Confondre $\forall x\, \exists y$ et $\exists y\, \forall x$ : l'ordre des quantificateurs change la valeur de l'énoncé.
• Oublier l'initialisation : une hérédité seule ne prouve rien (la propriété peut être héréditaire et fausse).
• Écrire « supposons que $\mathscr{P}_n$ est vraie pour tout $n$ » dans l'hérédité : on suppose $\mathscr{P}_n$ vraie pour un $n$ fixé, pas pour tous les $n$.
• Confondre réciproque et contraposée : seule la contraposée est équivalente à l'implication.
• Rédaction : chaque affirmation doit être justifiée par une définition ou un théorème nommé ; « c'est évident » n'est pas une justification.
• Image directe vs image réciproque : $f^{-1}$ n'existe que si $f$ est bijective ; l'image réciproque $f^{-1}(B')$ comme préimage existe toujours.

Graphe de référence

La suite $u_n = \dfrac{n}{2^n}$ (qui apparaît dans les récurrences du type $u_{n+1} = \dfrac{u_n}{2} + \dfrac{1}{2^{n+1}}$) est positive, croissante puis décroissante, et tend vers $0$ : un exemple concret de ce que la récurrence permet d'établir.

Pour aller plus loin

Ce chapitre n'a pas de renvoi spécifique dans la table du §4 de l'annexe Ressources, exercices et annales (programme non explicitement couvert par les thèmes recensés) — voir la page générale pour les manuels recommandés, les banques d'exercices gratuites et les annales par matière.