5. DÉMONSTRATIONS



THÉORIE DE LA DÉMONSTRATION

1. Crise des fondements

1.1.Paradoxes

2. Raisonnement hypothético-déductif

3. Calcul propositionnel

3.1. Propositions

3.2. Connecteurs

3.3. Procédures de décision

3.3.1. Procédures de décision non axiomatisées

3.3.2. Procédures de décision axiomatisées

3.4. Quantificateurs

4. Calcul des prédicats

4.1. Grammaire

4.2. Langages

4.2.1. Symboles

4.2.2. Termes

4.2.3. Formules

5. Démonstrations

5.1. Règles de démonstration

Les démonstrations que l'on trouve dans les ouvrages de mathématiques sont des assemblages de symboles mathématiques et de phrases contenant des mots clés tels que: "donc", "parce que", "si", "si et seulement si", "il est nécessaire que", "il suffit de", "prenons un x tel que", "supposons que", "cherchons une contradiction", etc. Ces mots sont supposés être compris par tous de la même manière, ce qui n'est en fait, pas toujours le cas.

Dans tout ouvrage, le but d'une démonstration est de convaincre le lecteur de la vérité de l'énoncé. Suivant le niveau du lecteur, cette démonstration sera plus ou moins détaillée : quelque chose qui pourra être considéré comme évident dans un cours de licence pourrait ne pas l'être dans un cours de niveau inférieur.

Dans un devoir, le correcteur sait que le résultat demandé à l'étudiant est vrai et il en connaît la démonstration. L'étudiant doit démontrer (correctement) le résultat demandé. Le niveau de détail qu'il doit donner  dépend donc de la confiance qu'aura le correcteur : dans une bonne copie, une "preuve par une récurrence évidente" passera bien, alors que dans une copie où il y eu auparavant un "évident", qui était évidemment... faux, ça ne passera pas!

Pour pouvoir gérer convenablement le niveau de détail, il faut savoir ce qu'est une démonstration complète. Ce travail de formalisation a été fait qu'au début de 20ème siècle!!

Plusieurs choses peuvent paraître surprenantes:

- il n'y a qu'un nombre fini de règles: deux pour chacun des connecteurs (et l'égalité) plus trois règles générales. Il n'était pas du tout évident à piori qu'un nombre fini de règles soit suffisant pour démontrer tout ce qui est vrai. Nous montrerons ce résultat (c'est essentiellement, le théorème de complétude). La preuve n'en est pas du tout triviale.

- ce sont les mêmes règles pour toutes les mathématiques et la physique: algèbre, analyse, géométrie, etc. Cela veut dire que nous avons réussi à isoler tout ce qui est général dans un raisonnement. Nous verrons plus loin qu'une démonstration est un assemblage de couples, où equation est un ensemble de formules (les hypothèses) et A une formule (la conclusion). Quand nous faisons de l'arithmétique, de la géométrie ou de l'analyse réelle, nous utilisons, en plus des règles, des hypothèses que l'on appelle des "axiomes". Ceux-ci expriment les propriétés particulières des objets que nous manipulons (pour plus de détails sur les axiomes voir la page d'introduction du site).

Nous démontrons donc, en général, des formules en utilisant un ensemble d'hypothèses, et cet ensemble peut varier au cours de la démonstration: quand nous disons "supposons F et montrons G", F est alors une nouvelle hypothèse que nous pourrons utiliser pour montrer G. Pour formaliser cela, nous introduisons le concept de "séquent":

Définitions:

D1. Un "séquent" est un couple (noté equation) où :

- equation est un ensemble fini de formules qui représente les hypothèses que nous pouvons utiliser. Cet ensemble s'appelle aussi le "contexte du séquent".

- F est une formule. C'est la formule que nous voulons montrer. Nous dirons que cette formule est la "conclusion du séquent".

Remarques:

R1. Si equation nous pourrons noter equation au lieu de equation. Le signe equation se lit "thèse" ou "démontre". 

R2. Nous noterons equation un séquent dont l'ensemble d'hypothèses est vide et equation un séquent dont l'ensemble d'hypothèses est equation

R3. Nous noterons que dans le séquent equation la formule A peut-être dans equation (elle devient alors un hypothèse).

R4. Nous écrirons equation pour dire que "equation est non prouvable".

D2. Un séquent equation est "prouvable" (ou démontrable, dérivable) s'il peut être obtenu par une application finie de règles. Une formule F est prouvable si le séquent equation est prouvable.

5.1. RÈGLES DE DÉMONSTRATION

Les règles de démonstration sont les briques qui permettent de construire les dérivations. Une dérivation formelle est un assemblage fini (et correct!) de règles. Cet assemblage n'est pas linéaire (ce n'est pas une suite) mais un "arbre". Nous sommes en effet souvent amenés à faire des branchements.

