RÉCURSIVITÉ, logique mathématique

Carte mentale

Élargissez votre recherche dans Universalis

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 :

dans laquelle le membre de droite est une formule du langage des anneaux, l'addition et la multiplication des entiers naturels étant définies par la restriction de l'addition et de la multiplication de Z aux éléments de Z vérifiant cette formule. On démontre ainsi de nombreux résultats : la théorie des relations binaires, la théorie des corps, la théorie des groupes, etc., sont indécidables (Par contre, la théorie des corps finis – c'est le théorème d'Ax et Kochen – et la théorie des groupes commutatifs sont des théories décidables.)

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 à des résultats difficiles d'algèbre, d'arithmét [...]


1  2  3  4  5
pour nos abonnés,
l’article se compose de 14 pages




Écrit par :

Classification


Autres références

«  RÉCURSIVITÉ, logique mathématique  » est également traité dans :

CHURCH ALONZO (1903-1995)

  • Écrit par 
  • Françoise ARMENGAUD
  •  • 611 mots

Mathématicien et logicien, philosophe et historien de la logique, Alonzo Church est né le 14 juin 1903 à Washington et mort le 11 août 1995 à Hudson (Ohio). Professeur de mathématiques à l'université de Princeton, directeur du Journal of Symbolic Logic , il est selon Kneale « le plus fidèle des disciples de Frege ». Réputé « platonisant », il défend une conception délibérément réaliste de la propo […] Lire la suite☛ http://www.universalis.fr/encyclopedie/alonzo-church/#i_82872

DÉMONSTRATION THÉORIE DE LA

  • Écrit par 
  • Jean-Yves GIRARD
  •  • 6 260 mots
  •  • 1 média

Dans le chapitre « La logique Π12 »  : […] L'extension des résultats obtenus par Takeuti, Pohlers, Buchholz... pour le schéma de compréhension Π 1 1 à des systèmes plus forts nécessite de remplacer la ω-logique par des logiques correspondant à de plus grandes complexités logiques, Π 2 1 et plus généralement Π 1 n . Le problème de la B -règle, posé par Mostowski est le suivant : Caractériser les énoncés qui sont vrais dans tout modèle da […] Lire la suite☛ http://www.universalis.fr/encyclopedie/theorie-de-la-demonstration/#i_82872

KLEENE STEPHEN COLE (1909-1994)

  • Écrit par 
  • Pierre GOUJON
  •  • 370 mots

Mathématicien américain né à Hartford (Connecticut). Diplômé de l'Amherst College, Stephen C. Kleene entre, en 1930, à l'université de Princeton. Il est docteur de la même université en 1934. Dès cette époque, il partage son temps entre l'enseignement (université du Wisconsin) et la recherche. Il est successivement membre du Conseil national de la recherche scientifique (1957), puis président de l […] Lire la suite☛ http://www.universalis.fr/encyclopedie/stephen-cole-kleene/#i_82872

POST EMIL LEON (1897-1954)

  • Écrit par 
  • Bernard JAULIN
  •  • 622 mots

Mathématicien américain né à Augustów (Pologne) et mort à New York. Arrivé aux États-Unis en 1904, Emil Post obtint son Ph.D. à l'université Columbia de New York en 1920. Il était membre de l'American Mathematical Society depuis 1918 et de l'Association for Symbolic Logic dès sa fondation en 1935. Sa thèse de doctorat, publiée en 1921, porte sur le calcul propositionnel de A. N. Whitehead et B. Ru […] Lire la suite☛ http://www.universalis.fr/encyclopedie/emil-leon-post/#i_82872

Voir aussi

Pour citer l’article

Kenneth Mc ALOON, Bernard JAULIN, Jean-Pierre RESSAYRE, « RÉCURSIVITÉ, logique mathématique », Encyclopædia Universalis [en ligne], consulté le 12 janvier 2020. URL : http://www.universalis.fr/encyclopedie/recursivite-logique-mathematique/