Quantificateurs et raisonnements en maths sup (MPSI) : cours et méthodes

La négation \(\neg P\) est vraie exactement quand \(P\) est fausse. La conjonction « \(P\) et \(Q\) » est vraie quand les deux sont vraies. La disjonction « \(P\) ou \(Q\) » est vraie quand au moins l’une des deux l’est. Enfin, l’implication \(P \Rightarrow Q\) est fausse dans un seul cas : \(P\) vraie et \(Q\) fausse.

« \(\forall x \in E,\ P(x)\) » se lit « pour tout \(x\) de \(E\), \(P(x)\) ». Cette assertion est vraie si \(P(x)\) est vraie pour chaque élément de \(E\).

« \(\exists x \in E,\ P(x)\) » se lit « il existe \(x\) dans \(E\) tel que \(P(x)\) ». Elle est vraie si au moins un élément de \(E\) convient. Enfin, « \(\exists !\, x \in E,\ P(x)\) » affirme l’existence d’un tel \(x\) et son unicité.

Comparons \(A\) : « \(\forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ y > x\) » et \(B\) : « \(\exists y \in \mathbb{R},\ \forall x \in \mathbb{R},\ y > x\) ».

D’abord, \(A\) est vraie : pour un réel \(x\) donné, le réel \(y = x + 1\) convient. Ici, \(y\) est choisi après \(x\) et dépend de lui. Ensuite, \(B\) est fausse : un tel \(y\) serait strictement plus grand que tous les réels, donc que lui-même. Autrement dit, \(B\) affirme que \(\mathbb{R}\) possède un plus grand élément strict, ce qui est absurde.

Deux quantificateurs de même nature commutent : \(\forall x\, \forall y\) équivaut à \(\forall y\, \forall x\), et de même pour \(\exists\). De plus, « \(\exists y\, \forall x,\ P(x, y)\) » implique toujours « \(\forall x\, \exists y,\ P(x, y)\) ». Cependant, la réciproque est fausse en général, comme le montre l’exemple précédent.

Pour toutes assertions \(P\) et \(Q\) et tout prédicat \(R\) :

• \(\neg(P \text{ et } Q)\) équivaut à \((\neg P) \text{ ou } (\neg Q)\), et \(\neg(P \text{ ou } Q)\) équivaut à \((\neg P) \text{ et } (\neg Q)\) ;
• \(\neg(P \Rightarrow Q)\) équivaut à « \(P\) et \(\neg Q\) » ;
• \(\neg(\forall x \in E,\ R(x))\) équivaut à \(\exists x \in E,\ \neg R(x)\) ;
• \(\neg(\exists x \in E,\ R(x))\) équivaut à \(\forall x \in E,\ \neg R(x)\).

Pour nier une assertion écrite en symboles :

1. on garde l’ordre des quantificateurs et on échange chaque \(\forall\) avec \(\exists\) ;
2. on ne touche pas aux ensembles qui suivent les quantificateurs ;
3. on nie la partie finale, sans quantificateur, avec les règles précédentes ;
4. on relit enfin en français pour vérifier que le sens est bien contraire.

Soit \(g : [0, 4] \to \mathbb{R}\). L’assertion « \(g\) est bornée » s’écrit :

\[\exists M \in \mathbb{R},\ \forall t \in [0, 4],\ |g(t)| \leq M.\]

Nous appliquons la méthode. Le \(\exists M\) devient \(\forall M\), puis le \(\forall t\) devient \(\exists t\). Enfin, l’inégalité large se nie en inégalité stricte. On obtient :

\[\forall M \in \mathbb{R},\ \exists t \in [0, 4],\ |g(t)| > M.\]

En français : quel que soit le seuil choisi, la fonction le dépasse en valeur absolue quelque part.

À l’implication \(P \Rightarrow Q\), on associe sa réciproque \(Q \Rightarrow P\) et sa contraposée \(\neg Q \Rightarrow \neg P\). L’équivalence \(P \Leftrightarrow Q\) signifie que l’implication et sa réciproque sont vraies toutes les deux.

Une implication et sa contraposée ont toujours la même valeur de vérité.

