Consistant(système formel)

Imaginez un cahier qui contient des règles de raisonnement. Si ces règles permettent d’écrire à la fois une affirmation et son contraire, le cahier ne donne plus de verdict fiable. Un système consistant évite précisément ce choc : aucune formule ne peut y être dérivée en même temps que sa négation.

Cette absence de contradiction est un minimum, pas la promesse que le système répondra à toutes les questions.

La consistance, aussi appelée cohérence, est une propriété d’un système formel. Elle concerne les formules que ses axiomes et ses règles permettent de dériver. Pour un système nommé S et une formule nommée P, le critère s’écrit :

Le symbole de dérivation signifie ici « peut être obtenu dans le système ». Être consistant signifie donc qu’il n’existe aucune formule P telle que P et sa négation soient toutes deux dérivables. Cette condition est minimale pour qu’un système formel soit utile. Elle ne signifie pas que toutes les formules y sont décidables. Le premier théorème d’incomplétude de Gödel affirme qu’un système formel effectivement axiomatisé, consistant et assez puissant pour formaliser l’arithmétique contient des énoncés indécidables. Sous les hypothèses techniques du second théorème, un tel système ne peut pas démontrer l’énoncé arithmétisé Con(S) qui exprime sa propre consistance.

Quatre éléments permettent de poser la question de la consistance. Le langage fournit les formules et leur négation. Les axiomes sont les formules admises au départ. Les règles de dérivation autorisent le passage de formules déjà disponibles à de nouvelles formules. Les dérivations sont les suites d’étapes effectivement permises par ces règles.

Les axiomes ne produisent des conséquences qu’à travers les règles, et chaque dérivation dépend donc des deux. Le test de consistance porte sur le résultat : aucune dérivation ne doit mener à une formule tandis qu’une autre mène à sa négation. Le choix graphique des symboles ne définit pas la propriété ; ce sont les axiomes, les règles et les dérivations qu’ils autorisent qui comptent.

Considérons un système jouet S. Son langage est engendré par une formule P et la négation, de sorte qu’il contient notamment P, sa négation et leurs négations itérées. Son unique axiome est P, et il ne possède aucune règle permettant de produire une autre formule.

Données : la paire à tester est formée de P et « non-P » ; l’ensemble des axiomes contient seulement P ; aucune règle de dérivation n’est disponible.

1. Par son statut d’axiome, P est dérivable dans S.

2. Comme aucune règle ni aucun autre axiome ne fournit « non-P », cette négation n’est pas dérivable. Le système jouet est donc consistant.

3. Ajoutons maintenant « non-P » aux axiomes. P et sa négation sont alors dérivables immédiatement : le système modifié n’est pas consistant.

Le contrôle est refaisable en listant les formules dérivables avant et après l’ajout : la seconde liste contient la paire contradictoire, tandis que la première ne la contient pas.

Lorsqu’on étudie un système d’axiomes et de règles, on examine si une formule et sa négation peuvent toutes deux être dérivées. Si une telle paire apparaît, le système échoue au critère minimal de consistance.

Face à deux conclusions opposées, le geste utile consiste à remonter leurs dérivations : les axiomes et les règles employés indiquent où la contradiction est produite. Continuer à raisonner sans traiter cette contradiction ne rétablit pas la consistance.

Pour un système suffisamment expressif, l’indécidabilité d’un énoncé n’est pas un signal d’inconsistance. Les théorèmes de Gödel imposent précisément de séparer l’absence de contradiction de la capacité à décider chaque énoncé.

Consistance et complétude. La consistance interdit de dériver simultanément une formule et sa négation. La complétude demanderait que chaque énoncé pertinent puisse être décidé dans le système. Un système effectivement axiomatisé, consistant et assez puissant pour formaliser l’arithmétique contient des énoncés indécidables, comme l’établit le premier théorème d’incomplétude de Gödel.

Incapacité à prouver sa consistance et inconsistance. Sous les hypothèses techniques du second théorème de Gödel, un système effectivement axiomatisé, consistant et assez puissant pour formaliser l’arithmétique ne peut pas démontrer l’énoncé arithmétisé qui exprime sa propre consistance. Cette impossibilité ne fournit pas, à elle seule, une formule accompagnée de sa négation ; elle ne constitue donc pas une contradiction.

Une seule paire suffit. Même si de nombreuses dérivations ne posent aucun problème, l’existence d’une formule dérivable avec sa négation rend le système inconsistant. Il faut examiner les deux dérivations, pas compter les résultats sans contradiction.

Consistant ne signifie pas tout-puissant. Un énoncé indécidable n’est ni une contradiction ni une réponse cachée. Dans un système effectivement axiomatisé, consistant et assez puissant pour formaliser l’arithmétique, le premier théorème de Gödel garantit précisément l’existence de tels énoncés.

La preuve interne a une limite. Sous les hypothèses techniques du second théorème de Gödel, un système effectivement axiomatisé, consistant et assez puissant pour formaliser l’arithmétique ne peut pas démontrer l’énoncé arithmétisé qui exprime sa propre consistance. Il faut conserver cette restriction au lieu de transformer le théorème en affirmation générale sur tout système formel.

Les théorèmes d’incomplétude de Gödel — Pour approfondir le lien entre consistance, indécidabilité et impossibilité d’une preuve interne de consistance.

axiome — Pour préciser le rôle des énoncés de départ dans les dérivations d’un système formel.