Το θεώρημα της μη πληρότητας του Gödel με απλούς όρους. Ενδιαφέροντα γεγονότα και χρήσιμες συμβουλές

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

Το 1900 πραγματοποιήθηκε στο Παρίσι το Παγκόσμιο Συνέδριο Μαθηματικών, στο οποίο ο David Hilbert (1862-1943) παρουσίασε με τη μορφή περιλήψεων τα 23 σημαντικότερα, κατά τη γνώμη του, προβλήματα που διατύπωσε ο ίδιος, τα οποία επρόκειτο να επιλυθούν από θεωρητικούς επιστήμονες. του ερχόμενου εικοστού αιώνα. Το νούμερο δύο στη λίστα του ήταν ένα από αυτά απλές εργασίες, η απάντηση στο οποίο φαίνεται προφανής μέχρι να σκάψετε λίγο πιο βαθιά. ομιλία σύγχρονη γλώσσα, αυτό ήταν το ερώτημα: είναι επαρκή τα μαθηματικά από μόνα τους; Το δεύτερο πρόβλημα του Hilbert ήταν να αποδείξει αυστηρά ότι το σύστημα αξιώματα- οι βασικές δηλώσεις που λαμβάνονται στα μαθηματικά ως βάση χωρίς απόδειξη - είναι τέλειο και πλήρες, δηλαδή σας επιτρέπει να περιγράψετε μαθηματικά όλα όσα υπάρχουν. Ήταν απαραίτητο να αποδειχθεί ότι είναι δυνατό να τεθεί ένα τέτοιο σύστημα αξιωμάτων που, πρώτον, θα είναι αμοιβαία συνεπή και, δεύτερον, μπορεί κανείς να συναγάγει ένα συμπέρασμα από αυτά σχετικά με την αλήθεια ή το ψεύδος οποιασδήποτε δήλωσης.

Ας πάρουμε ένα παράδειγμα από τη σχολική γεωμετρία. Πρότυπο Ευκλείδεια επιπεδομετρία(γεωμετρία στο επίπεδο) είναι δυνατόν να αποδειχθεί άνευ όρων ότι η πρόταση "το άθροισμα των γωνιών ενός τριγώνου είναι 180°" είναι αληθής και η πρόταση "το άθροισμα των γωνιών ενός τριγώνου είναι 137°" είναι ψευδής. Μιλώντας ουσιαστικά, στην Ευκλείδεια γεωμετρία, οποιαδήποτε δήλωση είναι είτε ψευδής είτε αληθής, και η τρίτη δεν δίνεται. Και στις αρχές του εικοστού αιώνα, οι μαθηματικοί πίστευαν αφελώς ότι η ίδια κατάσταση έπρεπε να παρατηρηθεί σε οποιοδήποτε λογικά συνεπές σύστημα.

Και τότε το 1931, κάποιος Βιεννέζος μαθηματικός με γυαλιά, Kurt Godel, πήρε και δημοσίευσε ένα σύντομο άρθρο που απλώς ανέτρεψε ολόκληρο τον κόσμο της λεγόμενης «μαθηματικής λογικής». Μετά από μακρά και πολύπλοκα μαθηματικά και θεωρητικά προοίμια, εδραίωσε κυριολεκτικά τα εξής. Ας πάρουμε οποιαδήποτε δήλωση όπως: "Η υπόθεση #247 είναι λογικά αναπόδεικτη σε αυτό το σύστημα αξιωμάτων" και ας την ονομάσουμε "δήλωση Α". Έτσι ο Gödel απλά απέδειξε την ακόλουθη καταπληκτική ιδιότητα όποιοςαξιωματικά συστήματα:

"Εάν μια πρόταση Α μπορεί να αποδειχθεί, τότε μια πρόταση που δεν είναι Α μπορεί να αποδειχθεί."

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

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

Η διατύπωση λοιπόν πρώτα,ή αδύναμος Θεωρήματα μη πληρότητας του Gödel: "Οποιοδήποτε επίσημο σύστημα αξιωμάτων περιέχει ανεπίλυτες υποθέσεις." Όμως ο Gödel δεν σταμάτησε εκεί, να διατυπώνει και να αποδεικνύει δεύτερος,ή ισχυρός Θεώρημα μη πληρότητας του Γκόντελ: «Η λογική πληρότητα (ή η μη πληρότητα) οποιουδήποτε συστήματος αξιωμάτων δεν μπορεί να αποδειχθεί στο πλαίσιο αυτού του συστήματος. Για την απόδειξη ή την απόρριψή του απαιτούνται πρόσθετα αξιώματα (ενίσχυση του συστήματος)».

Θα ήταν ασφαλέστερο να πιστεύουμε ότι τα θεωρήματα του Godel είναι αφηρημένα και δεν μας αφορούν, αλλά μόνο τομείς εξαιρετικής μαθηματικής λογικής, αλλά στην πραγματικότητα αποδείχθηκε ότι σχετίζονται άμεσα με τη δομή του ανθρώπινου εγκεφάλου. Ο Άγγλος μαθηματικός και φυσικός Roger Penrose (γεννημένος το 1931) έδειξε ότι τα θεωρήματα του Gödel θα μπορούσαν να χρησιμοποιηθούν για να αποδείξουν θεμελιώδεις διαφορές μεταξύ του ανθρώπινου εγκεφάλου και ενός υπολογιστή. Η ουσία του συλλογισμού του είναι απλή. Ο υπολογιστής λειτουργεί αυστηρά λογικά και δεν είναι σε θέση να προσδιορίσει αν η πρόταση Α είναι αληθής ή ψευδής εάν ξεφεύγει από το εύρος της αξιωματικής, και τέτοιες δηλώσεις, σύμφωνα με το θεώρημα του Γκέντελ, αναπόφευκτα υπάρχουν. Ένα άτομο, αντιμέτωπο με μια τόσο λογικά αναπόδεικτη και αδιάψευστη δήλωση Α, είναι πάντα σε θέση να προσδιορίσει την αλήθεια ή το ψεύδος της - με βάση την καθημερινή εμπειρία. Τουλάχιστον σε αυτό ανθρώπινος εγκέφαλοςξεπερνάει έναν υπολογιστή δεσμευμένο με καθαρό λογικά κυκλώματα. Ο ανθρώπινος εγκέφαλος είναι σε θέση να κατανοήσει το πλήρες βάθος της αλήθειας που περιέχεται στα θεωρήματα του Gödel, αλλά ένας υπολογιστής δεν μπορεί ποτέ. Επομένως, ο ανθρώπινος εγκέφαλος κάθε άλλο παρά ένας υπολογιστής είναι. Είναι ικανός να παίρνουν αποφάσεις, και το τεστ Turing θα περάσει.