Nous allons présenter un choix de règles. Nous aurions pu en présenter d'autres (à la place ou en plus) qui donneraient la même notion de prouvabilité. Celles que l'on a choisies sont "naturelles" et correspondent aux raisonnements que l'on fait habituellement en mathématique. Dans la pratique courante nous utilisons, en plus des règles ci-dessous, beaucoup d'autres règles mais celles-ci peuvent se déduire des précédentes. Nous les appellerons "règles dérivées".

Il est de tradition d'écrire la racine de l'arbre (le séquent conclusion) en bas, les feuilles en haut: la nature est ainsi faite... Comme il est également de tradition d'écrire, sur une feuille de papier, de haut en bas, il ne serait pas déraisonnable d'écrire la racine en haut et les feuilles en bas. Il faut faire un choix !

Une règle se compose:

- d'un ensemble de "prémisses": chacune d'elles est un séquent. Il peut y en avoir zéro, un ou plusieurs

- du séquent conclusion de la règle

- d'une barre horizontale séparant les prémisses (en haut) de la conclusion (en bas). Sur la droit de la barre, nous indiquerons le nom de la règle.

exemple Exemple:

equation   (1.30)

Cette règle à deux prémisses (equation et  equation) et une conclusion (equation). Le nom abrégé de cette règle est equation.

Cette règle peut se lire de deux manières :

- de bas en haut: si nous voulons prouver la conclusion, il suffit par utilisation de la règle de prouver les prémisses. C'est ce qu'on fait quand nous cherchons une démonstration. Cela correspond à "l'analyse".

- de haut en bas: si nous avons prouvé les prémisses, alors nous avons aussi prouvé la conclusion. C'est ce que nous faisons fait quand nous rédigons une démonstration. Cela correspond à la "synthèse".

Pour les démonstrations il existe un nombre fini de règles au nombre de 17 que nous allons définir ci-après:

1. Axiome:

equation   (1.31)

De bas en haut : si la conclusion du séquent est une des hypothèses, alors le séquent est prouvable.

2. Affaiblissement:

equation   (1.32)

Explications :

- De haut en bas : si nous démontrons A sous les hypothèses equation, en ajoutant d'autres hypothèses on peut encore démontrer A.

- De bas en haut : il y a des hypothèses qui peuvent ne pas servir

3. Introduction de l'implication:

equation   (1.33)

- De bas en haut: pour montre que equation nous supposons A (c'est-à-dire que nous l'ajoutons aux hypothèses) et nous démontrons B.

4. Elimination de l'implication:

equation   (1.34)

- De bas en haut : pour démontrer B, si nous connaissons un théorème de la forme equation et si nous pouvons démontrer le lemme equation, il suffit de démontrer A.

5. Introduction à la conjonction:

equation   (1.35)

- De bas en haut : pour montrer equation, il suffit de montrer A et de montrer B.

6. Elimination de la conjonction:

equation   (1.36)  et equation   (1.37)

- De haut en bas: de equation, nous pouvons déduire A (élimination gauche) et B (élimination droite).

7. Introduction de la disjonction:

equation   (1.38)  ou equation   (1.39)

- De bas en haut: pour démontrer equation, il suffit de démontrer A (disjonction gauche) ou de démontrer B (disjonction droite).

8. Elimination de la disjonction:

equation   (1.40)

