Θεωρήματα μη πληρότητας του Γκέντελ

Στη μαθηματική λογική, τα θεωρήματα μη πληρότητας του Γκέντελ, τα οποία αποδείχτηκαν από τον Κουρτ Γκέντελ (Kurt Gödel) το 1931, είναι δύο θεωρήματα που υποδεικνύουν έμφυτους περιορισμούς σε όλα τα (πλην των τετριμμένων) τυπικά συστήματα των μαθηματικών. Τα θεωρήματα είναι πολύ σημαντικά για τη φιλοσοφία των μαθηματικών. Ερμηνεύονται γενικά ως μια απόδειξη πως το πρόγραμμα του Χίλμπερτ να βρεθεί ένα πλήρες και συνεπές σύνολο από αξιώματα για όλα τα μαθηματικά είναι αδύνατο, δίνοντας έτσι αρνητική απάντηση στο δεύτερο πρόβλημα του Χίλμπερτ.

Υπόβαθρο

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

Επειδή οι δηλώσεις μιας τυπικής θεωρίας γράφονται σε συμβολική μορφή, είναι δυνατόν να επαληθευτεί μηχανικά ότι μία τυπική απόδειξη από ένα πεπερασμένο σύνολο από αξιώματα είναι έγκυρη. Αυτή η δουλειά, γνωστή ως αυτοματοποιημένη επαλήθευση αποδείξεων, σχετίζεται στενά με την αυτοματοποιημένη απόδειξη θεωρημάτων. Η διαφορά είναι ότι αντί να κατασκευάσει μια νέα απόδειξη, ο επαληθευτής αποδείξεων απλά ελέγχει αν μια δεδομένη τυπική απόδειξη (ή, σε μερικές περιπτώσεις, οι οδηγίες που μπορεί να ακολουθήσει κανείς για να δημιουργήσει μια τυπική απόδειξη) είναι σωστή. Αυτό δεν είναι απλά και μόνο υποθετικό. Συστήματα όπως το Isabelle χρησιμοποιούνται σήμερα για να τυποποιούν αποδείξεις και μετά να ελέγχουν την εγκυρότητά τους.

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