Αναρωτιέμαι αν ο Χίλμπερτ είχε ιδέα πόσο μακριά θα μας πήγαιναν οι ερωτήσεις του;

Kurt Godel, 1906-78

Αυστριακός και τότε Αμερικανός μαθηματικός. Γεννήθηκε στο Brünn (Brünn, τώρα Brno, Τσεχία). Αποφοίτησε από το Πανεπιστήμιο της Βιέννης, όπου παρέμεινε δάσκαλος στο Τμήμα Μαθηματικών (από το 1930 - καθηγητής). Το 1931 δημοσίευσε ένα θεώρημα που αργότερα έλαβε το όνομά του. Όντας ένας καθαρά απολιτικός άνθρωπος, επέζησε εξαιρετικά σκληρά από τη δολοφονία του φίλου και υπαλλήλου του τμήματος από έναν ναζιστή φοιτητή και έπεσε σε βαθιά κατάθλιψη, οι υποτροπές της οποίας τον στοίχειωσαν μέχρι το τέλος της ζωής του. Στη δεκαετία του 1930, μετανάστευσε στις Ηνωμένες Πολιτείες, αλλά επέστρεψε στην πατρίδα του την Αυστρία και παντρεύτηκε. Το 1940, στο απόγειο του πολέμου, αναγκάστηκε να καταφύγει στην Αμερική διαμετακομίζοντας μέσω της ΕΣΣΔ και της Ιαπωνίας. Εργάστηκε για λίγο στο Ινστιτούτο Πρίνστον προηγμένη έρευνα. Δυστυχώς, η ψυχή του επιστήμονα δεν άντεξε και πέθανε από ασιτία σε μια ψυχιατρική κλινική, αρνούμενος να φάει, επειδή ήταν πεπεισμένος ότι σκόπευαν να τον δηλητηριάσουν.

Με ενδιαφέρει εδώ και καιρό τι είναι το συγκλονιστικό θεώρημα Gödel. Και πώς είναι χρήσιμο για τη ζωή. Και τελικά μπόρεσα να το καταλάβω.

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

Θα το μετέφραζα σε μια ανθρώπινη μη μαθηματική γλώσσα όπως αυτή (αξίωμα είναι η αρχική θέση μιας θεωρίας, που γίνεται αποδεκτή στο πλαίσιο αυτής της θεωρίας ως αληθής χωρίς να απαιτείται απόδειξη και χρησιμοποιείται ως βάση για την απόδειξη των άλλων διατάξεών της). Στη ζωή, αξίωμα είναι οι αρχές που ακολουθεί ένα άτομο, η κοινωνία, επιστημονική κατεύθυνση, δηλώνει. Μεταξύ των εκπροσώπων της θρησκείας, τα αξιώματα ονομάζονται δόγματα. Κατά συνέπεια, οποιαδήποτε αρχή μας, οποιοδήποτε σύστημα απόψεων, ξεκινώντας από ένα ορισμένο επίπεδο, γίνεται εσωτερικά αντιφατικό ή ελλιπές. Για να πειστεί κανείς για την αλήθεια μιας ορισμένης δήλωσης, θα πρέπει να υπερβεί το δεδομένο σύστημα απόψεων και να οικοδομήσει ένα νέο. Θα είναι όμως και ατελής. Δηλαδή η ΔΙΑΔΙΚΑΣΙΑ ΤΗΣ ΓΝΩΣΗΣ ΕΙΝΑΙ ΑΠΕΙΡΗ. Ο κόσμος δεν μπορεί να γίνει πλήρως γνωστός μέχρι να φτάσουμε στην πηγή.

"... αν θεωρήσουμε την ικανότητα λογικής λογικής ως το κύριο χαρακτηριστικό του ανθρώπινου νου ή τουλάχιστον το κύριο εργαλείο του, τότε το θεώρημα του Γκέντελ υποδεικνύει άμεσα τις περιορισμένες δυνατότητες του εγκεφάλου μας. Συμφωνήστε ότι είναι πολύ δύσκολο για ένα άτομο που φέρεται με βάση την πίστη στην άπειρη δύναμη της σκέψης να αποδεχθεί τη θέση για τα όρια της δύναμής της… Πολλοί ειδικοί πιστεύουν ότι οι τυπικές-υπολογιστικές, «αριστοτελικές» διαδικασίες που κρύβονται λογική σκέψη, είναι μόνο ένα μέρος ανθρώπινη συνείδηση. Η άλλη του περιοχή, ουσιαστικά «μη υπολογιστική», είναι υπεύθυνη για εκδηλώσεις όπως η διαίσθηση, οι δημιουργικές ιδέες και η κατανόηση. Και αν το πρώτο μισό του μυαλού εμπίπτει στους περιορισμούς του Gödel, τότε το δεύτερο μισό είναι απαλλαγμένο από τέτοια όρια... Ο φυσικός Roger Penrose προχώρησε ακόμη περισσότερο. Πρότεινε την ύπαρξη κάποιων κβαντικών επιδράσεων μη υπολογιστικής φύσης, που εξασφαλίζουν την πραγματοποίηση δημιουργικών πράξεων συνείδησης... Μία από τις πολλές συνέπειες της υπόθεσης Penrose μπορεί να είναι, ειδικότερα, το συμπέρασμα ότι τεχνητή νοημοσύνημε βάση τις σύγχρονες υπολογιστικές συσκευές, ακόμα κι αν η έλευση των κβαντικών υπολογιστών θα οδηγήσει σε μια μεγαλειώδη ανακάλυψη στον τομέα της τεχνολογίας υπολογιστών. Το γεγονός είναι ότι οποιοσδήποτε υπολογιστής μπορεί να μοντελοποιήσει όλο και με μεγαλύτερη ακρίβεια το έργο της τυπικής-λογικής, «υπολογιστικής» δραστηριότητας της ανθρώπινης συνείδησης, αλλά οι «μη υπολογιστικές» ικανότητες της νόησης είναι απρόσιτες σε αυτόν.