- De bas en haut : si nous voulons montrer C et que nous savons que nous avons equation, il suffit de le montrer d'une part en supposant A, d'autre part en supposant B. C'est un raisonnement par cas.

9. Introduction de la négation:

equation   (1.41)

- De bas en haut: pour montrer equation, nous supposons A et nous démontrons l'absurde (equation).

10. Elimination de la négation:

equation   (1.42)

- De haut en bas : si nous avons montré equation et A, alors nous avons montré l'absurde (equation)

11. Absurdité classique:

equation   (1.43)

- De bas en haut: pour démontrer A, il suffit de démontrer l'absurde en supposant equation.

Cette règle, est équivalente à dire : A est vraie si et seulement si il est faux que A soit fausse. Cette règle ne va pas de soi : elle est nécessaire pour prouver certains résultats (il y a des résultats que nous ne pouvons pas prouver si nous n'avons pas cette règle). Contrairement, à beaucoup d'autres, cette règle peut par ailleurs être appliquée à tout moment. Nous pouvons, en effet, toujours dire : pour prouver A je suppose equation et je vais chercher une contradiction.

12. Introduction au quantificateur universel:

equation   (1.44)

- De bas en haut: pour démontrer equation, il suffit de montrer A en ne faisant aucune hypothèse sur x.

Remarque: pour des démonstrations cette vérification (aucune hypothèse sur x) est souvent source d'erreur.

13. Elimination du quantificateur universel:

equation   (1.45)

- De haut en bas: de equation, nous pouvons déduire equation pour n'import quel terme t. Ce que nous pouvons dire aussi sous la forme: si nous avons prouvé A pour tout x, alors nous pouvons utiliser A avec n'importe quel objet t (!!).

14. Introduction du quantificateur existentiel:

equation   (1.46)

- De bas en haut: pour démontrer equation, il suffit de trouver un objet (in extenso un terme t) pour lequel nous savons montrer equation.

15. Elimination du quantificateur existentiel:

equation   (1.47)

- De bas en haut: nous démontrons qu'il existe bien un ensemble d'hypothèses tel que equation et partant de ce résultat comme nouvelle hypothèse, nous démontrons C. Cette formule C hérite alors de la formule equation et dès lors x n'est pas libre dans C car il ne l'était déjà pas dans equation.

16. Introduction de l'égalité:

equation   (1.48)

De bas en haut: nous pouvons toujours montrer t=t. Cette règle signifie que l'égalité est réflexive (cf. chapitre Opérateurs).

17. Elimination de l'égalité:

equation   (1.49)

- De haut en bas: si nous avons démontré equation et t=u, alors nous avons démontré equation. Cette règle exprime que les objets égaux ont les mêmes propriétés. Nous noterons cependant que les formules (ou relations) t=u et u=t ne sont pas, formellement, identiques. Il nous faudra démontrer que l'égalité est symétrique (nous en profiterons aussi pour démontrer que l'égalité est transitive).

exemple Exemples:

E1. Cet exemple montre que l'égalité est symétrique (un petit peu non trivial mais bon pour commencer) :

equation   (1.50)

- De haut en bas: nous introduisons l'égalité equation et prouvons à partir de l'hypothèse equation la formule equation. En même temps, nous définissons l'axiome comme quoi equation. Ensuite à partir de ces prémisses, nous éliminons l'égalité equation en substituant les termes de façon à ce que à partir de la supposition equation (venant de l'axiome) nous obtenions equation. Ensuite, l'élimination de l'égalité implique automatiquement sans aucune hypothèse que equation. Dès lors, il nous suffit d'introduire le quantificateur universel pour chacune des variables (donc deux fois) sans aucune hypothèse afin d'obtenir que l'égalité est symétrique.

E2. Cet exemple montre que l'égalité est transitive (c'est-à-dire si equation et equation alors equation) . En notant F la formule equation :

equation   (1.51)

