Teorema d'incompletesa de Gödel: diferència entre les revisions

El treball combinat de Gödel i [[Paul Cohen]] ha donat a conèixer exemples concrets d'afirmacions indecidibles: tant els [[axioma d'elecció|axiomes d'elecció]] com la [[hipòtesi del continu]] són indecidibles en l'axiomatització estàndard de [[teoria de conjunts]]. Aquests resultats no requereixen el teorema d'incompletesa.

 

 

Al [[1973]], es va demostrar que el [[problema de Whitehead]] en [[teoria de grups]] és indecidible en la teoria estàndard de grups. El [[1977]], Kirby, Paris i Harrington demostraren que una afirmació en [[combinatòria]], una versió del [[teorema de Ramsey]], és indecidible en l'axiomatització de l'aritmètica donada pels [[axiomes de Peano]], però es pot demostrar certa en el sistema més ampli que és la teoria de conjunts. L'[[algorisme de Kruskal]], que té implicacions en informàtica, també és indecidible a partir dels axiomes de Peano però demostrable en teoria de conjunts. Així mateix, el [[teorema de Goodstein]] és una afirmació relativament simple sobre els nombres naturals que és indecidible en l'aritmètica de Peano.