Mathventure
Propositions, implications et quantificateurs
Un raisonnement commence par un énoncé précis : quels sont les objets étudiés, dans quel ensemble vivent-ils et que faut-il démontrer ? On distingue une proposition, qui est vraie ou fausse, d'une expression contenant une variable libre, dont la valeur de vérité dépend de cette variable.
Définition 1 (Connecteurs et quantificateurs). Pour des propositions $P$ et $Q$, $P\land Q$ signifie « $P$ et $Q$ », $P\lor Q$ signifie « $P$ ou $Q$ », et $\neg P$ est la négation de $P$. L'implication $P\Rightarrow Q$ est fausse seulement quand $P$ est vraie et $Q$ fausse. L'équivalence $P\Leftrightarrow Q$ réunit les deux implications.
$\forall x\in E,\ P(x)$ signifie que chaque élément de $E$ vérifie $P$. $\exists x\in E,\ P(x)$ signifie qu'au moins un élément de $E$ la vérifie. L'ordre des quantificateurs compte : le témoin de $\forall x\,\exists y$ peut dépendre de $x$.
Proposition 2 (Nier sans changer le domaine). Les lois de De Morgan donnent $\neg(P\land Q)\Leftrightarrow(\neg P\lor\neg Q)$ et $\neg(P\lor Q)\Leftrightarrow(\neg P\land\neg Q)$.
Pour les quantificateurs : $$\neg(\forall x\in E,\ P(x))\Leftrightarrow\exists x\in E,\ \neg P(x),$$ $$\neg(\exists x\in E,\ P(x))\Leftrightarrow\forall x\in E,\ \neg P(x).$$ Enfin, $\neg(P\Rightarrow Q)\Leftrightarrow P\land\neg Q$.
Exemple 3 (Un témoin qui dépend de la variable). L'énoncé $\forall x\in\R,\ \exists y\in\R,\ y>x$ est vrai : pour un $x$ donné, on choisit $y=x+1$. En revanche, $\exists y\in\R,\ \forall x\in\R,\ y>x$ est faux : quel que soit $y$, le choix $x=y+1$ le contredit.
Exercice 4 (Négations et valeur de vérité). Écrire la négation de chacun des énoncés suivants, puis déterminer si l'énoncé initial est vrai :
- $A$ : $\forall x\in\R,\ \exists n\in\N,\ n>x^2$.
- $B$ : $\exists x\in\R,\ \forall y\in\R,\ x+y\ge0$.
Indice
Inverse chaque quantificateur, puis nie uniquement l'inégalité finale. Pour $A$, utilise la propriété d'Archimède : tout réel est dépassé par un entier naturel. Pour $B$, choisis $y$ en fonction de $x$.
Solution
La négation de $A$ est $\exists x\in\R,\ \forall n\in\N,\ n\le x^2$. L'énoncé $A$ est vrai : pour chaque $x$, la propriété d'Archimède fournit un entier $n>x^2$. Sa négation est donc fausse.
La négation de $B$ est $\forall x\in\R,\ \exists y\in\R,\ x+y<0$. Elle est vraie : pour n'importe quel $x$, on peut prendre $y=-x-1$, ce qui donne $x+y=-1<0$. Aucun $x$ ne convient dans $B$ : $B$ est faux.
Ensembles et applications
Définition 5 (Inclusion, image et antécédent). L'inclusion $A\subseteq B$ signifie $\forall x,\ x\in A\Rightarrow x\in B$. Pour prouver $A=B$, on peut montrer les deux inclusions.
Une application $f:E\to F$ associe à chaque $x\in E$ une unique image $f(x)\in F$. L'image d'une partie $A\subseteq E$ est $f(A)=\{f(x):x\in A\}$. L'image réciproque d'une partie $B\subseteq F$ est $f^{-1}(B)=\{x\in E:f(x)\in B\}$ ; cette notation est définie même si $f$ n'est pas bijective.
Définition 6 (Injection, surjection et bijection). Une application $f:E\to F$ est :
- injective si $f(x)=f(x')$ implique $x=x'$ pour tous $x,x'\in E$ ;
- surjective si $\forall y\in F,\ \exists x\in E,\ f(x)=y$ ;
- bijective si elle est à la fois injective et surjective.
Une bijection possède une application réciproque $f^{-1}:F\to E$. Les ensembles de départ et d'arrivée font partie de la définition de $f$.
Exemple 7 (Prouver une égalité par double inclusion). Pour toutes parties $A,B,C$ d'un ensemble, $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$.
Si $x\in A\cap(B\cup C)$, alors $x\in A$ et $x$ appartient à $B$ ou à $C$, donc il appartient au membre de droite. Réciproquement, si $x$ appartient à $A\cap B$ ou à $A\cap C$, alors $x\in A$ et $x\in B\cup C$, donc il appartient au membre de gauche.
Exercice 8 (Le carré selon son domaine). Soit $f:\R\to[0,+\infty[$ définie par $f(x)=x^2$. Est-elle injective ? Surjective ? Montrer que sa restriction $g:[0,+\infty[\to[0,+\infty[$ est bijective et donner $g^{-1}$.
Indice
Compare les images de $1$ et $-1$. Pour la surjectivité, résous $x^2=y$ avec $y\ge0$. La restriction impose $x\ge0$.
Solution
L'application $f$ n'est pas injective car $f(1)=f(-1)=1$ alors que $1\ne-1$. Elle est surjective : tout $y\ge0$ possède l'antécédent $x=\sqrt y\in\R$.
Si $x,x'\ge0$ et $g(x)=g(x')$, alors $x^2=x'^2$. Ainsi $(x-x')(x+x')=0$. Si $x+x'=0$, les deux nombres sont nuls ; sinon $x-x'=0$. Dans tous les cas $x=x'$ : $g$ est injective. Chaque $y\ge0$ a toujours pour antécédent $\sqrt y\ge0$ : $g$ est aussi surjective. Elle est donc bijective, et $g^{-1}(y)=\sqrt y$.
Démonstration directe, contraposée et récurrence
Proposition 9 (Choisir une méthode de preuve). Pour une implication $P\Rightarrow Q$, une preuve directe part de $P$ pour établir $Q$. La contraposée prouve l'implication équivalente $\neg Q\Rightarrow\neg P$. Une preuve par l'absurde suppose $P$ et $\neg Q$, puis obtient une contradiction. Un contre-exemple suffit à réfuter un énoncé universel.
Exemple 10 (La contraposée en arithmétique). Montrons que, pour $n\in\Z$, si $n^2$ est pair alors $n$ est pair. Par contraposée, supposons $n$ impair : $n=2k+1$ avec $k\in\Z$. Alors $n^2=4k^2+4k+1=2(2k^2+2k)+1$ est impair. La contraposée est démontrée, donc l'implication initiale aussi.
Théorème 11 (Principe de récurrence). Soit $P(n)$ une propriété définie pour tous les entiers $n\ge n_0$. Si $P(n_0)$ est vraie (initialisation) et si, pour chaque $n\ge n_0$, $P(n)\Rightarrow P(n+1)$ (hérédité), alors $P(n)$ est vraie pour tout $n\ge n_0$. Dans l'hérédité, on suppose un rang $n$ fixé mais arbitraire ; on ne suppose pas déjà la conclusion pour tous les rangs.
Exercice 12 (Somme des carrés). Démontrer par récurrence que, pour tout entier $n\ge1$, $$1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}6.$$
Indice
Vérifie le cas $n=1$. Au rang suivant, ajoute $(n+1)^2$ à la formule supposée vraie, puis factorise par $n+1$.
Solution
Pour $n=1$, le membre de droite vaut $1\times2\times3/6=1$ : l'initialisation est vérifiée.
Supposons la formule vraie à un rang $n\ge1$. Alors $$\sum_{k=1}^{n+1}k^2=\frac{n(n+1)(2n+1)}6+(n+1)^2$$ $$=\frac{(n+1)\big(n(2n+1)+6(n+1)\big)}6$$ $$=\frac{(n+1)(2n^2+7n+6)}6=\frac{(n+1)(n+2)(2n+3)}6.$$ C'est exactement la formule au rang $n+1$, puisque $2(n+1)+1=2n+3$. L'hérédité est établie ; le principe de récurrence conclut pour tout $n\ge1$.
Vérifie ta compréhension. Quelle proposition est équivalente à $P\Rightarrow Q$ ?
- $Q\Rightarrow P$
- $\neg Q\Rightarrow\neg P$
- $\neg P\Rightarrow\neg Q$
Réponse
Bonne réponse : B.
La contraposée $\neg Q\Rightarrow\neg P$ est équivalente à l'implication initiale. La réciproque $Q\Rightarrow P$ peut être fausse même quand $P\Rightarrow Q$ est vraie.