indécidabilité

Cet article est extrait de l'ouvrage Larousse « Dictionnaire de la philosophie ».

Logique, Mathématiques

Propriété d'une proposition qui n'est pas démontrable et dont la négation n'est pas démontrable non plus. Inversement, une proposition est décidable si elle-même ou sa négation est démontrable. La notion s'applique aussi à une théorie pour laquelle il n'existe pas de procédure automatique permettant de démontrer ou de réfuter chacune des propositions formulables dans le langage de cette théorie.

La notion de décidabilité / indécidabilité est relative. Cela veut dire qu'une proposition indécidable dans une théorie T₁ peut être décidable dans une théorie T₂. Cependant, si une proposition P demeure indécidable dans toute extension convenable de T₁, alors on dit qu'elle est « essentiellement indécidable ». La notion de décidabilité / indécidabilité est, de plus, méta-théorique dans la mesure où elle décrit une propriété d'une proposition P dans un langage L₂ qui ne se confond pas avec le langage L₁ de la théorie T₁ où est écrite P. Par exemple, la célèbre proposition de Fermat s'écrit dans le langage algébrique : xⁿ + yⁿ = zⁿ, où x, y, z et n désignent des nombres entiers. Fermat a conjecturé que pour n = 3 cette équation est insoluble. Conjecture récemment confirmée. L'insolubilité de l'équation xⁿ + yⁿ = zⁿ ayant été démontrée, on peut dire (dans le métalangage, qui est ici le langage courant) que la proposition de Fermât est décidable.

Un célèbre exemple de proposition indécidable est celle de Gödel, écrite dans le langage de l'arithmétique du premier ordre et qui n'est dans ce langage ni démontrable ni réfutable. Un exemple classique de théorie décidable est constitué par le calcul des propositions, la procédure de décision étant constituée par la méthode des tables de vérité. Au contraire, le calcul des prédicats du premier ordre est indécidable, comme A. Church et A. Turing l'ont démontré en 1936.

L'existence de propositions indécidables a ruiné la croyance en la résolubilité de principe de tout problème mathématiquement formulé. Elle a également conduit à remettre en cause la validité universelle du principe logique du tiers exclu. Selon ce principe, il n'y a que deux valeurs de vérité, qui s'excluent mutuellement, le vrai et le faux. Mais on peut imaginer des systèmes logiques où aux valeurs « vrai » et « faux » s'ajoute la valeur « indéterminé » (ni vrai ni faux), ce qui est le cas de la logique trivalente de Lukasiewicz (1878-1956) et de la logique intuitionniste de Brouwer (1881-1966) et Heyting (1898-1980). On peut aussi imaginer des logiques avec une infinité de valeurs de vérité comparable à l'infinité des nombres réels compris entre 0 et 1 (logiques floues).

Hourya Sinaceur

→ incomplétude, langage, proposition, théorie