Axiomatisable

Définition

DÉMONSTRATION THÉORIE DE LA
- Écrit par Jean-Yves GIRARD
- 33 765 mots
- 1 média
Soit AP l'arithmétique de Peano de premier ordre, T un sous-système finiment axiomatisable de AP et A un énoncé arbitraire à une variable libre x ; soit enfin ThmT (⌈A⌉) l'énoncé de AP qui exprime que A est démontrable dans T. On a :Pour la démonstration, on se ramène au cas où T est le calcul des prédicats ; il s'agit de montrer, par induction sur une démonstration, que tout énoncé démontrable est vrai ; or, c'est un résultat bien connu de Tarski, il n'y a pas de prédicat de vérité pour les énoncés de AP défini dans AP elle-même.
RÉCURSIVITÉ, logique mathématique
- Écrit par Kenneth Mc ALOON, Bernard JAULIN, Jean-Pierre RESSAYRE
- 49 023 mots
La seconde partie de ce théorème dit que la théorie T1 est essentiellement indécidable, c'est-à-dire que toute théorie récursivement axiomatisable T qui contient T1 n'est pas récursive ; plus précisément, l'ensemble des théorèmes de T n'est pas récursif, à une bonne numérotation près des formules. Cela résulte du fait que les sous-ensembles de N fortement représentables dans T1 sont les ensembles récursifs – on dit que X ⊂ N est fortement représentable s'il existe une formule F(x) à une variable libre telle que : Une seconde illustration des notions introduites ci-dessus est une forme du second théorème d'incomplétude de Gödel (cf.