L’implication \(P \Rightarrow Q\) est fausse seulement quand \(P\) est vraie et \(Q\) fausse. De même, \(\neg Q \Rightarrow \neg P\) est fausse seulement quand \(\neg Q\) est vraie et \(\neg P\) fausse. Autrement dit, c’est encore le cas où \(Q\) est fausse et \(P\) vraie. Les deux assertions sont donc fausses dans le même unique cas, d’où le résultat.

Lorsque \(P \Rightarrow Q\) est vraie, \(P\) suffit à garantir \(Q\) : c’est une condition suffisante. Dans l’autre sens, \(Q\) est indispensable à \(P\) : c’est une condition nécessaire. Quand \(P \Leftrightarrow Q\), on dit que \(P\) est une condition nécessaire et suffisante pour \(Q\).

Pour un réel \(x\), posons \(P\) : « \(x > 3\) » et \(Q\) : « \(x^2 > 4\) ». Si \(x > 3\), alors \(x^2 > 9 > 4\). Donc \(P\) est une condition suffisante pour \(Q\).

Cependant, \(P\) n’est pas nécessaire pour \(Q\) : le réel \(x = -3\) vérifie \(x^2 = 9 > 4\), mais pas \(x > 3\). Enfin, une condition nécessaire et suffisante pour \(Q\) est « \(x < -2\) ou \(x > 2\) ».

En colle, reformulez toujours « il faut que » par « nécessaire » et « il suffit que » par « suffisant ». Ensuite, écrivez l’implication correspondante avant de répondre. Cette traduction évite les confusions de sens.

Montrons que, pour tout entier \(n\), l’entier \(n^2 + n + 11\) est impair. Deux cas recouvrent tous les entiers.

• Si \(n = 2k\), alors \(n^2 + n + 11 = 4k^2 + 2k + 10 + 1 = 2(2k^2 + k + 5) + 1\), qui est impair.
• Si \(n = 2k + 1\), alors \(n^2 + n = (2k + 1)(2k + 2) = 2(2k + 1)(k + 1)\) est pair. Donc \(n^2 + n + 11\) est impair.

Dans les deux cas, la conclusion est la même. Par conséquent, le résultat vaut pour tout entier \(n\).

1. On écrit clairement la contraposée : « Nous montrons que si \(\neg Q\), alors \(\neg P\). »
2. On suppose \(\neg Q\), en la traduisant de façon utilisable.
3. On en déduit \(\neg P\) par un calcul direct.
4. On conclut : « Par contraposition, \(P \Rightarrow Q\). »

Le réel \(\log_{10}(2)\) est irrationnel.

Supposons par l’absurde que \(\log_{10}(2) = p/q\) avec \(p, q\) entiers et \(q \geq 1\). Comme \(1 < 2 < 10\), on a \(0 < \log_{10}(2) < 1\), donc \(p \geq 1\). Ensuite, \(10^{p/q} = 2\), puis \(10^p = 2^q\). Or \(10^p\) est divisible par \(5\), alors que \(2^q\) ne l’est pas. C’est une contradiction, donc \(\log_{10}(2)\) est irrationnel.

1. Analyse. On suppose qu’un objet convient et l’on en tire des conditions nécessaires. Le but est d’aboutir à une liste restreinte de candidats, parfois un seul.
2. Synthèse. On vérifie, parmi ces candidats, lesquels conviennent vraiment. C’est l’étape de la condition suffisante.
3. Conclusion. On énonce l’ensemble exact des solutions.

Cherchons les fonctions \(f : \mathbb{R} \to \mathbb{R}\) telles que, pour tous réels \(x\) et \(y\), \(f(x) – f(y) = 3(x – y)\).

Analyse. Soit \(f\) une solution. En prenant \(y = 0\), on obtient \(f(x) = 3x + f(0)\) pour tout \(x\). Donc \(f\) est de la forme \(x \mapsto 3x + c\), avec \(c\) réel.

Synthèse. Réciproquement, soit \(c\) réel et \(f(x) = 3x + c\). Alors \(f(x) – f(y) = 3x – 3y = 3(x – y)\) pour tous \(x, y\). Toutes ces fonctions conviennent.

