Logique et méthode axiomatique

"Les démonstrations sont les yeux de l'esprit."
Baruch Spinoza, Philosophe et polisseur de verres, (1632-1677).

"Une démonstration n'est pas autre chose que la résolution d'une vérité en d'autres vérités déjà connues."
Gottfried Wilhelm Leibniz, Mathématicien, philosophe, scientifique, diplomate, bibliothécaire et homme de loi allemand (1646 - 1716)

Logique élémentaire des propositions

Les mathématiques, c'est-à-dire les démonstrations mathématiques, reposent inconditionnellement sur des principes, ou règles, de "logique". Cette "logique" est celle qui permet entre autre d'inférer, manière de créer, des propositions à partir d'autres.
M. Jourdain manipulait la prose sans le savoir, les mathématiciens quant à eux raisonnaient "logiquement", depuis quelques millénaires, sans que cette "logique" et ses principes et règles ne soient clairement idientifiés.
A 18ème siècle, Emmanuel Kant écrivait à ce sujet que, depuis Aristote, la logique formelle "n'a pas pu faire un seul pas en avant, et qu'ainsi, selon toute apparence, elle semble close et achevée."¹

Quelques décennies plus tard, Georges Boole relança l'étude de la logique et publia en 1847 l'"analyse mathématique de la logique" dans lequel il fournit une algèbre de la logique (maintenant connue sous le nom d'"algèbre de Boole") et un ensemble de notations précises pour traiter des problèmes plus généraux, et surtout de manière plus précise et rigoureuse qu'avec la logique traditionnelle, antique et implicite.
Boole transforma ainsi le raisonnement logique en calculs: avec des valeurs de vérité pour certaines propositions (vraies ou fausses, 0 ou 1), on clacule la valeur de vérité d'autres propositions plus complexes, construites avec des règles de calcul explicite.
La question de savoir si tout raisonnement, voire même de tout type d'opération de la pensée, peut se ramener au calcul commence à émerger. Les machines à calculer et autres ordinateurs sont encore trop loin pour que cette question trouve un véritable écho. Turing, Kleene et Church y répondront un siècle plus tard, par le maintenant célèbre problème de l'arrêt.

En parallèle du programme de Boole, les mathématiques du 19ème siècle cherchaient à assoir les mathématiques pures, et le calcul infinitésimal, sur la logique formelle. Le courronnement de ces travaux se trouvent dans les "Principia mathematica"², publié en 1910 par Alfred North Whitehead et Bertrand Russel.
L'objectif y était de poser clairement les fondations des mathématiques: réduire tous les concepts arithmétiques à la logique et un petit nombre de propositions fondamentales assez évidentes pour être acceptables comme vérités purement logiques (axiomes).
Les Principia Mathematica semblaient être sur le point d'apporter une solution définitive au problème de la consistance³ des sytèmes mathématiques en ramenant ce problème à celui de la consistance de la logique formelle.

Quelques paradoxes et autres antinomies persistaient, comme le paradoxe de Russel, mais les Principia proposaient justement des outils élaborés pour s'en défaire (principe des "types" d'ensemble par exemple).
Néanmoins, lever ces antinomies n'expliquait guère, et ne convainquait donc pas plus, sur leur capacité à exclure toutes les antinomies et paradoxes, c'est-à-dire toute forme de constructions (auto-)contradictoires qui rendraient ainsi l'édifice complet inconsistant.
Les Principia n'apportèrent pas cette réponse, mais demeurent un travail fondamental, au moins de part les outils qu'ils fournissent, outils mathématiques et logiques formalisés, symboliques et rigoureux pour l'étude générale de la consistance de systèmes mathématiques.
D'une certaine façon aussi, les Principia fournirent l'outil qui, par la suite, permit de montrer leur échec. Les Principia constituent ainsi un vrai apport scientifique, au sens que le philosophe et épistémologue Karl Popper donnera aux théories scientifiques par la suite, en en ayant fournit les éléments et outils qui ont permis leur remise en cause.