Μια σημαντική συνέπεια του θεωρήματος του Gödel είναι το συμπέρασμα ότι δεν μπορεί κανείς να σκεφτεί στα άκρα. Πάντα μέσα υπάρχουσα θεωρίαυπάρχει μια δήλωση που δεν μπορεί ούτε να αποδειχθεί ούτε να διαψευστεί. Ή, με άλλα λόγια, σε κάποια δήλωση υπάρχει πάντα ένα ζευγάρι που τη διαψεύδει.

Επόμενο συμπέρασμα. Το καλό και το κακό είναι μόνο οι 2 όψεις του ίδιου νομίσματος, χωρίς τις οποίες δεν μπορεί να υπάρξει. Και προέρχεται από την αρχή ότι στο Σύμπαν υπάρχει μόνο μία πηγή για τα πάντα: το καλό και το κακό, η αγάπη και το μίσος, η ζωή και ο θάνατος.

Οποιαδήποτε δήλωση πληρότητας του συστήματος είναι ψευδής. Δεν μπορείτε να βασιστείτε σε δόγματα, γιατί αργά ή γρήγορα θα διαψευστούν.

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

Εδώ είναι ένα άλλο μικρό κείμενο που αποκαλύπτει ευρέως την ουσία που προκύπτει από το θεώρημα του Gödel:
«Μου φαίνεται ότι αυτό το θεώρημα έχει ένα σημαντικό φιλοσοφικό νόημα. Μόνο δύο επιλογές είναι δυνατές:

α) Η θεωρία είναι ελλιπής, δηλ. με όρους θεωρίας, μπορεί κανείς να διατυπώσει ένα ερώτημα στο οποίο είναι αδύνατο να εξαχθεί είτε θετική είτε αρνητική απάντηση από τα αξιώματα/αξιώματα της θεωρίας. Ταυτόχρονα, απαντήσεις σε όλα αυτά τα ερωτήματα μπορούν να δοθούν στο πλαίσιο μιας πιο ολοκληρωμένης θεωρίας, στην οποία η παλιά θα αποτελεί ειδική περίπτωση. Αλλά αυτό νέα θεωρίαθα έχει τα δικά του «αναπάντητα ερωτήματα» και ούτω καθεξής επί άπειρον.

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

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

Ο «Παντοδύναμος Θεός» ανήκει στον δεύτερο τύπο. Ο Παντοδύναμος Θεός είναι η απάντηση σε κάθε ερώτηση. Και αυτό σημαίνει αυτόματα ότι οδηγεί σε λογικό παραλογισμό. Παράδοξα όπως η «βαριά πέτρα» μπορούν να εφευρεθούν κατά παρτίδες.

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

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

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

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

Πριν από σχεδόν 100 χρόνια, ο Gödel έκανε ένα απίστευτο βήμα στην κατανόηση των νόμων του σύμπαντος. Και ακόμα δεν μπορέσαμε να το χρησιμοποιήσουμε, θεωρώντας αυτό το θεώρημα ως εξαιρετικά εξειδικευμένο μαθηματικό πρόβλημαγια έναν στενό κύκλο ανθρώπων που ασχολούνται με κάποια αφηρημένα θέματα στον δικό τους κύκλο. Μαζί με κβαντική θεωρίακαι οι διδασκαλίες του Χριστού, το θεώρημα του Γκέντελ μας δίνει τη δυνατότητα να ξεφύγουμε από την αιχμαλωσία των ψευδών δογμάτων, να ξεπεράσουμε την κρίση που εξακολουθεί να επιμένει στην κοσμοθεωρία μας. Και ο χρόνος τελειώνει.

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

Και λοιπόν? Παρακάτω θα προσπαθήσω να «στα δάχτυλα» να μιλήσω για αυτό. Η έκθεσή μου, φυσικά, δεν θα είναι αυστηρή και διαισθητική, αλλά θα ζητήσω από τους μαθηματικούς να μην με κρίνουν αυστηρά. Δεν αποκλείεται για τους μη μαθηματικούς (στους οποίους μάλιστα ανήκω και εγώ) να υπάρχει κάτι νέο και χρήσιμο σε όσα λέγονται παρακάτω.

Η μαθηματική λογική είναι πράγματι μια μάλλον περίπλοκη επιστήμη, και το πιο σημαντικό, όχι πολύ οικεία. Απαιτεί προσεκτικούς και αυστηρούς ελιγμούς, στους οποίους είναι σημαντικό να μην συγχέουμε το πραγματικά αποδεδειγμένο με το ότι «είναι ήδη ξεκάθαρο». Ωστόσο, ελπίζω ότι για να κατανοήσει το ακόλουθο «περίγραμμα της απόδειξης του TGN», ο αναγνώστης θα χρειαστεί μόνο γνώσεις σχολικών μαθηματικών / επιστήμης υπολογιστών, δεξιότητες λογικής σκέψης και 15-20 λεπτά χρόνου.

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

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

Η μετάβαση από τον έναν τύπο στον άλλο συμβαίνει σύμφωνα με ορισμένους γνωστούς κανόνες. Η μετάβαση από τον 4ο τύπο στον 5ο συνέβη, ας πούμε, επειδή κάθε αριθμός είναι ίσος με τον εαυτό του - αυτό είναι το αξίωμα της αριθμητικής. Και η όλη διαδικασία απόδειξης, έτσι, μεταφράζει τον τύπο στη δυαδική τιμή TRUE. Το αποτέλεσμα θα μπορούσε να είναι ΛΑΘΟΣ - αν διαψεύδαμε κάποια φόρμουλα. Σε αυτή την περίπτωση, θα αποδείξαμε την άρνησή του. Είναι δυνατό να φανταστεί κανείς ένα πρόγραμμα (και τέτοια προγράμματα στην πραγματικότητα γράφονται) που θα αποδείκνυε τέτοιες (και πιο σύνθετες) προτάσεις χωρίς ανθρώπινη παρέμβαση.

