Όταν ο Kurt Gödel δημοσίευσε τα διάσημα θεωρήματά του για την έλλειψη πληρότητας το 1931, συγκλόνισε τα θεμέλια της μαθηματικής λογικής: αντέκρουσε ότι όλα τα αξιώματα που μπορούν να δημιουργηθούν ως πιθανή βάση είναι αναπόφευκτα ελλιπή για να αποδείξουν όλες τις δηλώσεις σχετικά με τους αριθμούς - και το κατέστρεψαν Το όνειρο του Χίλμπερτ να αποδείξει τη συνέπεια της μαθηματικής θεωρίας.
Η εισαγωγή των αριθμών Gödel (η μοναδική χαρτογράφηση των τύπων σε φυσικούς αριθμούς) και η διαγώνια (η αντικατάσταση της ελεύθερης μεταβλητής σε συναρτήσεις με τον αντίστοιχο αριθμό Gödel) είναι δύο κεντρικές έννοιες που ο Gödel εισάγει στην απόδειξη του. Η αποφασιστική απόδειξη στην οποία ο Gödel συνδυάζει αυτές τις έννοιες μπορεί να καταγραφεί ως εξής:
$$P(p) \, \text{wahr} \Leftrightarrow p \in \, \overline{B}^* \Leftrightarrow d(p) \in \overline{B} \Leftrightarrow d(p) \notin B \Leftrightarrow g(P(p)) \notin B \Leftrightarrow P(p) \, \text{unbeweisbar}$$
Δεδομένου ότι το \(P(p)\) δεν μπορεί να είναι ψευδές (δεδομένου ότι διαφορετικά θα ήταν αποδείξιμο και επομένως αληθινό), \(P(p)\) αληθές και επομένως να μην είναι αποδεικτικό. Έτσι υπάρχει πάντα μια αληθινή πρόταση σε μια γλώσσα (με οποιαδήποτε επιλογή αξιώματος) που δεν μπορεί να αποδειχθεί. Εδώ \(g\) το Gödelization, \(p\) ο αριθμός Gödel του predikat \(P\) , που είναι το συμπληρωματικό αρχέτυπο \(\overline{B}^*\) του \(B\) (το σύνολο όλων Οι αριθμοί Godel όλων των αποδεδειγμένων προτάσεων) κάτω από τη διαγώνια συνάρτηση \(d\) .
Για περαιτέρω ανάγνωση προτείνουμε τη δημοσίευση του Gödel το 1931 και το καλά διαβαμένο άρθρο του Stepan Parunashvili . Εκτός από τα θεωρήματα της ατελούς εκτέλεσης, ο Gödel πέτυχε και άλλα πρωτοποριακά επιτεύγματα, συμπεριλαμβανομένης της αδιαμφισβήτητης διαδοχικής υπόθεσης του Cantor και της οντολογικής απόδειξης του Θεού στη γλώσσα της τροπικής λογικής.