Méthode axiomatique

Un premier exemple de système, le système PIPO (largement inspiré de [4]).

Système PIPO

On dispose de 3 lettres: P, I et O. On appelle proposition toute combinaison (ou chaîne) formée avec ces lettres.
Par exemple, PIO, POI, PIPO ou encore POIOIOIIII sont des propositions.
Bien sûr, toutes les propositions ne sont pas forcément vraies …
Bien sûr aussi, l'ordre des lettres dans une proposition compte.

Pour former (c'est-à-dire démontrer) une proposition, on a à notre disposition cinq axiomes:

Axiome 1: la chaîne PI
Axiome 2: si une chaîne se termine par I, on peut lui ajouter un O en fin.: Par exemple, PIOOI donne PIOOIO.
Axiome 3: d'une chaîne de type Px (où x est une chaîne quelconque), on peut faire une chaîne Pxx.: Par exemple, POP donne POPOP, et PIOOI donne PIOOIIOOI.
Axiome 4: si, dans une chaîne, on trouve trois I de suite, on a le droit de les remplacer par un O.: Par exemple, POIIIOI donne POOOI, et OPIIIPO donne OPOPO.
Axiome 5: si, dans une chaîne, on trouve deux O de suite, on a le droit de les abandonner.: Par exemple, IOOO donne IO.

À partir de ces axiomes, on peut tenter de démontrer, par exemple, les propositions (ou tenter de former les chaînes) PIPO, ou encore PIOIOIOI, ou PIOIOIO ou bien PO …
On arrive à construire certaines chaînes, d'autres non...
Parmi celles qu'on ne parvient pas à produire, on peut montrer pour certaines qu'on n'y parviendra jamais parce que cela est impossible.
Pour d'autres on n'arrive pas les démontrer, ni en fait à démontrer qu'il est impossible d'y parvenir … Est-ce parce qu'on n'est pas assez malins ?

On peut aussi démontrer de nouvelles règles, c'est-à-dire de nouveaux théorèmes, en tant que corollaire des axiomes fournis, par exemple, le corollaire "si dans une chaîne on a six I de suite, on peut les abondonner".

On crée et complète ainsi une liste de chaînes et de règles opératives au fur et à mesure.

On peut même imaginer sans mal un programme qui génère automatiquement toutes les chaînes valides: on applique toutes les axiomes possibles à la chaîne PI, puis tous les axiomes possibles à toutes les chaînes obtenues précédement, et ainsi de suite …

En fait, on peut imaginer aussi sans mal que le programme précédent ne s'arrête jamais, créant toujours et encore de nouvelles chaînes, sans cesse et sans relâche.

Pour formaliser un peu ce qui précède, on peut noter

E l'ensemble de toutes les chaînes que le programme précédent est capable de produire, c'est-à-dire l'ensemble de toutes les chaînes valides,
F l'ensemble de toutes les chaînes dont on peut montrer qu'elles ne sont pas valides.

Par exemple, PIPO est trivialement non valide, et donc PIPO ∈ F.
De même PI (axiome 1) et PIO (axiome 1 puis 2) sont valides: PI ∈ E et PIO ∈ E.
On a aussi évidemment ici PIPO ∉ E et PI ∉ F et PIO ∉ F, mais ceci est-il généralisable ?

Pour finir, notons Ω l'ensemble de toutes les chaînes possibles et imaginables formées des 3 lettres P, I et O:

Ω = { P; I; O; PI; PO; PP; IO; IP; IPP; IPOI; … }

alors deux questions essentielles se présentent:

A-t-on Ω = E ∪ F ?
En d'autres termes: pour toutes chaîne, est-on capable de montrer qu'elle est soit valide, soit invalide ?
Si tel est le cas, on parle de complétude du système axiomatique.
A-t-on E ∩ F = ∅ ?
En d'autres termes: existe-il des chaînes pour lesquelles on peut à la fois montrer qu'elles sont valides et qu'elles sont invalides ?
Si tel est le cas, on dit que le système axiomatique est consistant³, ou cohérent: il est impossible de montrer quelque chose et son contraire.

K. Gödel publiera en 1931 une réponse à ces questions fondamentales, dans ses célèbres théorème d' "incomplétudes", voir plus bas.

Géométrie euclidienne

À partir des 5 axiomes (aussi appelés postulats):

Axiome 1: il existe toujours une droite qui passe par deux points du plan
Axiome 2: tout segment peut être étendu suivant sa direction en une droite (infinie)
Axiome 3: à partir d'un segment, il existe un cercle dont le centre est un des points du segment et dont le rayon est la longueur du segment
Axiome 4: tous les angles droits sont égaux entre eux
Axiome 5: étant donné un point et une droite ne passant pas par ce point, il existe une seule droite passant par ce point et parallèle à la première

Ces axiomes ont été énoncés par Euclide (environ 300 av. J.C.) et ont fondé la géométrie (dite euclidienne ...) pendant près de 2000 ans.

Le 5ème axiome, dit axiome des parallèles, a tenu en haleine les géomètres et les mathématiciens pendant près de deux mille ans: Euclide lui-même ne semblait pas persuadé de son absolu nécessité. Il lui semblait qu'il devait pouvoir se déduire des 4 premiers axiomes. D'ailleurs, dans son immense traité de géométrie les premières (29 premières plus précisément) propriétés géométriques énoncées et démontrées le sont sans avoir recours à cet axiome des parallèles.

Géométrie non-euclidienne

Enfin donc, quelques 2000 ans plus tard, des mathématiciens comme Riemann eurent l'idée d'inverser le problème: si cet axiome découle vraiment des autres, alors en utilisant un système formé des 4 premiers axiomes et du 5ème nié: par un point donné il ne passe aucune parallèle à une autre droite on devrait arriver à une contradiction.

Axiome 1: il existe toujours une droite qui passe par deux points du plan
Axiome 2: tout segment peut être étendu suivant sa direction en une droite (infinie)
Axiome 3: à partir d'un segment, il existe un cercle dont le centre est un des points du segment et dont le rayon est la longueur du segment
Axiome 4: tous les angles droits sont égaux entre eux
Axiome 5: étant donné un point et une droite ne passant pas par ce point, il existe une seule droite passant par ce point et parallèle à la première: étant donné un point et une droite ne passant pas par ce point, il n'existe aucune droite parallèle à la première passant par ce point

Ce ne fut pas le cas, les systèmes ainsi formés restèrent consistants, et ne virent jamais pointer une absurdité ou une quelconqque contradiction !
Il resta alors à comprendre ce qui venait d'être créé ... Il s'agit de la géométrie riemanienne, la géométrie non plane, par exemple la géométrie à la surface d'une sphère (ou à la surface d'une planète comme la Terre ...), alors qu'Euclide et ses 5 axiomes traite de la géométrie plane.

