W dalszym ciągu będą nas interesować wyłącznie predykaty jednoargumentowe. Oznaczmy listę wszystkich takich predykatów jako
Rozważmy teraz wyrażenie „zdanie o numerze n zastosowane na argumencie n nie posiada dowodu”:
Powstał pewien jednoargumentowy predykat. Każdy taki predykat ma swój numer w przyporządkowaniu Oznaczmy ten numer przez
czyli
Rozważmy teraz właśnie ten predykat zastosowany na liczbie d: Z definicji powyżej mamy:
czyli
Zdanie jest zwane zdaniem Gödla i jest równoważne stwierdzeniu, że ono samo nie posiada dowodu. Czy zdanie to jest prawdziwe, czy fałszywe? Jeżeli jest prawdziwe, to prawdą jest także, że nie posiada ono dowodu, co oznacza, że nasz system formalny jest niezupełny. Jeżeli jest fałszywe, to istnieje jego dowód, co oznacza, że system formalny jest sprzeczny.
Zatem systemy formalne spełniające pewne założenia zawsze muszą być albo zupełne albo niesprzeczne i nigdy nie posiadają obu tych własności jednocześnie.
Wnioski Obydwa twierdzenia Gödla można uogólnić na dowolne systemy formalne zawierające skończoną lub rekurencyjnie przeliczalną liczbę aksjomatów. Warunkiem jest, aby w skład takiego systemu wchodziła arytmetyka liczb naturalnych lub zawierał on skończoną liczbę aksjomatów umożliwiającą przeprowadzenie tzw.