Πρώτο θεώρημα μη πληρότητας του Γκέντελ

Το πρώτο θεώρημα μη πληρότητας του Γκέντελ δηλώνει ότι:
Οποιαδήποτε αποτελεσματικά παραχθείσα θεωρία που είναι ικανή να εκφράσει τη στοιχειώδη αριθμητική δεν μπορεί να είναι και συνεπής και πλήρης.

Συγκεκριμένα, για κάθε συνεπή, αποτελεσματικά παραχθείσα τυπική θεωρία που αποδεικνύει συγκεκριμένες αλήθειες βασικής αριθμητικής, υπάρχει μία αριθμητική δήλωση η οποία είναι αληθής, αλλά δεν μπορεί να αποδειχθεί από τη θεωρία (Kleene 1967, p. 250).

Η αληθής δήλωση που δεν μπορεί να αποδειχθεί στην οποία αναφέρεται το θεώρημα συχνά αναφέρεται ως “η πρόταση Γκέντελ” της θεωρίας. Αυτή δεν είναι μοναδική. Υπάρχουν άπειρες δηλώσεις στη γλώσσα της θεωρίας οι οποίες έχουν την ιδιότητα ότι είναι αληθείς και δεν μπορούν να αποδειχθούν.

Για κάθε συνεπή τυπική θεωρία Θ που περιλαμβάνει αρκετές ιδιότητες της θεωρίας αριθμών, η αντίστοιχη πρόταση Γκέντελ G ισχυρίζεται: “Η G δεν μπορεί να αποδειχθεί ότι είναι αληθής μέσα στη θεωρία Θ”. Αν η G μπορούσε να αποδειχθεί μέσω των αξιωμάτων και των κανόνων συμπερασμού της Θ, τότε η Θ θα είχε ένα θεώρημα G, το οποίο αντίκειται στον εαυτό του, και άρα η θεωρία Θ θα ήταν ασυνεπής. Αυτό σημαίνει ότι αν η θεωρία Θ είναι συνεπής τότε η G δεν μπορεί να αποδειχθεί μέσα σ` αυτή. Αυτό σημαίνει ότι ο ισχυρισμός της G, ότι η ίδια δεν αποδεικνύεται, είναι σωστός. Υπό αυτήν την έννοια η G όχι μόνο δεν μπορεί να αποδειχθεί αλλά είναι και αληθής. Συνεπώς αποδεικνύεται-μέσα-στη-θεωρία-Θ και αλήθεια δεν είναι το ίδιο. Η θεωρία Θ δεν είναι πλήρης (είναι μη πλήρης).

Αν η G είναι αληθής τότε η G δεν μπορεί να αποδειχθεί μέσα στη θεωρία, και η θεωρία είναι μη πλήρης. Αν η G είναι ψευδής τότε η G μπορεί να αποδειχθεί μέσα στη θεωρία, και η θεωρία είναι ασυνεπής μιας και η G και αποδεικνύεται και αντικρούεται από την Θ.

Είναι δυνατόν να ορίσουμε μια μεγαλύτερη θεωρία Θ’ που να περιέχει όλη την Θ, συν την G ως πρόσθετο αξίωμα. Σε αυτήν την περίπτωση, η G είναι πράγματι θεώρημα στην Θ’(τετριμμένα, μιας και είναι αξίωμα). Παρόλα αυτά, αυτό το θεώρημα μη πληρότητας τότε εφαρμόζεται στην Θ’. Θα υπάρχει μια νέα πρόταση Γκέντελ G’ για την Θ’, που θα δείχνει ότι η Θ’ είναι επίσης μη πλήρης. Κάθε θεωρία έχει τη δική της πρόταση Γκέντελ.

Για να αποδείξει το πρώτο θεώρημα μη πληρότητας, ο Γκέντελ απαρίθμησε τις προτάσεις της θεωρίας: Σε κάθε πρόταση αντιστοίχισε έναν αριθμό. Σε αυτές τις προτάσεις συμπεριέλαβε και δηλώσεις πάνω στις ίδιες τις προτάσεις, οι οποίες θα πρέπει να είναι είτε αληθείς είτε ψευδείς. Θεώρησε την πρόταση “η πρόταση με τον αριθμό x δεν μπορεί να αποδειχτεί”. Κατόπιν έδειξε ότι υπάρχει μια αντιστοίχιση, τέτοια ώστε η παραπάνω πρόταση να έχει τον αριθμό x. Έτσι η πρόταση παίρνει τη μορφή: “Η παρούσα πρόταση δεν μπορεί να αποδειχτεί”. Αν είναι αληθής, τότε υπάρχει μια πρόταση στη θεωρία που δεν είναι αποδείξιμη και επομένως η θεωρία δεν είναι πλήρης. Αν είναι ψευδής, τότε η συγκεκριμένη πρόταση μπορεί να αποδειχτεί. Μια θεωρία όμως μέσα στην οποία μπορεί να αποδειχτεί μια λάθος πρόταση είναι αντιφατική και άρα ασυνεπής.

Πηγή: wikipedia