Conclusion. Les solutions sont exactement les fonctions \(x \mapsto 3x + c\), où \(c\) décrit \(\mathbb{R}\).

Soit \(n_0 \in \mathbb{N}\) et \(\mathcal{P}(n)\) un prédicat défini pour \(n \geq n_0\). On suppose que \(\mathcal{P}(n_0)\) est vraie et que, pour tout \(n \geq n_0\), \(\mathcal{P}(n) \Rightarrow \mathcal{P}(n + 1)\). Alors \(\mathcal{P}(n)\) est vraie pour tout entier \(n \geq n_0\).

Supposons par l’absurde que l’ensemble \(F\) des entiers \(n \geq n_0\) pour lesquels \(\mathcal{P}(n)\) est fausse soit non vide. Il admet alors un plus petit élément \(m\). D’abord, \(m \neq n_0\), puisque \(\mathcal{P}(n_0)\) est vraie. Ainsi, \(m – 1 \geq n_0\) et \(m – 1 \notin F\), donc \(\mathcal{P}(m – 1)\) est vraie. L’hérédité donne alors \(\mathcal{P}(m)\) vraie, ce qui contredit \(m \in F\).

Montrons que, pour tout \(n \geq 1\), \(\displaystyle\sum_{k=1}^{n} k(k+2) = \frac{n(n+1)(2n+7)}{6}\).

Pour \(n \geq 1\), notons \(\mathcal{P}(n)\) cette égalité. Initialisation : pour \(n = 1\), le membre de gauche vaut \(3\) et celui de droite \(\frac{1 \times 2 \times 9}{6} = 3\).

Hérédité : soit \(n \geq 1\) tel que \(\mathcal{P}(n)\) soit vraie. Alors la somme jusqu’à \(n + 1\) vaut \(\frac{n(n+1)(2n+7)}{6} + (n+1)(n+3)\). On factorise par \(\frac{n+1}{6}\) :

\[\frac{n+1}{6}\bigl(2n^2 + 7n + 6n + 18\bigr) = \frac{(n+1)(n+2)(2n+9)}{6}.\]

C’est exactement \(\mathcal{P}(n + 1)\), car \(2(n+1) + 7 = 2n + 9\). Par récurrence, l’égalité vaut pour tout \(n \geq 1\).

Récurrence double. On suppose \(\mathcal{P}(n_0)\) et \(\mathcal{P}(n_0 + 1)\) vraies. On suppose aussi que deux rangs consécutifs vrais \(n\) et \(n + 1\) entraînent toujours le rang \(n + 2\). Alors la propriété tient à chaque rang \(n \geq n_0\).

Récurrence forte. On suppose \(\mathcal{P}(n_0)\) vraie. On suppose aussi que, dès que tous les rangs de \(n_0\) jusqu’à \(n\) sont acquis, le rang \(n + 1\) l’est à son tour. Alors, là encore, la propriété tient à chaque rang \(n \geq n_0\).

Montrons que tout entier \(n \geq 2\) est un produit de nombres premiers. Pour \(n \geq 2\), notons \(\mathcal{P}(n)\) cette propriété. D’abord, \(\mathcal{P}(2)\) est vraie, car \(2\) est premier.

Ensuite, soit \(n \geq 2\) tel que \(\mathcal{P}(2), \ldots, \mathcal{P}(n)\) soient vraies. Si \(n + 1\) est premier, c’est terminé. Sinon, \(n + 1 = ab\) avec \(2 \leq a, b \leq n\). Les deux facteurs sont des produits de nombres premiers, donc \(n + 1\) aussi. Ici, une récurrence simple échouerait, car \(a\) et \(b\) ne valent pas \(n\) en général.

• S’exercer : exercices corrigés de maths sup (MPSI) sur quantificateurs et raisonnements
• Chapitre d’après : Ensembles, injections, surjections et relations
• Vérifier ses acquis : QCM de maths sup (MPSI) sur quantificateurs et raisonnements
• Contrôle corrigé en temps limité : Quantificateurs, injections et surjections : contrôle de maths en MPSI
• Tous les chapitres : le sommaire de maths sup (MPSI)
• Après le bac : les maths post-bac, de la MPSI à la L3