Arithmétique de Péano

Giuseppe Peano proposa à la fin du 19ème siècle 5 axiomes pour définir rigoureusement l'ensemble N des entiers naturels et axiomatiser l'arithmétique:

Axiome 1: L'élément appelé zéro et noté 0 est un entier naturel.
Axiome 2: Tout entier naturel n a un unique successeur, noté s(n) ou Sn.
Axiome 3: Aucun entier naturel n'a 0 pour successeur
Axiome 4: Deux entiers naturels ayant le même successeur sont égaux.
Axiome 5: Si un ensemble d'entiers naturels contient 0 et contient le successeur de chacun de ses éléments, alors cet ensemble est égal à N.

Le 5ème axiome est bien connu comme sous le nom de principe de récurrence.
Là aussi, ce 5ème axiome a été particulièrement étudié; voir là, une démonstration de ce principe (qui devient alors un théorème et non plus un axiome) à partir d'un autre axiome.

Tout ramener à la logique formelle, certes. Mais celle-ci est-elle consistante ?

Assez clairement il apparaît que la notion de démonstration se veut reposer sur deux éléments uniquement: la logique formelle des propositions et un ensemble d'axiomes (qu'on souhaite le plus restreint possible).

La logique est donc, comme annoncé au tout début, l'outil le plus fondamental, le liant de tous les raisonnements et démonstrations. Il est alors fortement souhaitable, et la formule est on ne peut plus faible, que cette logique elle-même soit consistante, c'est-à-dire que, même et déjà sans la mêler à une autre théorie (arithmétique, géométrie, ...), elle ne puisse à elle seule aboutir des contradictions.
Autre remarque fondamentale sur cette consistance: il est fondamental aussi de ne faire reposer une démonstration de cette consistance sur aucune autre théorie extérieure à la logique elle-même, sans quoi on ne ferait à nouveau que déplacer le problème et nécessiter la même démonstration pour un système plus vaste.
Une telle propriété de consistance est qualifiée d'absolue, et elle est possédée par la logique formelle des propositions.

