Teoria jest zupełna, jeśli dla każdej formuły w jej języku przynajmniej jedna z formuł lub jest logiczną konsekwencją danej teorii.
Arytmetyka Presburgera jest układem aksjomatycznym liczb naturalnych z dodawaniem, który jest zarówno niesprzeczny, jak i zupełny.
Twierdzenie Gödla o niezupełności pokazuje, że żadna dostatecznie silna efektywna teoria arytmetyki nie może być jednocześnie zupełna i niesprzeczna. Twierdzenie Gödla obejmuje arytmetykę Peana (PA) i prostą arytmetykę rekurencyjną (PRA), lecz nie arytmetykę Presburgera.
Ponadto drugie twierdzenie Gödla o niezupełności pokazuje, że dostatecznie silna efektywna teoria arytmetyki jest niesprzeczna wtedy i tylko wtedy, gdy nie ma w niej dowodu dla specyficznego zdania, zwanego zdaniem Gödla danej teorii. Zdanie to jest sformalizowanym stwierdzeniem, iż dana teoria jest rzeczywiście niesprzeczna. Tak więc niesprzeczność dostatecznie bogatej, efektywnej, niesprzecznej teorii arytmetyki nigdy nie może zostać udowodniona w ramach takiej teorii. Ten sam wynik zachodzi dla efektywnych teorii obejmujących dostatecznie bogaty fragment arytmetyki – włącznie z takimi teoriami jak teoria mnogości Zermela-Fraenkla. W tych teoriach mnogości nie można wykazać prawdziwości ich wyrażeń Gödla, nawet zakładając ich niesprzeczność.
Zobacz też Jan Łukasiewicz problemy Hilberta
Bibliografia
Kategoria:Logika matematyczna Kategoria:Problemy Hilberta