Ας πούμε το ίδιο και λίγο πιο επίσημα. Ας υποθέσουμε ότι έχουμε ένα σύνολο που αποτελείται από σειρές χαρακτήρων κάποιου αλφαβήτου και υπάρχουν κανόνες με τους οποίους ένα υποσύνολο του λεγόμενου δηλώσεις- δηλαδή φράσεις με γραμματική σημασία, καθεμία από τις οποίες είναι σωστή ή ψευδής. Μπορούμε να πούμε ότι υπάρχει μια συνάρτηση που αντιστοιχίζει προτάσεις από μία από τις δύο τιμές: TRUE ή FALSE (δηλαδή, τις αντιστοιχίζει σε ένα Boolean σύνολο δύο στοιχείων).

Ας καλέσουμε ένα τέτοιο ζεύγος - ένα σύνολο δηλώσεων και μια συνάρτηση από έως - "γλώσσα δηλώσεων". Σημειώστε ότι με την καθημερινή έννοια η έννοια της γλώσσας είναι κάπως ευρύτερη. Για παράδειγμα, η ρωσική φράση "Λοιπόν, έλα εδώ!"δεν είναι αληθές και όχι ψευδές, δηλαδή από την άποψη της μαθηματικής λογικής δεν είναι δήλωση.

Για ό,τι ακολουθεί, χρειαζόμαστε την έννοια του αλγορίθμου. Δεν θα δώσω εδώ τον επίσημο ορισμό του - αυτό θα μας παρέσυρε αρκετά. Θα περιοριστώ στο ανεπίσημο: "αλγόριθμος"- αυτή η ακολουθία μονοσήμαντων οδηγιών ("πρόγραμμα"), η οποία ανά πεπερασμένος αριθμόςβήματαμετατρέπει τα δεδομένα εισόδου σε έξοδο. Η πλάγια γραφή είναι θεμελιωδώς σημαντική - εάν το πρόγραμμα κολλήσει σε κάποια αρχικά δεδομένα, τότε δεν περιγράφει τον αλγόριθμο. Για απλότητα και εφαρμογή στην περίπτωσή μας, ο αναγνώστης μπορεί να θεωρήσει ότι ένας αλγόριθμος είναι ένα πρόγραμμα γραμμένο σε οποιαδήποτε γνωστή γλώσσα προγραμματισμού, το οποίο, για οποιαδήποτε δεδομένα εισόδου από μια δεδομένη κλάση, είναι εγγυημένο ότι θα ολοκληρώσει την εργασία του με ένα αποτέλεσμα Boole.

Ας αναρωτηθούμε: υπάρχει ένας «αλγόριθμος απόδειξης» για κάθε συνάρτηση (ή, εν συντομία, "επαγωγικός") ισοδύναμη με αυτήν τη συνάρτηση, δηλαδή μεταφράζοντας κάθε πρόταση στην ίδια ακριβώς boolean τιμή με αυτήν; Πιο συνοπτικά, το ίδιο ερώτημα μπορεί να διατυπωθεί ως εξής: είναι κάθε συνάρτηση πάνω από ένα σύνολο προτάσεων υπολογίσιμος? Όπως μπορείτε ήδη να μαντέψετε, από την εγκυρότητα του TGN προκύπτει ότι όχι, όχι καμία - υπάρχουν μη υπολογίσιμες συναρτήσεις αυτού του τύπου. Με άλλα λόγια, δεν μπορεί να αποδειχθεί κάθε αληθής δήλωση.

Μπορεί κάλλιστα αυτή η δήλωση να σας προκαλέσει μια εσωτερική διαμαρτυρία. Αυτό οφείλεται σε διάφορες συνθήκες. Πρώτον, όταν διδασκόμαστε σχολικά μαθηματικά, τότε μερικές φορές υπάρχει μια εσφαλμένη εντύπωση για την σχεδόν πλήρη ταυτότητα των φράσεων «το θεώρημα είναι αληθές» και «είναι δυνατό να αποδειχθεί ή να επαληθευτεί το θεώρημα». Αλλά αν το σκεφτείς, δεν είναι καθόλου προφανές. Μερικά θεωρήματα αποδεικνύονται πολύ απλά (για παράδειγμα, με την απαρίθμηση ενός μικρού αριθμού επιλογών), και μερικά είναι πολύ δύσκολα. Σκεφτείτε, για παράδειγμα, το περίφημο Τελευταίο Θεώρημα του Φερμά:

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

Το δεύτερο διαισθητικό επιχείρημα κατά του TGN είναι πιο λεπτό. Ας υποθέσουμε ότι έχουμε κάποια αναπόδεικτη (μέσα στο πλαίσιο αυτής της απαγωγικής) δήλωσης. Τι μας εμποδίζει να το δεχτούμε ως νέο αξίωμα; Έτσι, θα περιπλέκουμε ελαφρώς το σύστημα αποδείξεών μας, αλλά αυτό δεν είναι τρομερό. Αυτό το επιχείρημα θα ήταν απολύτως σωστό αν υπήρχε ένας πεπερασμένος αριθμός αναπόδεικτων προτάσεων. Στην πράξη, μπορεί να συμβεί το εξής - αφού θέσετε ένα νέο αξίωμα, θα σκοντάψετε σε μια νέα αναπόδεικτη δήλωση. Πάρτε το ως άλλο αξίωμα - θα σκοντάψετε στο τρίτο. Και ούτω καθεξής επί άπειρον. Λένε ότι το deductica θα μείνει ατελής. Μπορούμε επίσης να λάβουμε αυστηρά μέτρα ώστε ο αλγόριθμος απόδειξης να τελειώνει μετά από έναν πεπερασμένο αριθμό βημάτων με κάποιο αποτέλεσμα για οποιαδήποτε δήλωση της γλώσσας. Ταυτόχρονα όμως θα αρχίσει να λέει ψέματα - να οδηγεί στην αλήθεια για λανθασμένες δηλώσεις ή στα ψέματα - για τους πιστούς. Σε τέτοιες περιπτώσεις λέγεται ότι η απαγωγική αντιφατικός. Έτσι, μια ακόμη διατύπωση του TGN ακούγεται ως εξής: "Υπάρχουν προτασιακές γλώσσες για τις οποίες είναι αδύνατη η πλήρης συνεπής απαγωγή" - εξ ου και το όνομα του θεωρήματος.

