Démonstration (logique et mathématiques)

Dans le style de Fitch pour la déduction naturelle, une démonstration est « une suite finie de formules dont chacune est soit un axiome, soit une conséquence immédiate des formes précédentes en vertus d'une règle d'inférence »[3]. En déduction naturelle, une démonstration est un arbre[note 1].

De manière générale, une démonstration est un « raisonnement qui permet d'établir une proposition[4] ».

Dans son documentaire consacré au dernier théorème de Fermat[5], Simon Singh demande à des mathématiciens parmi lesquels John Conway, Bary Mazur, Ken Ribet, John Coates, Richard Taylor de préciser la notion de démonstration en mathématiques. Ils proposent, informellement : « suite d'arguments basée sur des déductions logiques, qui découlent les unes des autres, étape par étape, jusqu'à ce que vous établissiez une preuve rigoureuse ».

On trouve les premières démonstrations rigoureuses chez Euclide.

Une proposition une fois démontrée peut ensuite être elle-même utilisée dans d'autres démonstrations. Dans toute situation où les propositions initiales sont vraies, la proposition démontrée devrait être vraie[note 2] ; on ne pourrait la remettre en cause qu'en remettant en cause une ou plusieurs des propositions initiales ou le système de règles de déduction lui-même.

Cette description peut s'avérer idéale. Il arrive qu'une démonstration s'appuie partiellement sur l'intuition, géométrique par exemple, et donc que toutes les propriétés admises, les axiomes, ne soient pas explicites. Les démonstrations de géométrie que l'on peut trouver dans les Éléments d'Euclide sont par exemple considérées encore aujourd'hui comme des modèles de rigueur, alors qu'Euclide s'appuie en partie sur des axiomes implicites, comme l'a montré David Hilbert dans ses « fondements de la géométrie ». Par ailleurs, les démonstrations des mathématiciens ne sont pas formelles et une démonstration peut être considérée comme correcte dans les grandes lignes, alors que des points resteraient à expliciter en toute rigueur, voire que d'autres sont entachés d'erreurs « mineures ». On rédige une démonstration pour être lue et convaincre les lecteurs, et le niveau de détail nécessaire n'est pas le même suivant les connaissances de ceux-ci. Cependant avec l'avènement des ordinateurs et des systèmes d'aide à la démonstration, certains mathématiciens contemporains rédigent des démonstrations qui sont amenées à être vérifiées par des programmes.

Les démonstrations mathématiques passent par diverses étapes en suivant une certaine ligne de déduction. Certains grands types de démonstrations ont reçu des dénominations spécifiques.

• Les mathématiciens parlent assez informellement de démonstration directe, pour une démonstration d'un énoncé n'utilisant que les constituants de celui-ci, de la façon la plus simple possible, sans les recomposer, et sans le déduire de théorèmes plus forts. Dans certains contextes, on peut considérer qu'une démonstration par l'absurde ou par contraposition est indirecte.
• Une démonstration par un contre-exemple permet de valider une propriété existentielle (ou invalider une propriété universelle) (mais, en général, une proposition universelle ne peut être prouvée par un ou plusieurs exemples, même bien choisis).
• Une démonstration par disjonction de cas consiste à montrer que l'énoncé se ramène à un certain nombre (fini) de cas distincts, puis à les démontrer séparément.
• Une démonstration par l'absurde consiste à montrer qu'en affirmant la négation de l'assertion à démontrer on aboutit à une contradiction, typiquement une proposition et sa négation.
• Une démonstration est constructive si elle inclut une construction ou un mode de recherche effectif des objets dont elle établit l'existence.
• Une démonstration par récurrence s'appuie sur une méthode de déduction spécifique (dite récurrence) pour affirmer qu'une assertion est démontrable pour tous les entiers naturels : elle consiste à démontrer l'assertion pour 0, puis à démontrer que de l'assertion pour l'entier n, on peut déduire l'assertion pour l'entier n+1. Il existe des variantes plus générales pour les éléments d'un certain ensemble bien ordonné ou pour des structures qui sont construites d'une façon qui étend celle avec laquelle les entiers naturels sont décrits.
• Une démonstration probabiliste[8] utilise la théorie des probabilités pour démontrer l'existence certaine d'un objet.
• Une démonstration par analyse-synthèse consiste à étudier les propriétés de l'hypothétique solution d'un problème dont on cherche à prouver l'existence et l'unicité, jusqu'à identifier une seule solution possible, puis à montrer que ce candidat est effectivement solution.
• Une démonstration sans mots s'appuie sur une représentation visuelle d'un exemple bien choisi de la propriété à démontrer ; la valeur démonstrative d'un tel processus est néanmoins souvent contestée et il s'agit plutôt d'une heuristique.
• Une démonstration combinatoire peut se faire par double dénombrement ou en considérant une bijection bien choisie.

La logique mathématique a développé une branche qui est consacrée à l'étude des démonstrations et des systèmes déductifs et s'appelle pour cela la théorie de la démonstration. Ainsi, la notion de démonstration est formalisée. On parle alors de démonstration formelle en tant qu'objet mathématique[9] qui contient toutes les étapes de la déduction. Une formule F d’un langage L est dite démontrée dans une théorie T si et seulement s’il existe une suite finie de formules se terminant par F, telle que :

• ou bien F est une formule de T ou un axiome logique,
• ou bien F est déduite, par les règles d'inférence de la logique sous-jacente à T, des formules qui la précède dans la suite.