La différence entre ce que nous avons fait en Coq et votre cours de mathématiques classique est que Coq n'est pas équipé par défaut du principe du tiers exclu qui dit qu'une proposition est soit vraie, soit fausse. Donc, jusqu'à présent, nous n'avons pas pu faire de preuve par l'absurde, ni de raisonnement par contraposition.
Voici l'axiome du tiers-exclu :
Attention, un axiome n'est pas un théorème. En ajoutant un axiome on prend
le risque énorme que la théorie devienne incohérente, c'est-à-dire permette
de prouver
False
.
Dans notre cas, un théorème difficile montre que si Coq est correct
(c'est-à-dire ne permet pas de prouver
False
), alors il l'est encore avec
le tiers exclu.
Avec cet axiome, on peut prouver, par exemple, que le raisonnement par l'absurde est correct.
Remarquer
destruct (classic P) as [HP | HnP
.]. Ici,
classic
est un axiome qui prend une proposition en argument et
(classic P)
est une preuve de
(P \/ ~P)
. Avec
destruct
, on
peut donc la détruire et faire une preuve par cas.
Remarque (voir les exercices à faire à la maison) :
En utilisant le tiers exclu ou l'une de ses conséquences, prouver le théorème suivant :
En utilisant le tiers exclu ou l'une de ses conséquences, prouver le théorème suivant :
On va voir qu'en logique classique (comme dans vos cours de mathématique), la négation d'un "il existe" est un "pour tout" et la négation d'un "pour tout" est un "il existe".
Les deux prochains théorèmes n'ont pas besoin de l'axiome du tiers exclu.
Mais à partir d'ici, il y en a besoin. Remarquez que ce n'est pas toujours
facile de deviner à quelle proposition il faut l'appliquer.
Ici, il faut
destruct (classic (P n))
pour raisonner par cas sur
P n
.