Μερικές φορές ονομάζεται «θεώρημα Gödel» είναι η δήλωση ότι οποιαδήποτε θεωρία περιέχει προβλήματα που δεν μπορούν να επιλυθούν στο πλαίσιο της ίδιας της θεωρίας και απαιτούν τη γενίκευσή της. Κατά μία έννοια αυτό είναι αλήθεια, αν και μια τέτοια διατύπωση συσκοτίζει το ζήτημα παρά το διευκρινίζει.

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

Για όσα ακολουθούν, περιγράφουμε τη γλώσσα τυπική αριθμητική". Θεωρήστε μια κατηγορία συμβολοσειρών κειμένου πεπερασμένου μήκους, που αποτελούνται από αραβικούς αριθμούς, μεταβλητές (γράμματα Λατινικό αλφάβητο), παίρνοντας φυσικές αξίες, χώρους, χαρακτήρες αριθμητικές πράξεις, ισότητα και ανισότητα, ποσοτικοί δείκτες («υπάρχει») και («για οποιοδήποτε») και, ίσως, κάποια άλλα σύμβολα (ο ακριβής αριθμός και η σύνθεσή τους δεν έχουν σημασία για εμάς). Είναι σαφές ότι δεν έχουν νόημα όλες αυτές οι γραμμές (για παράδειγμα, το "" είναι ανοησία). Το υποσύνολο των εκφράσεων με νόημα από αυτήν την κλάση (δηλαδή, συμβολοσειρές που είναι αληθείς ή ψευδείς από την άποψη της συνηθισμένης αριθμητικής) θα είναι το σύνολο των δηλώσεών μας.

Παραδείγματα τυπικών αριθμητικών δηλώσεων:

και τα λοιπά. Τώρα ας ονομάσουμε έναν "τύπο με ελεύθερη παράμετρο" (FSP) μια συμβολοσειρά που γίνεται δήλωση εάν ένας φυσικός αριθμός αντικατασταθεί σε αυτήν ως αυτή η παράμετρος. Παραδείγματα FSP (με παράμετρο):

και τα λοιπά. Με άλλα λόγια, τα FSP είναι ισοδύναμα με συναρτήσεις ενός φυσικού ορίσματος με τιμή Boolean.

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

Ας στραφούμε τώρα σε ένα σκίτσο της απόδειξης του TGN στην ακόλουθη διατύπωση:

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

Θα το αποδείξουμε με αντίφαση.

Ας υποθέσουμε λοιπόν ότι υπάρχει μια τέτοια απαγωγική. Ας περιγράψουμε τον ακόλουθο βοηθητικό αλγόριθμο που εκχωρεί μια boolean τιμή σε έναν φυσικό αριθμό ως εξής:

Με απλά λόγια, ο αλγόριθμος καταλήγει στην τιμή TRUE εάν και μόνο εάν το αποτέλεσμα της αντικατάστασης στο FSP του δικού του αριθμού στη λίστα μας δίνει μια ψευδή δήλωση.

Εδώ φτάνουμε στο μόνο μέρος όπου θα ζητήσω από τον αναγνώστη να δεχτεί το λόγο μου.

Προφανώς, σύμφωνα με την παραπάνω υπόθεση, οποιοδήποτε FSP από μπορεί να συσχετιστεί με έναν αλγόριθμο που περιέχει έναν φυσικό αριθμό στην είσοδο και μια Boolean τιμή στην έξοδο. Λιγότερο προφανές είναι το αντίθετο:

Η απόδειξη αυτού του λήμματος θα απαιτούσε τουλάχιστον έναν τυπικό, όχι έναν διαισθητικό, ορισμό της έννοιας του αλγορίθμου. Ωστόσο, αν το σκεφτείς λίγο, είναι αρκετά εύλογο. Πράγματι, οι αλγόριθμοι είναι γραμμένοι σε αλγοριθμικές γλώσσες, μεταξύ των οποίων υπάρχουν εξωτικές όπως, για παράδειγμα, το Brainfuck , το οποίο αποτελείται από οκτώ λέξεις ενός χαρακτήρα, στις οποίες, ωστόσο, μπορεί να εφαρμοστεί οποιοσδήποτε αλγόριθμος. Θα ήταν περίεργο εάν η πλουσιότερη γλώσσα τυπικών αριθμητικών τύπων που περιγράψαμε αποδεικνυόταν φτωχότερη - αν και, αναμφίβολα, δεν είναι πολύ κατάλληλη για συνηθισμένο προγραμματισμό.

Αφού περάσουμε αυτό το ολισθηρό μέρος, φτάνουμε γρήγορα στο τέλος.

Έτσι, περιγράψαμε τον αλγόριθμο παραπάνω. Σύμφωνα με το λήμμα που σας ζήτησα να πιστέψετε, υπάρχει ένα αντίστοιχο FSP. Έχει κάποιο αριθμό στη λίστα - ας πούμε . Ας αναρωτηθούμε, ποιο είναι το νόημα; Ας είναι ΑΛΗΘΕΙΑ. Στη συνέχεια, σύμφωνα με την κατασκευή του αλγορίθμου (και επομένως τη συνάρτηση που ισοδυναμεί με αυτόν), αυτό σημαίνει ότι το αποτέλεσμα της αντικατάστασης ενός αριθμού στη συνάρτηση είναι FALSE. Το αντίθετο ελέγχεται με τον ίδιο τρόπο: από FALSE ακολουθεί TRUE. Φτάσαμε σε μια αντίφαση, που σημαίνει ότι η αρχική υπόθεση είναι λανθασμένη. Έτσι, για την τυπική αριθμητική, δεν υπάρχει πλήρης συνεπής έκπτωση. Q.E.D.

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

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

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

«Κάθε φράση κινέζικαείναι αληθινή δήλωση εάν περιέχεται στο βιβλίο αποσπασμάτων του συντρόφου Μάο Τσε Τουνγκ και είναι λανθασμένη αν δεν περιέχεται.

Τότε ο αντίστοιχος πλήρης και συνεπής αλγόριθμος απόδειξης (μπορεί να ονομαστεί «δογματικός απαγωγικός») μοιάζει κάπως έτσι:

