4. Indécidabilité et décidabilité
L'étude de l'indécidabilité des théories mathématiques relève de la théorie des fonctions récursives en deux sens : en premier lieu, car un résultat d'indécidabilité signifie qu'une certaine fonction, à savoir la fonction caractéristique de l'ensemble des théorèmes (modulo une bonne numération des formules du langage de la théorie), n'est pas récursive, et, en second lieu, car l'indécidabilité d'une théorie mathématique se démontre la plupart du temps en utilisant le théorème de transfert de A. Tarski qui utilise essentiellement le premier théorème de Gödel suivant lequel la théorie T1 introduite au chapitre 2 est essentiellement indécidable. Pour qu'une théorie mathématique T dans un langage L soit indécidable, il suffit en effet de trouver un modèle M de T dans lequel on puisse « définir » (en un sens à préciser) un modèle (en général la structure standard <N, +, x> de l'arithmétique) d'une théorie essentiellement indécidable (principalement T1). Ainsi, par exemple, la théorie des anneaux euclidiens, factoriels, commutatifs... est indécidable car, dans l'anneau Z, on peut définir (dans le langage des anneaux) la structure N. En effet, d'après le théorème de Lagrange suivant lequel tout nombre positif est somme de quatre carrés, on a, dans Z, l'équivalence :
Les techniques utilisées pour démontrer la décidabilité d'une théorie mathématique ne relèvent pas, de la théorie des fonctions récursives et font appel en général à […]
… pour nos abonnés, l'article se prolonge sur 13 pages…
