Αυτό θα είναι μάλλον το τελευταίο μου post για το 2009 και το θέμα του αφορά ένα από τα ενδιαφέροντά μου που δυστυχώς δεν αφιερώνω αρκετό χρόνο. Η αφορμή είναι το ότι διάβασα αυτές τις ημέρες το
Logicomix του
Απόστολου Δοξιάδη και το κομμάτι που αφορά αυτό το post έχει να κάνει με την λογική και όχι το κόμιξ (αν και είναι και αυτό ένα από τα ενδιαφέροντά μου).
Λοιπόν, για όσους δεν το έχουν υπόψη τους, το Logicomix πραγματεύεται υπό μία έννοια την ιστορία των θεμελίων (ή αλλιώς, της αυστηρής θεμελίωσης) των μαθηματικών, μέσα από την ζωή του
Bertrand Russell. Και είναι σε μορφή κόμιξ. Φυσικά η ιστορία είναι ένα μυθιστόρημα που απλά έχει ως πρωταγωνιστές πραγματικά πρόσωπα (και ιδέες) και δεν έχει πρόθεση να αποτελέσει μια ακριβής καταγραφή των γεγονότων, όπως επισημαίνουν και οι δημιουργοί. Για την υλοποίηση της ιδέας συνεργάστηκαν με τον Δοξιάδη, ο
Χρίστος Παπαδημητρίου (στην συγγραφή της ιστορίας), ο Αλέκος Παπαδάτος και η Annie Di Donna (στο σχέδιο). Να πω λοιπόν από την αρχή, ότι μου άρεσε πολύ τόσο η ιδέα όσο και η υλοποίηση και νομίζω ότι θα ανακινήσει το ενδιαφέρον για την λογική και τα μαθηματικά σε όποιον το διαβάσει.
Πρέπει να πω ακόμα ότι η εικόνα που είχα από τον Δοξιάδη ερχόταν αποκλειστικά και μόνο από την
«17η Νύχτα» (δεν έχω διαβάσει τον θείο Πέτρο), ένα θεατρικό σχετικά με την λογική και τις τελευταίες μέρες της ζωής του
Kurt Godel, ο οποίος πέθανε στο νοσοκομείο από ασιτία επειδή αρνιόταν να φαει φαγητό από τον φόβο ότι θέλανε να τον δηλητηριάσουν. Η εικόνα που είχα λοιπόν από αυτό το θεατρικό ήταν τραγική. Επειδή είχα δει την παράσταση, πιθανόν να έφταιγε και η σκηνοθετική ματιά του Αντώνη Καφετζόπουλου, αλλά όπως και να έχει η σύνδεση της ιστορίας με την λογική και τα θεωρήματα της μη πληρότητας του Godel ήταν πολύ κακή, θα έλεγα αποτυχημένη, για να μην πω για την καρικατουρίστικη εμφάνιση του
Hilbert σε κάποια σημεία του έργου που απλά γελοιοποιούσε το όλο θέμα.
Anyway, το κόμιξ μου άρεσε γενικά και το συνιστώ και από όσο μπόρεσα να αντιληφθώ, είναι γενικά αρκετά ακριβές στην παρουσίαση των μαθηματικών ιδεών, χωρίς όμως να γίνεται βαρύ.
Ακόμα, στο τέλος του βιβλίου, υπάρχει και ένα παράρτημα όπου ξεκαθαρίζονται διάφορες μαθηματικές έννοιες και δίνονται βιογραφικά στοιχεία για τους βασικούς ήρωες της ιστορίας. Εκεί είναι που υπάρχει και το πρόβλημα. Και το πρόβλημα αφορά το θεώρημα πληρότητας του Godel (
Godels completeness theorem), τα θεωρήματα μη πληρότητας (Godels first and second
incompleteness theorems), την λογική πρώτης βαθμίδας (
first order logic) και τη λογική δεύτερης βαθμίδας (
second order logic). Συγκεκριμένα, αυτό που μου χτύπησε στο μάτι ήταν η διατύπωση ότι η λογική πρώτης βαθμίδας και τα συστήματα που βασίζονται σ’ αυτήν είναι, σύμφωνα με το θεώρημα πληρότητας του Godel, πλήρη.
Και για να είμαι πιο συγκεκριμένος, η ακριβής διατύπωση είναι:
Γκέντελ, Κουρτ... Στη διδακτορική του διατριβή έκανε ένα σημαντικό βήμα προς την εκπλήρωση του «Προγράμματος του Χίλμπερτ», αποδεικνύοντας το θεώρημα της πληρότητας, που ορίζει ότι όλες οι αληθείς προτάσεις στη λογική πρώτης βαθμίδας – δηλαδή του απλού κατηγορηματικού λογισμού τύπου Φρεγκέ – μπορούν να αποδειχθούν από ένα μικρό σύνολο αξιωμάτων. Το 1931 όμως κατάφερε να αποδείξει ότι το ίδιο δεν ισχύει για την λογική δεύτερης βαθμίδας, δηλαδή για μια λογική αρκετά ισχυρή να στηρίξει τα θεμέλια της αριθμητικής, ή άλλων αντίστοιχων ή πιο σύνθετων μαθηματικών θεωριών. Τα δύο θεωρήματα που καταγράφουν αυτή τη διαπίστωση ονομάζονται της μη πληρότητας...
Μη πληρότητα... Η πληρότητα ενός λογικού συστήματος είναι η ιδιότητα βάση της οποίας μια ορθά διατυπωμένη ή γραμματικά ορθή πρότασή του (που είναι δηλαδή γραμμένη σύμφωνα με τους «γραμματικούς» κανόνες του συστήματος) μπορεί να αποδειχθεί, αυτή ή – αν είναι ψευδής – η αντίθετή της, από τα αξιώματα του συστήματος. Το θεώρημα της πληρότητας του Γκέντελ αποδεικνύει αυτή την ιδιότητα για το σύστημα της λογικής πρώτης βαθμίδας, δηλαδή τον κατηγορηματικό λογισμό στην μορφή που αυτός αναπτύχθηκε αρχικά από τον Φρεγκέ, στην Εννοιολογική Γραφή. Όμως, στο επίκεντρο του λεγόμενου «Προγράμματος του Χίλμπερτ» βρισκόταν η απόδειξη της πληρότητας της λογικής δεύτερης βαθμίδας (όπου οι λογικές μεταβλητές μπορούν να παίρνουν ως τιμές τους σύνολα), καθώς μόνο αυτή είναι επαρκής για να στηρίξει τα θεμέλια της αριθμητικής, ή και πιο σύνθετων κλάδων των μαθηματικών. Εντελώς αντίθετα με τις προσδοκίες και τα όνειρα της μαθηματικής κοινότητας, ο Γκέντελ απέδειξε... ότι οποιοδήποτε αξιωματικό σύστημα για την αριθμητική βασισμένο στις αρχές των Πρινκίπια θα ήταν αναγκαστικά μη πλήρες. Πιο συγκεκριμένα, το πρώτο από τα δύο θεωρήματα της μη πληρότητας ορίζει ότι σε οιοδήποτε σύστημα επαρκές να ορίσει τις ιδιότητες των ακεραίων αριθμών και τις αριθμητικές πράξεις, θα υπάρχουν πάντα τυπικά ορθές και επιπλέον αληθείς προτάσεις που δεν μπορούν να αποδειχθούν (αυτές ή, αν είναι ψευδείς, οι αντίθετές τους) μέσα στο σύστημα. Το δεύτερο θεώρημα λέει ότι αν ένα σύστημα τέτοιου τύπου είναι πλήρες, δεν μπορεί να αποδειχθεί μέσα στο σύστημα η συνέπειά του – με άλλα λόγια, ότι συνέπεια και πληρότητα δεν μπορούν να αποδειχθούν ταυτόχρονα σε ένα σύστημα της δεύτερης βαθμίδας.
Αυτό που φαίνεται από τα παραπάνω, όπως το αντιλαμβάνομαι εγώ, είναι ότι υπάρχει μια ασάφεια και μία σύγχυση (τουλάχιστον στη διατύπωση) σχετικά με την πληρότητα της λογικής πρώτης βαθμίδας, το κατά πόσο αυτή μπορεί να στηρίξει την αριθμητική και γενικότερα τι σημαίνει η πληρότητα ενός συστήματος σε σχέση με το θεώρημα της πληρότητας του Godel έναντι των δύο θεωρημάτων του της μη πληρότητας. Αυτή η σύγχυση μάλιστα, φαίνετε να υπάρχει γενικά στην βιβλιογραφία, αλλά και σε πολλές αναφορές και επικλήσεις των θεωρημάτων του Godel που γίνονται συχνά σε συζητήσεις. Μάλιστα, υπάρχει και ένα σχετικό βιβλίο, το οποίο έχει πολύ ενδιαφέρον και στο οποίο θα βασιστώ κατά κύριο λόγο. Το βιβλίο είναι το «Godel’s Theorem: An incomplete Guide to Its Use and Abuse», του
Torkel Franzen (όποιος ενδιαφέρεται, μπορεί να διαβάσει και αυτό το άρθρο:
«The Popular Impact of Gödel's Incompleteness Theorem»).
Το πρώτο ζήτημα λοιπόν, είναι το ζήτημα της πληρότητας της λογικής πρώτης βαθμίδας και του σχετικού θεωρήματος του Godel. Καταρχήν πρέπει να ξεκαθαρίσουμε τις έννοιες της «λογικής πρώτης βαθμίδας», του «Αξιωματικού Συστήματος», της «πληρότητας» όπως αυτή εννοείται στα πλαίσια του θεωρήματος της πληρότητας του Godel και της «πληρότητας» όπως αυτή εννοείται στα πλαίσια των θεωρημάτων της μη πληρότητας του Godel. Μετά θα συζητήσουμε και το θέμα της λογικής πρώτης και δεύτερης βαθμίδας και της αριθμητικής. Όπως φαίνετε από την προηγούμενη πρόταση πάντως, η σύγχυση πρέπει να οφείλεται στην συστηματική αναφορά στον όρο «πληρότητα».
Την λογική πρώτης βαθμίδας λοιπόν την παρουσιάζει αρκετά καλά το λήμμα
Κατηγορηματικός λογισμός, όπου λέει ουσιαστικά ότι είναι ένα σύνολο από κανόνες με την βοήθεια των οποίων μπορούμε να βγάλουμε λογικά συμπεράσματα και οι οποίοι έχουν μια τυποποιημένη μορφή στη μαθηματική γλώσσα, ενώ έχουν ως αντικείμενο στοιχεία ενός συνόλου (στην περίπτωση των φυσικών αριθμών, κάποιον φυσικό αριθμό). Είναι δηλαδή της μορφής, «για τον αριθμό x ισχύει η P ιδιότητα». Η λογική δεύτερης βαθμίδας από την άλλη μπορεί να διατυπώσει προτάσεις που αφορούν επιπλέον και σύνολα (για το σύνολο x ισχύει η P ιδιότητα) και υπό αυτή την έννοια είναι πλουσιότερη στην περιγραφική της δυνατότητα από την λογική πρώτης βαθμίδας.
Τώρα, ένα αξιωματικό σύστημα (formal system) αποτελείται από ένα σύνολο αξιωμάτων που συνοδεύονται από ένα σύνολο λογικούς κανόνες (ας τους πούμε «λογικό σύστημα»), με την βοήθεια των οποίων μπορούμε να συνάγουμε θεωρήματα από τα αξιώματα. Ένα τέτοιο «λογικό σύστημα» είναι και η λογική πρώτης βαθμίδας. Είναι λοιπόν σαφές ότι η λογική πρώτης βαθμίδας από μόνη της δεν αποτελεί ένα αξιωματικό σύστημα. Σε αυτό λοιπόν το σημείο, όπου έχουμε ένα αξιωματικό σύστημα, γεννάτε το ερώτημα του κατά πόσο οι λογικοί κανόνες που έχουμε, το λογικό σύστημα, είναι ικανοί να συνάγουν κάθε δυνατό θεώρημα που είναι λογική συνέπεια των αξιωμάτων του συστήματος. Και εδώ έρχεται το θεώρημα της πληρότητας της λογικής πρώτης βαθμίδας να μας πει ότι η λογική πρώτης βαθμίδας είναι ικανή να παράγει κάθε πρόταση που είναι λογική συνέπεια των αξιωμάτων ενός αξιωματικού συστήματος, και άρα με αυτή την έννοια πλήρης. Αυτή η έννοια της «πληρότητας» είναι διαφορετική από την έννοια της πληρότητας που εμφανίζεται στα θεωρήματα της μη πληρότητας του Godel (κάτι που φαίνετε να μπερδεύεται στις διατυπώσεις του βιβλίου). Στο βιβλίο γίνεται και λόγος για την πληρότητα της λογικής δεύτερης βαθμίδας, όπου αναφέρεται ότι αυτή δεν είναι πλήρης σύμφωνα με τα θεωρήματα της μη πληρότητας του Godel (στο λήμμα
Γκέντελ, Κουρτ ), πράγμα που όπως είπαμε και παραπάνω για την λογική πρώτης βαθμίδας, δεν έχει νόημα, αφού η πληρότητα ενός συνόλου λογικών κανόνων αναφέρεται σε άλλο πράγμα. Το αν η λογική δεύτερης βαθμίδας είναι πλήρης με την έννοια που είναι πλήρης και η λογική πρώτης βαθμίδας, είναι ένα θέμα που ξεφεύγει από τις γνώσεις μου, αλλά υπάρχει μία σχετική συζήτηση στην
wikipedia.
Αφού έχουμε πει όλα αυτά λοιπόν για τα «λογικά συστήματα» και την πληρότητά τους, ας επιστρέψουμε στο θέμα με τα θεωρήματα της μη πληρότητας του Godel. Αυτά λοιπόν τα θεωρήματα αφορούν όχι τα λογικά συστήματα, αλλά τα αξιωματικά συστήματα όπως τα ορίσαμε παραπάνω. Το θεώρημα έχει χοντρικά την παρακάτω διατύπωση:
Κάθε «συνεπές» αξιωματικό σύστημα, το οποίο περιέχει «στοιχειώδη αριθμητική», είναι μη πλήρες σε σχέση με προτάσεις που αφορούν την «στοιχειώδη αριθμητική», δηλαδή υπάρχουν τέτοιες προτάσεις που ούτε οι ίδιες ούτε οι αντίθετές τους μπορούν να αποδειχθούν.
Εδώ και πάλι πρέπει να συζητήσουμε κάποιες έννοιες, όπως την έννοια της «στοιχειώδους αριθμητικής».
Πριν από αυτό όμως, ας βγάλουμε από την μέση την έννοια του «συνεπές». Αν έχουμε μια πρόταση Α και την αντίθετή της, τότε συνεπές σημαίνει να μην μπορεί να είναι ταυτόχρονα αληθής και η Α και η αντίθετή της.
Για να πάμε στο «στοιχειώδης αριθμητική» πρέπει πρώτα να ορίσουμε ακόμα μία έννοια. Την έννοια της πρότασης τύπου Goldbach. Μία πρόταση τύπου Goldbach είναι μια πρόταση που δηλώνει ότι, «κάποιος αριθμός έχει την ιδιότητα P», όπου η ιδιότητα P είναι μια ιδιότητα που μπορούμε να ελέγξουμε εφαρμόζοντας έναν συγκεκριμένο αλγόριθμο (προφανή από την διατύπωση της πρότασης) ο οποίος τελικά θα μας δώσει ένα αποτέλεσμα. Για παράδειγμα η πρόταση, «οι ζυγοί αριθμοί διαιρούνται με το 2», είναι μια τέτοια πρόταση, αφού μπορούμε να εφαρμόσουμε έναν αλγόριθμο (να πάρουμε ζυγούς και να τους διαιρέσουμε με το 2) και να βγάλουμε συμπέρασμα για το αν ισχύει η ιδιότητα (δίνει ή δεν δίνει υπόλοιπο μηδέν). Μία σημαντική ιδιότητα αυτού του τύπου των προτάσεων είναι ότι μπορούμε να συμπεράνουμε, εφαρμόζοντας τον αλγόριθμο, το αν η πρόταση ή η αντίθετή της είναι αληθής. Και ερχόμαστε τώρα στο «στοιχειώδης αριθμητική». Όταν λέμε ότι ένα αξιωματικό σύστημα περιέχει κάποια «στοιχειώδη αριθμητική» εννοούμε ότι για κάθε πρόταση του παραπάνω τύπου που μπορεί να αποδειχθεί στα πλαίσια του αξιωματικού αυτού συστήματος, υπάρχει μία διαδικασία που θα παράγει αυτή την απόδειξη.
Ένα παράδειγμα τέτοιου αξιωματικού συστήματος είναι και η αριθμητική των φυσικών αριθμών όπως θεμελιώθηκε αξιωματικά από τον Peano (
Peano Arithmetics), δηλαδή η στοιχειώδης αριθμητική, και βασίζεται στην λογική πρώτης βαθμίδας.
Σχετικά με το θεώρημα και την λογική του, υπάρχει μια πολύ ωραία παρουσίαση στην σελίδα,
Kenny's Overview of Hofstadter's Explanation of Gödel's Theorem, η οποία είναι σχετικά στοιχειώδης και αρκετά επεξηγηματική, ενώ δεν χρειάζεται και πολλές τεχνικές γνώσεις.
Ακόμα πρέπει να πω ότι το θεώρημα δεν εφαρμόζεται σε κάθε αξιωματικό σύστημα (η ιδέα αυτή είναι μία συνήθης παρανόηση). Υπάρχουν και αξιωματικά συστήματα, όπως η Ευκλείδεια Γεωμετρία και η Αριθμητική των Πραγματικών Αριθμών, που ξεφεύγουν από το θεώρημα και είναι και συνεπή και πλήρη.
Πέρα από τα καθαρά μαθηματικά, που δεν εξαντλούνται σε καμία περίπτωση στα παραπάνω, υπάρχουν πολλά ακόμα που μπορεί να πει κανείς σχετικά με το θεώρημα και τις ενδεχόμενες προεκτάσεις του, αλλά αυτό είναι μια πολύ μεγάλη συζήτηση.
Αυτά τα ολίγα...
Και καλή μας χρονιά!!!