Que faisons, nous ici ? Nous introduisons d'abord la formule F deux fois en tant qu'axiome afin de la décortiquer plus tard à gauche et à droite (nous n'introduisons pas l'égalité supposée déjà introduite en tant que règle). Une fois ceci fait, nous éliminons à gauche et à droite la conjonction sur la formule pour travailler sur les termes gauches et droites seuls et introduisons l'égalité sur les deux termes ce qui fait qu'à partir de la formule nous avons l'égalité transitive. Il s'ensuit que sans aucune hypothèse cela implique automatiquement que l'égalité est transitive et finalement nous disons que ceci est valable pour tout valeur des différentes variables (si la formule est vraie, alors l'égalité est transitive).

E3. L'objectif sera de démontrer que toute involution est une bijection (cf. chapitre de Théorie Des Ensembles). Soit f un symbole de fonction unaire (à une variable), nous notons (pour plus de détails voir le chapitre de Théorie Des Ensembles) :

- equation la formule:

equation   (1.52)

qui signifie que f est injective.

- equation la formule:

equation   (1.53)

qui signifie que f est surjective

- equation la formule:

equation   (1.54)

qui signifie que f est bijective.

- equation la formule:

equation   (1.55)

qui signifie que f est une involution (nous notons également cela equation c'est-à-dire que la composition de f est l'identité).

Nous aimerions savoir si :

equation   (1.56)

Nous allons présenter (en essayant que ce soit au plus clair) cette démonstration de quatre manières différentes : classique (informelle), classique (pseudo-formelle) et formelle en arbre et formelle en ligne.

Méthode classique :

Nous devons montrer que si f est involutive alors elle est donc bijective. Nous avons donc deux choses à montrer (et les deux doivent être satisfaites en même temps) : que la fonction est injective et surjective.

1. Montrons que l'involution est injective. Nous supposons pour cela, puisque f est involutive elle est donc injective, tel que :

equation   (1.57)

implique:

equation   (1.58)

Or, cette supposition découle automatiquement de la définition de l'involution que:

equation   (1.59)

et de l'application de f à la relation :

equation   (1.60)

(soit trois égalités) tel que:

equation   (1.61)

nous avons donc:

equation   (1.62)

2. Montrons que l'involution est surjective : si elle est surjective, alors nous devons avoir:

equation   (1.63)

Or, définissons la variable x par définition de l'involution elle-même:

equation   (1.64)

(puisque equation...) un changement de variables après nous obtenons:

equation   (1.65)

et donc la surjectivité est assurée.

Méthode pseudo-formelle :

Nous reprenons la même chose et nous y injectons les règles de la théorie de la démonstration :

Nous devons montrer que f involutive est donc bijective. Nous avons donc deux choses à montrer equation (et les deux doivent être satisfaites en même temps) : que la fonction est injective et surjective:

equation   (1.66)

1. Montrons d'abord que l'involution est injective. Nous supposons pour cela, puisque f est involutive et donc injective, que:

equation equation   (1.67)

implique:

equation equation   (1.68)

Or, cette supposition découle automatiquement de la définition de l'involution que:

equationequation   (1.69)

et de l'application de f à la relation:

equation   (1.70)

(soit trois égalités equation) tel que:

equation   (1.71)

nous avons donc:

equation   (1.72)

2. Montrons que l'involution est surjective. Si elle est surjective, alors nous devons avoir:

equationequation   (1.73)

Or, définissons la variable x par définition de l'involution elle-même:

equationequation   (1.74)

(puisque equation...) un changement de variables après nous obtenons:

equation   (1.75)

et donc:

equation   (1.76)

la surjectivité est assurée.

Méthode formelle en arbre :

Faisons cela avec la méthode graphique que nous avons déjà présentée plus haut.

1. Montrons que l'involution est injective :

Pour cela, d'abord montrons que equation

equation   (1.77)

Remarque: Cette dernière relation est abrégée equation et appelée (comme d'autres existantes) "règle dérivée" car c'est un raisonnement qui est très souvent fait lors de démonstrations et un peu long à développer à chaque fois...

Dès lors :

equation   (1.78)

2. Montrons que l'involution est surjective :

equation   (1.79)

Il s'ensuit :

equation   (1.80)

Méthode formelle en ligne :

Nous pouvons faire la même chose sous une forme un peu moins... large... et plus tabulée... (cela n'en est pas moins indigeste) :