Axiomatisation de la logique

Écrire l'ensemble de la logique sous forme d'axiomes a au moins deux objectifs, fondamentaux tous les deux:

rendre explicite les règles et le fonctionnement de la logique et dépasser, enfin, l'implicite évoqué au tout début.
Entre autre, ce qui était déjà cher à Aristote, on devra pouvoir séparer clairement et objectivement une démonstration logique correcte, ou valide, d'une qui ne l'est pas.
s'attaquer à la question essentielle: cette logique est-elle consistante ? ou permet-elle d'arriver, catastrophiquement, à des contradictions en menant des démonstrations valides partant d'un même point.

Cette axiomatisation comporte 4 axiomes:

Axiomes pour la disjonction:
- A ⇒ ( A ∨ B)
- ¬A ⇒ ( ( A ∨ B) ⇒ B )
Axiomes pour la conjection:
- A ⇒ ( B ⇒ ( A ∧ B)
- ( A ∧ B ⇒ ) ⇒ A

Consistance (absolue !) de la logique

On peut maintenant montrer que la logique des propositions (ou booléenne) est consistante. Cette démonstration se faisant de plus à l'intérieur de cette logique elle-même, c'est-à-dire en n'utilisant que ses règles et axiomes précédents, on démontre ainsi sa consistance absolue.

Supposons en effet qu'il soit possible de démontrer une proposition F et son contraire ¬F.
Comme on a toujours, pour toute proposition G, le symbole "∨" désignant le "ou" logique,

F ⇒ ( F ∨ G )

on a donc, comme F est supposé vraie, que F ∨ G est aussi vraie.
On a aussi, avec le même raisonnement appliqué à ¬F :

¬F ⇒ ( ¬F ∨ G )

et ainsi, comme on a supposé que ¬F est vraie, on a donc aussi que ¬F ∨ G est vraie.

Ces deux propriétés étant simultanément vraie, on a aussi que (en désignant par "∧" le "et" logique)

( F ∨ G ) ∧ ( ¬F ∨ G )

est vraie.

Or, on démontre facilement (en utilisant par exemple une table de vérité^*) que cette propriété est logiquement équivalente à G:

( ( F ∨ G ) ∧ ( ¬F ∨ G ) ) ⇔ G

On vient donc de démontrer, finalement, que si il est possible à l'aide de la logique des propositions (logique de Boole) de montrer une proposition et son contraire, alors il est possible de montrer toute proposition G (et donc aussi son contraire ¬G).
Ceci est absurde car on sait qu'il existe des propositions (au moins une suffirait) qui n'est pas vraie.
Par exemple la propriété A∧B n'est pas toujours vraie, suivant les valeurs de A et B.

On a ainsi montrer que la logique des propostions est consistante, et ce de manière absolue. C'est un bon point de départ pour la suite ... mais qui va s'avérer insuffisant ...

Théorème de Gödel

En 1931 Kurt Gödel, jeune mathématicien de 25 ans, publia un court article dans une revue allemande, au titre assez rébarbatif: " Sur les propositions formellement indécidables des Principia Mathematica² et des systèmes apparentés ".
Cet article contient les deux, maintenant célèbres, théorèmes d'"incomplétudes", à savoir, pour citer Gödel lui-même³:

" Dans tout système formel consistant³ contenant une théorie des nombres finitaires relativement développée, il existe des propositions indécidables "
" la consistance d'un tel système ne saurait être démontré à l'intérieur d'un tel système "

La premier théorème est une alternative:

soit le système est inconsistant, ce qui qu'il existe des propriétés dont on peut démontrer à la fois qu'elles sont vraies et fausses,
soit il contient des propositions dont il est impossible de montrer ni qu'elles sont vraies, ni qu'elles sont fausses: elles sont indécidables.

Exemples de propositions indécidables

Hypothèse du continu

Lorsqu'un problème porte sur un nombre fini d'éléments, il est difficile d'imaginer qu'il soit indécidable: il suffit de tester toutes les possibilités pour conclure …
Un exemple de tel problème indécidable est né justement avec les recherches sur l'infini de Georg Cantor, un mathématicien allemand (1845-1918).
Cantor s'est intéressé à la nature de l'infini, à essayer de fournir des outils pour l'étudier rigoureusement et de voir s'il y a avait plusieurs "types" d'infini.
Jusqu'à lui, l'infini, ou les infinis posaient des problèmes parce que s'ils étaient manipulés avec des outils "classiques", c'est-à-dire les outils et opérations portant sur les nombres (finis), des contraditions ou paradoxes apparaissaient.
Par exemple, on s'aperçoit facilement qu'il y a exactement autant de nombres entiers naturels (0, 1, 2, 3, ...) que d'entiers naturels pairs (0, 2, 4, 6, ...). En effet, ces deux ensembles peuvent être mis en bijection: à chaque entier correspond exactement un entier pair: son double, et à chaque entier pair coresspond exactement un entier: sa moitié.
On associe ainsi bijectivement (biunivoquement est un terme synonyme, plus littéraire):

1↔2 ; 2↔4 ; 3↔6; ...

On en conclut donc qu'il y a exactement autant de nombres entiers que de nombres pairs. Or on voit bien aussi qu'il y exactement, aussi, le double d'entiers naturels que d'entiers pairs (pour constituer l'ensemble des antiers pairs, on prend un entier naturel sur deux).
Ce genre de paradoxe n'en est plus un, c'est la définition même du fait qu'il y a un nombre infini de nombre entiers, et d'une certaine façon, les opérations sur l'infini diffèrent de celles sur les nombres finis, et on peut ici écrire:

2 x ∞ = ∞

égalité qui n'est vrai pour aucun nombre fini autre que 0 (mais on n'est bien persuadé qu'il n'y a pas 0 nombre entier ! 0 est entier, donc il y en a au moins 1 !).

Les interrogations de Cantor portèrent ensuite sur la comparaison des infinis: y-a-t'il par exemple plus de nombre rationnels que de nombre entiers ? plus de nombres réels que de nombres entiers ?
Cantor démontra clairement qu'il y a plus de nombres réels que de nombres entiers: l'infinité des nombres réels est strctement plus grande que l'infinité des nombres entiers. Dit d'une autre manière, on ne peut pas compter, ou dénombrer, les nombres réels.

Par contre, Cantor pensait, mais n'a pas su démontrer, qu'entre l'infini des nombres entiers et l'infini des nombres réels il n'y existe pas d'ensemble de nombres contenant plus de nombres que les nombres entiers, et moins que les nombres réels.
Cette conjecture émise par Cantor est maintenant relativement célèbre sous le nom d'"hypothèse du continu": tout sous-ensemble de R est soit dénombrable, soit continu.

En 1940, Gödel bâtit une théorie consistante en supposant vrai cette hypothèse du continu. Quelque temps après, son élève Paul Cohen fit de même ... en supposant cette hypothèse fausse et aboutit aussi à une théorie consistante.
Cette hypothèse est donc une proposition indécidable, qu'on la suppose vraie ou fausse, on peut batir avec une théorie cohérente.

Problème de l'arrêt

Une méthode de calcul peut comporter un certain nombre d'étapes. Par exemple, assez simplement, se demander si 30 est un nombre pair, uniquement par des considérations calculatoires, passe par l'examen successif des doubles des nombres entiers 0, 1, 2, 3, ... jusqu'à 15 qui nous permet de conclure que 30 est bien pair.
Néanmoins le même problème avec 31 révèle nettement une difficulté. La méthode précédente ne donne aucun résultat, et effectuera des calculs sans cesse.

Turing, Church et Kleene se sont intéressés, indépendamment, au problème dit de "l'arrêt" qui consiste à se demander si une méthode de calcul va donner un résultat ou non. Ce qu'ont montré Turing, Church et Kleene, c'est que ce problème ne peut se résoudre par le calcul. En effet, la méthode peut rappeler celle du paradoxe du menteur et ses variantes: supposons qu'il existe une méthode de calcul qui permette d'analyser les autres méthodes de calcul et qui donne un résultat uniquement quand la méthode analysée n'en donne pas.
On arrive alors à une impossiblité: si cette méthode existe, elle pourrait donc en particulier s'analyser elle-même ... et donner un résultat seulement si ... elle n'en donne pas.

Enfin, le langage étant universel, il permet d'exprimer tout type de propriété, entre autre la propriété "telle méthode de calcul donne un résultat". S'il y avait une méthode calcul qui permette si une phrase est démontrable ou non, il sufirait de l'appliquer à celle précédente pour résoudre le problème de l'arrêt, ce qui est impossible.
Ce qu'ont ainsi montré Church, Turing et Kleene, est que le calcul est limité, et qu'on ne peut y réduire le raisonnement.
Le raisonnement est plus puissant, dans le sens ou il donne accès à plus d'éléments, que le calcul.

Notes et références bibliographiques:

[1] E. Kant, Critique de la raison pure
[2] Les Principia Mathematica sont un traité monumental et fondamental en 3 volumes, dû à Alfred North Whitehead et Bertrand Russel, et qui portent sur les fondements des mathématiques et la logique mathématique.
[3] La consistance d'une théorie ou d'un système formel est une propriété indiquant qu'il est impossible de montrer à partir des éléments de cette théorie une propriété et son contraire.
"Consistance" est la traduction de l'anglais "consistent" dont une traduction plus littérale est "cohérent" ce qui reflète bien (mieux ?) la propriété: une théorie consistante est une théorie "cohérente", ou encore dans laquelle on ne peut trouver d'incohérence.
[3] Le théorème de Gödel, E. Nagel, J.R. Newman, K. Gödel, et J.Y. Girard
[4] Gödel, Escher, Bach: Les Brins d'une Guirlande Éternelle, Douglas Hofstadter
* Table de vérité qui permet de montrer que (F∨G)∧(¬F∨G) ⇔ G

F G F∨G ¬F ¬F∨G (F∨G)∧(¬F∨G)

0 0 0 1 1 0

0 1 1 1 1 1

1 0 1 0 0 0

1 1 1 0 1 1

Voir aussi:

F	G	F∨G	¬F	¬F∨G	(F∨G)∧(¬F∨G)
0	0	0	1	1	0
0	1	1	1	1	1
1	0	1	0	0	0
1	1	1	0	1	1