«Ξεφυλλίστε το βιβλίο αποσπασμάτων του συντρόφου Μάο Τσε Τουνγκ μέχρι να βρείτε τη δήλωση που ψάχνετε. Αν βρεθεί, τότε είναι αληθές, και αν το βιβλίο αποσπασμάτων έχει τελειώσει και η δήλωση δεν βρεθεί, τότε είναι ψευδής.

Εδώ μας σώζει το γεγονός ότι οποιαδήποτε παραπομπή είναι προφανώς πεπερασμένη, άρα η διαδικασία της «απόδειξης» αναπόφευκτα θα τελειώσει. Επομένως, το TGN δεν μπορεί να εφαρμοστεί στη γλώσσα των δογματικών δηλώσεων. Αλλά μιλούσαμε για πολύπλοκες γλώσσες, σωστά;

Ετικέτες: Προσθήκη ετικετών

09ιαπωνικό λεπτό

Το 1900 πραγματοποιήθηκε στο Παρίσι το Παγκόσμιο Συνέδριο Μαθηματικών, όπου Ντέιβιντ Γκίλμπερτ(David Hilbert, 1862–1943) περιέγραψε με τη μορφή διατριβών τα 23 σημαντικότερα, κατά τη γνώμη του, καθήκοντα που έπρεπε να επιλύσουν οι θεωρητικοί του εικοστού αιώνα. Το νούμερο δύο στη λίστα του ήταν ένα από εκείνα τα απλά προβλήματα που φαίνονται προφανή μέχρι να σκάψετε λίγο πιο βαθιά. Με σύγχρονους όρους, ήταν το ερώτημα: είναι επαρκή τα μαθηματικά από μόνα τους; Το δεύτερο καθήκον του Hilbert περιορίστηκε στην ανάγκη να αποδείξει αυστηρά ότι το σύστημα των αξιωμάτων - βασικές δηλώσεις που λαμβάνονται στα μαθηματικά ως βάση χωρίς απόδειξη - είναι τέλειο και πλήρες, δηλαδή επιτρέπει τη μαθηματική περιγραφή όλων όσων υπάρχουν. Ήταν απαραίτητο να αποδειχθεί ότι είναι δυνατό να τεθεί ένα τέτοιο σύστημα αξιωμάτων που, πρώτον, θα είναι αμοιβαία συνεπή και, δεύτερον, μπορεί κανείς να συναγάγει ένα συμπέρασμα από αυτά σχετικά με την αλήθεια ή το ψεύδος οποιασδήποτε δήλωσης.

Ας πάρουμε ένα παράδειγμα από τη σχολική γεωμετρία. Στην τυπική ευκλείδεια επιπεδομετρία (γεωμετρία σε επίπεδο), μπορεί να αποδειχθεί άνευ όρων ότι η πρόταση "το άθροισμα των γωνιών ενός τριγώνου είναι 180°" είναι αληθής και η πρόταση "το άθροισμα των γωνιών ενός τριγώνου είναι 137°". "είναι ψευδής. Μιλώντας ουσιαστικά, στην Ευκλείδεια γεωμετρία, οποιαδήποτε δήλωση είναι είτε ψευδής είτε αληθής, και η τρίτη δεν δίνεται. Και στις αρχές του εικοστού αιώνα, οι μαθηματικοί πίστευαν αφελώς ότι η ίδια κατάσταση έπρεπε να παρατηρηθεί σε οποιοδήποτε λογικά συνεπές σύστημα.

Και τότε το 1931 κάποιος Βιεννέζος μαθηματικός με γυαλιά Kurt Gödel- πήρε και δημοσίευσε ένα σύντομο άρθρο που απλά ανέτρεψε όλο τον κόσμο της λεγόμενης «μαθηματικής λογικής». Μετά από μακρά και πολύπλοκα μαθηματικά και θεωρητικά προοίμια, εδραίωσε κυριολεκτικά τα εξής. Ας πάρουμε οποιαδήποτε δήλωση όπως: "Η υπόθεση #247 είναι λογικά αναπόδεικτη σε αυτό το σύστημα αξιωμάτων" και ας την ονομάσουμε "δήλωση Α". Έτσι, ο Gödel απέδειξε απλώς την ακόλουθη καταπληκτική ιδιότητα οποιουδήποτε συστήματος αξιωμάτων:

"Εάν μια πρόταση Α μπορεί να αποδειχθεί, τότε μια πρόταση που δεν είναι Α μπορεί να αποδειχθεί."

Με άλλα λόγια, εάν είναι δυνατόν να αποδειχθεί η εγκυρότητα της δήλωσης «Η υπόθεση 247 δεν αποδεικνύεται», τότε είναι δυνατόν να αποδειχθεί και η εγκυρότητα της δήλωσης «Υπόθεση 247 είναι αποδείξιμη». Δηλαδή, επιστρέφοντας στη διατύπωση του δεύτερου προβλήματος Hilbert, εάν το σύστημα των αξιωμάτων είναι πλήρες (δηλαδή, οποιαδήποτε δήλωση σε αυτό μπορεί να αποδειχθεί), τότε είναι ασυνεπής.

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

Έτσι, η διατύπωση του πρώτου, ή ασθενούς, θεωρήματος της μη πληρότητας του Gödel είναι: "Οποιοδήποτε επίσημο σύστημα αξιωμάτων περιέχει ανεπίλυτες υποθέσεις". Αλλά ο Gödel δεν σταμάτησε εκεί, διατυπώνοντας και αποδεικνύοντας το δεύτερο ή ισχυρό θεώρημα της ατελότητας του Gödel: «Η λογική πληρότητα (ή η ατελότητα) οποιουδήποτε συστήματος αξιωμάτων δεν μπορεί να αποδειχθεί στο πλαίσιο αυτού του συστήματος. Για την απόδειξη ή την απόρριψή του απαιτούνται επιπλέον αξιώματα (ενίσχυση του συστήματος).

