Logique, ensembles et méthodes de démonstration

L'analyse est la première branche des mathématiques où l'intuition ne suffit plus. Une suite «qui s'approche de plus en plus» d'une valeur, une fonction «sans saut», une aire «limite» de rectangles de plus en plus fins: ces images sont utiles, mais elles ne permettent ni de trancher les cas litigieux (la suite $(-1{)}^n/n$ converge-t-elle? la fonction $x\mapsto \sin (1/x)$ a-t-elle une limite en $0$?) ni de démontrer quoi que ce soit. Depuis Cauchy et Weierstrass, l'analyse s'est dotée d'un langage précis, fait de quantificateurs et d'implications, dans lequel chaque énoncé a un sens unique et chaque démonstration peut être vérifiée pas à pas. Cette annexe rassemble ce langage: la logique élémentaire, le vocabulaire des ensembles et des fonctions, les méthodes de démonstration utilisées dans tout le cours, et enfin les notations et l'alphabet grec.

Pour lire un énoncé mathématique, prenez l'habitude de vous poser trois questions: quels sont les objets (un réel, une suite, une fonction, un intervalle)? quelles hypothèses portent sur eux? et quelle est la conclusion, avec quels quantificateurs? Un théorème mal lu est un théorème mal appliqué: le théorème de Weierstrass, par exemple, affirme qu'une fonction continue sur un intervalle fermé et borné atteint son maximum, et chacun de ces mots est indispensable: $x\mapsto 1/x$ sur $]0,1]$ (intervalle non fermé), $x\mapsto x$ sur $[0,+\infty [$ (intervalle non borné) et la fonction qui vaut $x$ sur $[0,1[$ et en (fonction non continue) n'atteignent aucun maximum.

Logique élémentaire

Propositions et connecteurs

À partir de deux propositions $P$ et $Q$, on en fabrique de nouvelles avec les connecteurs logiques: la négation $\neg P$ («non $P$»), la conjonction $P\wedge Q$ («$P$ et $Q$»), la disjonction $P\vee Q$ («$P$ ou », au sens inclusif: l'un, l'autre ou les deux), l'implication («si alors ») et l'équivalence (« si et seulement si »). Leur sens est entièrement fixé par la table de vérité suivante.

Deux lignes méritent un commentaire. D'abord, l'implication $P⟹Q$ n'est fausse que dans un seul cas: $P$ vraie et $Q$ fausse. En particulier, une implication dont l'hypothèse est fausse est toujours vraie: «si $1=2$ alors $\pi$ est rationnel» est une implication vraie. Cette convention n'est pas un caprice: elle garantit que «pour tout $x\in \mathbb{R}$, $x>2⟹x^2>4$» reste vrai même pour , où l'hypothèse n'est pas satisfaite. Ensuite, est vraie exactement lorsque et ont la même valeur de vérité; elle équivaut à , ce qui explique la méthode de démonstration par double implication vue plus loin.

Deux propositions composées sont dites logiquement équivalentes lorsqu'elles ont la même table de vérité. Les équivalences suivantes servent constamment:

Les deux premières négations sont les lois de De Morgan: la négation transforme «et» en «ou» et réciproquement. La dernière ligne dit comment réfuter une implication: il faut exhiber une situation où $P$ est vraie et $Q$ fausse.

Implication, réciproque, contraposée

Étant donné une implication $P⟹Q$, on appelle:

• réciproque l'implication $Q⟹P$;
• contraposée l'implication $\neg Q⟹\neg P$;
• négation la proposition $P\wedge \neg Q$.

Démonstration. On compare les tables de vérité: $P⟹Q$ est fausse uniquement si $P$ est vraie et $Q$ fausse; $\neg Q⟹\neg P$ est fausse uniquement si $\neg Q$ est vraie et $\neg P$ fausse, c'est-à-dire si $Q$ est fausse et $P$ vraie. Les deux propositions sont fausses dans le même cas et vraies dans tous les autres.

Condition nécessaire, condition suffisante

Lorsque $P⟹Q$ est vraie, on dit que $P$ est une condition suffisante pour $Q$ (il suffit que $P$ soit vraie pour que $Q$ le soit) et que $Q$ est une condition nécessaire pour $P$ (si $P$ est vraie, alors nécessairement $Q$ l'est). Ainsi, «» est une condition nécessaire à la convergence de la série , mais pas suffisante (série harmonique, chapitre 4); « converge» est une condition suffisante, mais pas nécessaire (série harmonique alternée). Une condition est exactement lorsque l'on a l'équivalence .

Quantificateurs

Pour transformer un prédicat en proposition, on peut fixer la variable, ou bien la quantifier. Le quantificateur universel $\forall$ se lit «pour tout» (ou «quel que soit»), le quantificateur existentiel $\exists$ se lit «il existe (au moins un)», et $\exists !$ se lit «il existe un unique». Par exemple:

Un énoncé du type $\forall x\in E,P(x)$ est vrai si $P(x)$ est vraie pour chaque élément de $E$; il est vrai «par défaut» si $E$ est vide. Un énoncé $\exists x\in E,P(x)$ est vrai dès qu'un seul élément convient. La variable quantifiée est muette: $\forall x\in \mathbb{R},x^2\ge 0$ et sont le même énoncé.

L'ordre des quantificateurs

Lorsqu'un énoncé contient plusieurs quantificateurs, deux quantificateurs de même nature peuvent être échangés ($\forall x\forall y$ est la même chose que $\forall y\forall x$), mais l'ordre entre $\forall$ et $\exists$ est essentiel. Comparez:

Le premier énoncé est vrai (prendre $y=x+1$: le $y$ dépend de $x$); le second est faux (il affirme l'existence d'un réel plus grand que tous les réels, lui-même compris). Dans $\forall x\exists y$, l'objet $y$ peut dépendre de $x$; dans $\exists y\forall x$, le même $y$ doit convenir pour tous les : c'est un énoncé bien plus fort.

Négation d'un énoncé quantifié

Pour nier un énoncé quantifié, on applique mécaniquement les règles suivantes:

Autrement dit, la négation échange $\forall$ et $\exists$ en conservant leur ordre, puis nie la propriété finale. Combinée avec $\neg (P⟹Q)⟺(P\wedge \neg Q)$ et avec la négation des inégalités ($\neg (a<b)⟺a\ge b$), cette règle permet de nier n'importe quelle définition de l'analyse.

Ensembles

Appartenance, inclusion, égalité

Un ensemble est une collection d'objets, ses éléments; on écrit $x\in E$ («$x$ appartient à $E$») et $x\notin E$ sinon. Un ensemble est déterminé par ses éléments, sans ordre ni répétition: $\{1,2,3\}=\{3,1,2\}=\{1,1,2,3\}$. L' n'a aucun élément.

Ne confondez pas $\in$ et $\subset$: $1\in \{1,2\}$, $\{1\}\subset \{1,2\}$, mais $1\not\subset \{1,2\}$ et $\{1\}\notin \{1,2\}$. L'ensemble vide est inclus dans tout ensemble (l'implication est vraie par défaut, car son hypothèse est toujours fausse).

Opérations sur les ensembles

Soient $A$ et $B$ deux parties d'un ensemble $E$. On définit la réunion $A\cup B=\{x\in E:x\in A\vee x\in B\}$, l' , la et le (noté aussi ou ). Deux ensembles d'intersection vide sont dits . Les connecteurs logiques et les opérations ensemblistes se correspondent terme à terme ( et , et , et complémentaire), si bien que les lois de De Morgan se transposent:

On a de plus la distributivité $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$ et $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$.

Produit cartésien, intervalles, ensembles de nombres

Le produit cartésien $A\times B$ est l'ensemble des couples $(a,b)$ avec $a\in A$ et $b\in B$; ici l'ordre compte: $(1,2)\ne (2,1)$. Le plan est , et le graphe d'une fonction est la partie de .

Les ensembles de nombres du cours sont emboîtés:

avec ${\mathbb{N}}^{\ast }=\mathbb{N}\setminus \{0\}$, ${\mathbb{R}}^{\ast }=\mathbb{R}\setminus \{0\}$, ${\mathbb{R}}_{+}=[0,+\infty [$ et . Les de sont notés à la française, le crochet tourné vers l'extérieur indiquant une borne exclue: , , , , , , et . Un intervalle est caractérisé par sa : si et , alors ; c'est cette propriété qu'utilise le théorème des valeurs intermédiaires.

La notation en compréhension $\{x\in E:P(x)\}$ (on rencontre aussi une barre verticale à la place des deux-points) désigne l'ensemble des éléments de $E$ vérifiant $P$: par exemple $\{n\in \mathbb{N}:n\text{ pair}\}$, ou $\{x\in \mathbb{R}:x^2<2\}=]-\sqrt{2},\sqrt{2}[$. Cette notation est la traduction ensembliste d'un prédicat.

Image et image réciproque

Attention: la notation $f^{-1}(B)$ ne suppose pas que $f$ soit bijective; c'est un ensemble, défini pour toute fonction. Par exemple, pour $f(x)=x^2$ sur $\mathbb{R}$, $f([-1,2])=[0,4]$, et . Les images réciproques se comportent parfaitement vis-à-vis des opérations (, de même pour et le complémentaire); les images directes sont moins dociles: on a seulement , avec inclusion stricte possible (, , ).

Injections, surjections, bijections

Ces propriétés dépendent autant des ensembles de départ et d'arrivée que de la formule:

• $x\mapsto x^2$, de $\mathbb{R}$ dans $\mathbb{R}$, n'est ni injective ($f(-1)=f(1)$) ni surjective ($-1$ n'est pas atteint); de ${\mathbb{R}}_{+}$ dans , elle est bijective, de réciproque ;

Graphiquement, $f$ est injective si toute droite horizontale coupe son graphe au plus une fois, surjective si toute horizontale $y=c$ avec $c\in F$ le coupe au moins une fois. Le chapitre 6 utilise ces notions pour définir $\ln$, $\arcsin$, $\arctan$ et les fonctions hyperboliques réciproques.

Ensembles dénombrables

Les bijections permettent de comparer la «taille» des ensembles infinis.

$\mathbb{Z}$ est dénombrable: la liste $0,1,-1,2,-2,3,-3,\dots$ atteint chaque entier exactement une fois. $\mathbb{Q}$ l'est aussi: on range les fractions irréductibles $p/q$ ($q\ge 1$) par valeurs croissantes de $|p|+q$, ce qui ne laisse qu'un nombre fini de fractions dans chaque paquet. En revanche, (Cantor, 1874). L'argument diagonal (1891) en donne l'idée: si était une liste de tous les réels de écrits en développement décimal, le réel dont la -ième décimale vaut si la -ième décimale de n'est pas , et sinon, diffère de chaque en au moins une décimale et n'est donc pas dans la liste. Ainsi, bien que les rationnels soient dans (chapitre 1), les irrationnels sont incomparablement plus nombreux: c'est une première indication que la densité et la taille sont deux notions différentes.

Méthodes de démonstration

Une démonstration est une suite d'énoncés dont chacun est un axiome, une hypothèse, un résultat déjà établi, ou découle des précédents par une règle de logique. En pratique, on dispose d'un petit nombre de schémas de raisonnement, que nous passons en revue avec, pour chacun, un exemple emprunté à l'analyse.

Démonstration directe

Pour prouver $P⟹Q$, on suppose $P$ et l'on déduit $Q$ par une chaîne d'implications. C'est la méthode par défaut.

Démonstration par contraposée

Pour prouver $P⟹Q$, on prouve $\neg Q⟹\neg P$, ce qui est équivalent d'après le théorème A.1. On y recourt lorsque la négation des énoncés est plus maniable que les énoncés eux-mêmes.

Démonstration par l'absurde

Pour prouver $P$, on suppose $\neg P$ et l'on aboutit à une contradiction (un énoncé de la forme $R\wedge \neg R$); $\neg P$ est donc fausse et $P$ vraie. La démonstration de l'irrationalité de $\sqrt{2}$, au chapitre 1, en est l'exemple canonique: on suppose avec irréductible et l'on montre que et sont tous deux pairs. En voici un autre, plus proche de la topologie de .

Contraposée et absurde sont proches, mais ne se confondent pas: la contraposée prouve une implication en partant de $\neg Q$ pour atteindre précisément $\neg P$; l'absurde prouve un énoncé quelconque en partant de sa négation pour atteindre une contradiction quelconque.

Démonstration par disjonction de cas

Si l'on sait que $P_1\vee P_2\vee \cdots \vee P_k$ est vraie, et que chaque $P_i$ implique , alors est vraie. Il faut que les cas recouvrent toutes les situations possibles.

Démonstration par récurrence

Le raisonnement par récurrence sert à établir qu'une propriété $P(n)$ est vraie pour tout entier $n$ à partir d'un certain rang. Il repose sur le fait que $\mathbb{N}$ est engendré par $0$ et le passage au successeur.

La forme simple est le théorème 1.15 du chapitre 1; nous la rappelons ici pour lui adjoindre sa variante forte. Dans l'étape d'hérédité, on fixe un entier $n\ge n_0$ et l'on suppose $P(n)$ (c'est l'hypothèse de récurrence), puis on démontre $P(n+1)$. On ne suppose pas «$P(n)$ pour tout $n$», ce qui serait supposer le résultat. La récurrence forte autorise à utiliser tous les rangs précédents, ce qui est indispensable lorsque se ramène à un rang plus petit que , et non pas seulement à .

Démonstration d'une équivalence

Pour prouver $P⟺Q$, on prouve séparément $P⟹Q$ et $Q⟹P$ (double implication), en annonçant clairement chaque sens. On peut aussi enchaîner des équivalences, mais chaque étape doit alors être réellement réversible: «$x=2⟹x^2=4$» est vrai, «» ne l'est pas. Pour démontrer que plusieurs propriétés sont équivalentes, il suffit de prouver un cycle d'implications .

Démonstration d'une égalité d'ensembles

Pour prouver $A=B$, on prouve $A\subset B$ puis $B\subset A$ (double inclusion). Chaque inclusion se démontre en prenant un élément quelconque du premier ensemble et en montrant qu'il appartient au second.

Existence et unicité

Prouver un énoncé $\exists x,P(x)$ peut se faire de deux manières. Une démonstration constructive exhibe explicitement un objet: pour montrer qu'il existe un réel $x$ tel que $x^2-3x+2=0$, on présente $x=1$. Une démonstration non constructive prouve l'existence sans fournir l'objet: pour montrer que l'équation $x^5+x-1=0$ a une solution dans , on remarque que est continue, que et , et le théorème des valeurs intermédiaires (chapitre 5) garantit l'existence d'un zéro, sans dire lequel. En analyse, les théorèmes d'existence (TVI, Bolzano–Weierstrass, théorème de Rolle, existence d'un maximum sur un fermé borné) sont presque tous de ce type; c'est ensuite le rôle de l'analyse numérique de construire des approximations.

Prouver l'unicité se fait selon un schéma unique: on suppose que deux objets $x$ et $x^{\prime }$ vérifient la propriété, et l'on montre que $x=x^{\prime }$.

Analyse et synthèse

Lorsqu'on cherche un objet dont on ne connaît pas encore la forme, on raisonne en deux temps. L'analyse suppose que l'objet existe et en déduit des conditions nécessaires, jusqu'à ne laisser qu'un candidat (ce qui prouve l'unicité). La synthèse vérifie que ce candidat convient réellement (ce qui prouve l'existence). Oublier la synthèse est une erreur fréquente: l'analyse ne fournit que des conditions nécessaires.

Contre-exemples

Pour réfuter un énoncé universel $\forall x\in E,P(x)$, il suffit, d'après les règles de négation, d'exhiber un seul $x\in E$ tel que $P(x)$ soit fausse: c'est un contre-exemple. Ainsi:

• «toute fonction continue est dérivable» est réfutée par $x\mapsto |x|$ en $0$;
• «toute suite convergente est monotone à partir d'un certain rang» est réfutée par $u_n=(-1{)}^n/n$;
• «si $u_n\to 0$, alors converge» est réfutée par la série harmonique ;

À l'inverse, un million d'exemples ne prouvent pas un énoncé universel: la conjecture «$n^2+n+41$ est premier pour tout $n\in \mathbb{N}$» (Euler) est vraie pour $n=0,1,\dots ,39$ et fausse pour $n=40$. Un bon réflexe, face à un énoncé nouveau, est de chercher simultanément une démonstration et un contre-exemple: l'échec de l'un éclaire souvent l'autre.

Notations et alphabet grec

Les lettres grecques sont omniprésentes en analyse; voici celles que vous rencontrerez dans ce cours, avec leur prononciation usuelle en français et leurs emplois typiques.

Manipuler le symbole $\sum$

Deux transformations reviennent sans cesse. Le changement d'indice renomme la variable muette: avec $j=k+1$,

Le télescopage simplifie une somme de différences consécutives: tous les termes intermédiaires s'annulent deux à deux,

Par exemple, $\frac{1}{k(k+1)}=\frac{1}{k}-\frac{1}{k+1}$ donne , qui tend vers : c'est le prototype des séries télescopiques du chapitre 4. Enfin, un facteur qui ne dépend pas de l'indice sort de la somme (), mais un produit ne se distribue pas: en général.

Les symboles et notations qui suivent sont utilisés sans autre explication dans les chapitres.

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Références

• J. Douchet et B. Zwahlen, Calcul différentiel et intégral, vol. 1, Presses polytechniques et universitaires romandes (PPUR), Lausanne. Le manuel de référence des cours d'analyse de l'EPFL, dont ce cours reprend les notations.
• F. Liret et D. Martinais, Analyse 1re année. Cours et exercices avec solutions, Dunod, Paris. Chapitres de mise à niveau sur les ensembles, les fonctions et le raisonnement.
• D. J. Velleman, How to Prove It: A Structured Approach, 3e éd., Cambridge University Press. Le manuel de référence pour apprendre à construire et rédiger des démonstrations, avec quantificateurs et tables de vérité.
• K. Houston, How to Think Like a Mathematician: A Companion to Undergraduate Mathematics, Cambridge University Press. Lecture d'énoncés, contre-exemples, pièges de rédaction.
• R. Cori et D. Lascar, Logique mathématique, tome 1, Dunod, Paris. Pour aller plus loin: calcul propositionnel, calcul des prédicats, un peu de théorie des ensembles.
• G. Pólya, Comment poser et résoudre un problème, Dunod (trad. de How to Solve It). Heuristiques de recherche d'une démonstration, par un mathématicien qui enseigna à l'ETH Zurich de 1914 à 1940.