Μια τυπική θεωρία λέγεται πως είναι αποτελεσματικά παραχθείσα αν το σύνολο των αξιωμάτων της είναι ένα αναδρομικά απαριθμήσιμο σύνολο. Αυτό σημαίνει ότι υπάρχει ένα πρόγραμμα υπολογιστή που, κατ` αρχήν, θα μπορούσε να απαριθμήσει όλα τα αξιώματα της θεωρίας χωρίς να συμπεριλάβει στη λίστα καμία δήλωση που δεν είναι αξίωμα. Αυτό είναι ισοδύναμο με την ικανότητα να απαριθμήσει όλα τα θεωρήματα της θεωρίας χωρίς να απαριθμήσει καμία δήλωση που δεν είναι θεώρημα. Για παράδειγμα, η θεωρία της αριθμητικής του Πεάνο (η αξιωματική περιγραφή των φυσικών αριθμών) και η θεωρία συνόλων των Τσερμέλο-Φρένκελ έχουν άπειρο αριθμό αξιωμάτων η κάθε μια, και κάθε μια είναι αποτελεσματικά παραχθείσα.

Κατά την επιλογή ενός συνόλου από αξιώματα, ο στόχος είναι με βάση αυτά να μπορεί να αποδείξει κανείς όσο το δυνατόν περισσότερα σωστά αποτελέσματα, χωρίς να μπορεί να αποδείξει κανένα λανθασμένο αποτέλεσμα. Ένα σύνολο από αξιώματα είναι πλήρες αν, για κάθε δήλωση στη γλώσσα των αξιωμάτων, είτε η αυτή δήλωση είτε η άρνησή της μπορεί να αποδειχτεί από τα αξιώματα. Ένα σύνολο αξιωμάτων είναι (απλά) συνεπές αν δεν υπάρχει δήλωση τέτοια ώστε και αυτή και η άρνηση της να μπορούν να αποδειχτούν από τα αξιώματα. Στο πρότυπο σύστημα της λογικής πρώτου βαθμού ένα συνεπές σύνολο αξιωμάτων θα αποδείξει κάθε δήλωση στη γλώσσα της (αυτό μερικές φορές καλείται η αρχή της έκρηξης) και είναι επομένως αυτόματα πλήρες. Ένα σύνολο από αξιώματα που είναι και πλήρες και συνεπές, παρ'όλα αυτά, αποδεικνύει ένα μέγιστο σύνολο από μη-αντιφατικά θεωρήματα. Τα θεωρήματα μη πληρότητας του Γκέντελ δείχνουν ότι σε συγκεκριμένες περιπτώσεις δεν είναι δυνατόν να έχουμε μια αποτελεσματικά παραχθείσα, πλήρη και συνεπή θεωρία.

Πρώτο θεώρημα μη πληρότητας

Το πρώτο θεώρημα μη πληρότητας του Γκέντελ δηλώνει ότι:

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

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

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

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

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

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

Δεύτερο θεώρημα μη πληρότητας

Το δεύτερο θεώρημα μη πληρότητας Γκέντελ μπορεί να διατυπωθεί ως εξής:

Για κάθε αποτελεσματικά παραχθείσα τυπική θεωρία Θ που συμπεριλαμβάνει βασικές αριθμητικές αλήθειες και επίσης συγκεκριμένες αλήθειες για την δυνατότητα τυπικής απόδειξης, η Θ συμπεριλαμβάνει δήλωση περί της ιδίας συνέπειας αν και μόνο αν η Θ είναι ασυνεπής.

Αυτό ενισχύει το πρώτο θεώρημα μη πληρότητας, επειδή η δήλωση που κατασκευάσαμε στο πρώτο θεώρημα μη πληρότητας δεν εκφράζει ευθέως την συνέπεια της θεωρίας. Η απόδειξη του δεύτερου θεωρήματος μη πληρότητας λαμβάνεται, ουσιαστικά, τυπικοποιώντας την απόδειξη του πρώτου θεωρήματος μη πληρότητας μέσα στην ίδια την θεωρία.

Μια τεχνική λεπτομέρεια στο δεύτερο θεώρημα μη πληρότητας είναι πως να εκφράσουμε την συνέπεια της Θ ως φόρμουλα στην γλώσσα της Θ. Υπάρχουν πολλοί τρόποι να το κάνουμε, και δεν οδηγούν όλοι στο ίδιο αποτέλεσμα. Συγκεκριμένα, διαφορετικές τυπικοποιήσεις της αξίωσης ότι η Θ είναι συνεπής μπορεί να είναι ή να μην είναι ισοδύναμες στην Θ, και μερικές μπορεί ακόμα και να μπορούν να αποδειχθούν. Για παράδειγμα, η πρώτου βαθμού αριθμητική του Πεάνο (PA: Peano arithmetic) μπορεί να αποδείξει ότι το μεγαλύτερο συνεπές υποσύνολο της PA είναι συνεπές. Αλλά μιας και η PA είναι συνεπής, το μεγαλύτερο συνεπές υποσύνολο της PA είναι απλά η PA, οπότε υπό αυτή την έννοια η PA "αποδεικνύει ότι είναι συνεπής". Αυτό που η PA δεν αποδεικνύει είναι πως το μεγαλύτερο συνεπές υποσύνολο της PA είναι, στην πραγματικότητα, ολόκληρη η PA. (Ο όρος "μεγαλύτερο συνεπές υποσύνολο της PA" είναι μάλλον ασαφής, αλλά αυτό που εννοούμε εδώ είναι το μεγαλύτερο συνεπές αρχικό κομμάτι των αξιωμάτων της PA ταξινομημένο σύμφωνα με κάποια κριτήρια. Για παράδειγμα, με τους "αριθμούς Γκέντελ", τους αριθμούς που κωδικοποιούν τα αξιώματα όπως στο σχήμα που χρησιμοποίησε ο Γκέντελ που αναφέρθηκε παραπάνω).

Περιορισμοί των θεωρημάτων του Γκέντελ

Τα συμπεράσματα των θεωρημάτων του Γκέντελ ισχύουν μόνο για τις τυπικές θεωρίες που ικανοποιούν τις απαραίτητες υποθέσεις. Δεν ικανοποιούν όλα τα αξιωματικά συστήματα αυτές τις υποθέσεις, ακόμα και όταν αυτά τα συστήματα έχουν μοντέλα που συμπεριλαμβάνουν τους φυσικούς αριθμούς ως υποσύνολο. Για παράδειγμα, υπάρχουν πρώτου βαθμού αξιωματικοποιήσεις της Ευκλείδειας γεωμετρίας και των πραγματικών κλειστών πεδίων που δεν ικανοποιούν τις υποθέσεις των θεωρημάτων του Γκέντελ. Το γεγονός κλειδί είναι ότι αυτές οι αξιωματικοποιήσεις δεν είναι αρκετά εκφραστικές ώστε να ορίσουν το σύνολο των φυσικών αριθμών ή να αναπτύξουν βασικές ιδιότητες των φυσικών αριθμών.

Σχέση με την υπολογισιμότητα

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

Ο Στίβεν Κλέινι (Stephen Cole Kleene) (1943) παρουσίασε μία απόδειξη του θεωρήματος μη πληρότητας του Γκέντελ χρησιμοποιώντας βασικά αποτελέσματα της θεωρίας υπολογισμού. Ένα τέτοιο αποτέλεσμα δείχνει ότι το πρόβλημα τερματισμού δεν έχει λύση: δεν υπάρχει πρόγραμμα υπολογιστή που δοθέντος ενός προγράμματος Π ως είσοδο, να μπορεί να αποφασίσει σωστά αν το Π τελικά σταματά όταν τρέξει χωρίς είσοδο. Ο Κλιν έδειξε ότι η ύπαρξη μιας πλήρους, αποτελεσματικής θεωρίας της αριθμητικής με συγκεκριμένες ιδιότητες συνέπειας θα σήμαινε πως το πρόβλημα του τερματισμού είναι αποφασίσιμο (υπολογίσιμο), μια αντίφαση. Η μη-υπολογισιμότητα μπορεί επομένως να περιγραφεί ως συνέπεια της μη πληρότητας του Γκέντελ.

Εξωτερικοί σύνδεσμοι

• Stanford Encyclopedia of Philosophy: "Kurt Gödel" -- by Juliette Kennedy.
• Βιογραφίες:
  • Kurt Gödel. Αρχειοθετήθηκε 2005-10-13 στο Wayback Machine.
  • Gerhard Gentzen. Αρχειοθετήθηκε 2012-10-19 στο Wayback Machine.
  • What is Mathematics:Gödel's Theorem and Around by Karlis Podnieks. An online free book.