Teorema d'incompletesa de Gödel: diferència entre les revisions
Contingut suprimit Contingut afegit
m →Relació amb la computabilitat: mecanografia |
m Corregit: tal i com -> tal com |
||
Línia 63:
És de notar que els teoremes de Gödel només són aplicables a sistemes axiomàtics ''suficientment forts''. Aquest terme significa que la teoria conté la suficient aritmètica per portar a terme les instruccions de codificació requerides per la prova del primer teorema d'incompletesa. Essencialment, tot el que se li exigeix són alguns fets bàsics sobre l'addicció i la multiplicació tal com per exemple es formalitzen en l'[[aritmètica Q de Robinson]]. Hi ha sistemes axiomàtics inclús més dèbils que són consistents i complets, com per exemple l'[[aritmètica de Presburger]] que demostra totes les afirmacions de primer ordre certes aplicant només la suma.
Els sistemes axiomàtics poden consistir en un nombre infinit d'axiomes (tal
Un altre exemple d'una especificació d'una teoria en la que el primer teorema de Gödel no és aplicable es pot construir de la següent manera: ordenem totes les possibles declaracions sobre els nombres naturals, primer per la seva longitud i després en [[ordre lexicogràfic]]; comencem amb un sistema axiomàtic inicialment igual als axiomes de Peano, repassem la llista de declaracions una a una, i, si la declaració actual no es pot demostrar ni refutar a partir de l'actual sistema d'axiomes, llavors l'afegim a la llista. Això crea un sistema que és complet, consistent i suficientment potent, però no és [[conjunt recursivament enumerable|recursivament enumerable]].
|