Θα ήταν ασφαλέστερο να πιστεύουμε ότι τα θεωρήματα του Godel είναι αφηρημένα και δεν μας αφορούν, αλλά μόνο τομείς εξαιρετικής μαθηματικής λογικής, αλλά στην πραγματικότητα αποδείχθηκε ότι σχετίζονται άμεσα με τη δομή του ανθρώπινου εγκεφάλου. Ο Άγγλος μαθηματικός και φυσικός Roger Penrose (γεννημένος το 1931) έδειξε ότι Θεωρήματα Gödelμπορεί να χρησιμοποιηθεί για να αποδείξει την ύπαρξη θεμελιωδών διαφορών μεταξύ του ανθρώπινου εγκεφάλου και ενός υπολογιστή. Η ουσία του συλλογισμού του είναι απλή. Ο υπολογιστής λειτουργεί αυστηρά λογικά και δεν είναι σε θέση να προσδιορίσει αν η πρόταση Α είναι αληθής ή ψευδής εάν ξεφεύγει από το εύρος της αξιωματικής, και τέτοιες δηλώσεις, σύμφωνα με το θεώρημα του Γκέντελ, αναπόφευκτα υπάρχουν. Ένα άτομο, αντιμέτωπο με μια τόσο λογικά αναπόδεικτη και αδιάψευστη δήλωση Α, είναι πάντα σε θέση να προσδιορίσει την αλήθεια ή το ψεύδος της - με βάση την καθημερινή εμπειρία. Τουλάχιστον σε αυτό, ο ανθρώπινος εγκέφαλος είναι ανώτερος από έναν υπολογιστή που δένεται από καθαρά λογικά κυκλώματα. Ο ανθρώπινος εγκέφαλος είναι σε θέση να κατανοήσει το πλήρες βάθος της αλήθειας που περιέχεται στα θεωρήματα του Gödel, αλλά ένας υπολογιστής δεν μπορεί ποτέ. Επομένως, ο ανθρώπινος εγκέφαλος κάθε άλλο παρά ένας υπολογιστής είναι. Είναι σε θέση να παίρνει αποφάσεις και το τεστ Τούρινγκ θα περάσει.

με θέμα: "ΘΕΩΡΗΜΑ ΤΟΥ GODEL"

Kurt Gödel

Ο Kurt Gödel είναι ο μεγαλύτερος ειδικός σε μαθηματική λογική- γεννήθηκε στις 28 Απριλίου 1906 στο Brunn (τώρα Brno, Τσεχία). Αποφοίτησε από το Πανεπιστήμιο της Βιέννης, όπου υπερασπίστηκε τη διδακτορική του διατριβή, ήταν επίκουρος καθηγητής το 1933–1938. Μετά το Anschluss, μετανάστευσε στις Ηνωμένες Πολιτείες. Από το 1940 έως το 1963 ο Γκέντελ εργάστηκε στο Ινστιτούτο Πρίνστον ανώτερες σπουδές. Gödel, Επίτιμος Διδάκτορας από τα Πανεπιστήμια Yale και Harvard, υπότροφος Εθνική ΑκαδημίαΕπιστήμες των Ηνωμένων Πολιτειών και η Αμερικανική Φιλοσοφική Εταιρεία.

Το 1951, ο Kurt Gödel τιμήθηκε με το υψηλότερο επιστημονικό βραβείο στις Ηνωμένες Πολιτείες, το Βραβείο Einstein. Σε ένα άρθρο αφιερωμένο σε αυτό το γεγονός, ένας άλλος από τους μεγαλύτερους μαθηματικούς της εποχής μας, ο John von Neumann, έγραψε: «Η συμβολή του Kurt Gödel στη σύγχρονη λογική είναι πραγματικά μνημειώδης. Αυτό είναι κάτι περισσότερο από ένα απλό μνημείο. Αυτό είναι ένα ορόσημο που χωρίζει δύο εποχές... Μπορεί να ειπωθεί χωρίς καμία υπερβολή ότι το έργο του Gödel άλλαξε θεμελιωδώς το ίδιο το θέμα της λογικής ως επιστήμης.

Πράγματι, ακόμη και ένας ξερός κατάλογος των επιτευγμάτων του Γκόντελ στη μαθηματική λογική δείχνει ότι ο συγγραφέας τους ουσιαστικά έθεσε τα θεμέλια για ολόκληρα τμήματα αυτής της επιστήμης: η θεωρία των μοντέλων (1930· το λεγόμενο θεώρημα για την πληρότητα του στενού κατηγορηματικού λογισμού, που δείχνει: χονδρικά μιλώντας, η επάρκεια των μέσων της «επίσημης λογικής» για να αποδείξει όλες τις αληθινές προτάσεις που εκφράζονται στη γλώσσα της), η εποικοδομητική λογική (1932–1933· έχει ως αποτέλεσμα τη δυνατότητα αναγωγής ορισμένων κατηγοριών προτάσεων κλασικής λογικής στις αντίστοιχες διαισθητικές τους, οι οποίες έθεσαν το θεμέλιο για τη συστηματική χρήση των «εργασιών εμβάπτισης» που επιτρέπουν μια τέτοια μείωση των διαφόρων λογικά συστήματαο ένας τον άλλον), επίσημη αριθμητική (1932–1933· αποτελέσματα σχετικά με τη δυνατότητα αναγωγής της κλασικής αριθμητικής σε διαισθητική αριθμητική, δείχνοντας κατά μία έννοια τη συνέπεια της πρώτης σε σχέση με τη δεύτερη), τη θεωρία των αλγορίθμων και των αναδρομικών συναρτήσεων (1934· ορισμός της έννοιας μιας γενικής αναδρομικής συνάρτησης, που έπαιξε ΚΑΘΟΡΙΣΤΙΚΟΣ ΡΟΛΟΣστον καθορισμό της αλγοριθμικής αδιαλυτότητας της σειράς κρίσιμα ζητήματαμαθηματικά αφενός. Και στην υλοποίηση λογικών και μαθηματικών προβλημάτων σε ηλεκτρονικούς υπολογιστές - από την άλλη πλευρά, η αξιωματική θεωρία συνόλων (1938· απόδειξη της σχετικής συνέπειας του αξιώματος της επιλογής και η υπόθεση του συνεχούς του Cantor από τα αξιώματα της θεωρίας συνόλων, που σηματοδότησε την αρχή της σειράς βασικά αποτελέσματασχετικά με τη σχετική συνέπεια και την ανεξαρτησία των αρχών της θεωρίας συνόλων).

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

Εισαγωγή

Το 1931, σε ένα από τα γερμανικά επιστημονικά περιοδικάεμφανίστηκε μια σχετικά σύντομη εργασία με τον μάλλον τρομακτικό τίτλο "On Formally Undecidable Propositions of Principia Mathematica and Related Systems". Ο συγγραφέας του ήταν ένας εικοσιπεντάχρονος μαθηματικός από το Πανεπιστήμιο της Βιέννης, ο Kurt Gödel, ο οποίος αργότερα εργάστηκε στο Ινστιτούτο Προηγμένων Μελετών του Πρίνστον. Αυτό το έργο έπαιξε καθοριστικό ρόλο στην ιστορία της λογικής και των μαθηματικών. Στην απόφαση πανεπιστήμιο Χάρβαρνταπονέμοντας στον Gödel επίτιμο διδάκτορα (1952), χαρακτηρίστηκε ως μία από τις τα μεγαλύτερα επιτεύγματασύγχρονη λογική.

Ωστόσο, τη στιγμή της δημοσίευσης, κανένας τίτλος του έργου του Gödel. Ούτε το περιεχόμενό του είπε τίποτα στους περισσότερους μαθηματικούς. Αναφέρεται στον τίτλο του, το Principia Mathematica είναι η μνημειώδης τρίτομη πραγματεία των Alfred North Whitehead και Bertrand Russell για τη μαθηματική λογική και τα θεμέλια των μαθηματικών. εξοικείωση με την πραγματεία δεν ήταν σε καμία περίπτωση απαραίτητη προϋπόθεσηΓια επιτυχημένη δουλειάστους περισσότερους κλάδους των μαθηματικών. Το ενδιαφέρον για τα ζητήματα που εξετάζονται στο έργο του Gödel ήταν πάντα το ενδιαφέρον μιας πολύ μικρής ομάδας επιστημόνων. Ταυτόχρονα, τα επιχειρήματα που έδωσε ο Gödel στις αποδείξεις του ήταν τόσο ασυνήθιστα για την εποχή τους. Ότι η πλήρης κατανόησή τους απαιτούσε αποκλειστική γνώση του θέματος και εξοικείωση με τη βιβλιογραφία που ήταν αφιερωμένη σε αυτά τα πολύ συγκεκριμένα προβλήματα.

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

Το πρώτο θεώρημα μη πληρότητας του Gödelφαίνεται να είναι το πιο σημαντικό αποτέλεσμα στη μαθηματική λογική. Ακούγεται κάπως έτσι:

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

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

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

Το πρώτο θεώρημα της μη πληρότητας τιτλοφορήθηκε "Θεώρημα VI" στην εργασία του Gödel το 1931. Σχετικά με τις τυπικά αδιευκρίνιστες προτάσεις στο Principia Mathematica και τα σχετικά συστήματα I. Στην αρχική ηχογράφηση του Gödel, ακουγόταν ως εξής:

«Το γενικό συμπέρασμα σχετικά με την ύπαρξη αναποφάσιστων προτάσεων είναι το εξής:

Θεώρημα VI .

Για κάθε ω-συνεπή αναδρομική κλάση kΤΥΠΟΣ υπάρχουν αναδρομικέςΣΗΜΑΔΙΑ r τέτοια που ούτε (vΓεν r), ούτε ¬( vΓεν r)δεν ανήκουν στη Φλγ (κ)(όπου είναι vΔΩΡΕΑΝ ΜΕΤΑΒΛΗΤΗ r ) ».

Ονομασία Flgπροέρχεται από αυτόν. Folgerungsmenge- σύνολο ακολουθιών, Γενπροέρχεται από αυτόν. γενίκευση- γενίκευση.

Σε γενικές γραμμές, η δήλωση Gödel σολισχυρίζεται: «αλήθεια σολδεν μπορεί να αποδειχθεί». Αν σολθα μπορούσε να αποδειχθεί μέσα στη θεωρία, τότε η θεωρία θα περιέχει ένα θεώρημα που έρχεται σε αντίθεση με τον εαυτό της, και επομένως η θεωρία θα ήταν ασυνεπής. Αλλα αν σολαναπόδεικτο, τότε είναι αλήθεια, και επομένως η θεωρία είναι ελλιπής (η δήλωση σολδεν συνάγεται σε αυτό).

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

Το δεύτερο θεώρημα της μη πληρότητας του Gödel

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

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

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

Πολλοί προσπάθησαν να χρησιμοποιήσουν αυτό το θεώρημα για να αποδείξουν ότι η ευφυής δραστηριότητα δεν μπορεί να αναχθεί σε υπολογισμούς. Για παράδειγμα, το 1961, ο διάσημος λογικός John Lucas σκέφτηκε ένα παρόμοιο πρόγραμμα. Το σκεπτικό του αποδείχθηκε αρκετά ευάλωτο - ωστόσο, έθεσε το καθήκον ευρύτερα. Ο Roger Penrose ακολουθεί μια ελαφρώς διαφορετική προσέγγιση, η οποία παρουσιάζεται στο βιβλίο εντελώς, «από την αρχή».

Συζητήσεις

Οι συνέπειες των θεωρημάτων επηρεάζουν τη φιλοσοφία των μαθηματικών, ειδικά εκείνους τους φορμαλισμούς που χρησιμοποιούν τυπική λογικήνα καθορίσουν τις αρχές τους. Κάποιος μπορεί να επαναδιατυπώσει το πρώτο θεώρημα της μη πληρότητας ως εξής: είναι αδύνατο να βρεθεί ένα ολοκληρωμένο σύστημα αξιωμάτων που θα μπορούσε να αποδείξει όλαμαθηματικές αλήθειες και όχι ένα ψέμα". Από την άλλη πλευρά, από τη σκοπιά της αυστηρής τυπικότητας, αυτή η αναδιατύπωση δεν έχει πολύ νόημα, καθώς προϋποθέτει ότι οι έννοιες του «αληθούς» και του «ψευδούς» ορίζονται με απόλυτη έννοια, παρά με σχετική κάθε συγκεκριμένο σύστημα.