Μη πληρότητα-Γκολντμπαχ

[George_F]

Διαβάζω αυτή την εποχή για την ζωή και το έργο του Κουρτ Γκεντελ, αυτού του μεγάλου μαθηματικού που φαντάζομαι οι περισσότεροι έχετε ακουστά. Για να μην μακρηγορώ ο Γκέντελ επινόησε και απέδειξε τα δυο περίφημα θεωρήματα της μη πληρότητας των μαθηματικών καταρρίπτοντας τα σχέδια του Χίλμπερτ για την απόδειξη του 2ου άλυτου προβλήματος όπως το είχε παρουσιάσει στο συνέδριο στην Γαλλία κατά τον 20ο αιώνα(ο Χίλμπερτ συνέταξε και παρουσίασε τα 20 άλυτα προβλήματα που θα απασχολήσουν τους μαθηματικούς στο μέλλον, το 2ο στην λίστα το οποίο αναφέρεται στην συμβατότητα των αριθμητικών αξιωμάτων). Η γενική ιδέα των δυο αυτών θεωρημάτων είναι ότι μια μαθηματική πρόταση μπορεί να είναι αληθής αλλά μη αποδείξιμη, βέβαια δυστυχώς δεν μπορούμε εξ αρχής να ξέρουμε αν ένα πρόβλημα εμπίπτει στην περίπτωση Γκέντελ , όπως για παράδειγμα πριν την απόδειξη του Τελευταίου θεωρήματος του Φερμά κανείς δεν ήξερε αν όντως θα μπορούσε να αποδειχθεί μέχρι που το '91 έφερε την απόδειξη του ο Ουάλις.

Η ερώτηση μου προς εσάς είναι θεωρείτε ότι υπάρχει περίπτωση η Εικασία του Γκόλντμπαχ* που δεν γνωρίζουμε αν εμπίπτει ή όχι στην περίπτωση Γκέντελ να αποδειχθεί τα επόμενα χρόνια παρ' ότι ένα από τα παλιότερα άλυτα προβλήματα της θεωρίας αριθμών και γενικότερα των μαθηματικών?

*(Κάθε άρτιος θετικός ακέραιος μεγαλύτερος του 2 μπορεί να γραφεί ως άθροισμα δύο πρώτων αριθμών, έτσι ώστε για κάθε n ≧ 2, 2n = p + q, όπου p, q πρώτοι αριθμοί.)

Ευχαριστώ.

[ΔΗΜΗΤΡΗΣ ΙΩΑΝΝΟΥ]

Η ερώτηση μου προς εσάς είναι θεωρείτε ότι υπάρχει περίπτωση η Εικασία του Γκόλντμπαχ* που δεν γνωρίζουμε αν εμπίπτει ή όχι στην περίπτωση Γκέντελ να αποδειχθεί τα επόμενα χρόνια παρ' ότι ένα από τα παλιότερα άλυτα προβλήματα της θεωρίας αριθμών και γενικότερα των μαθηματικών?

*(Κάθε άρτιος θετικός ακέραιος μεγαλύτερος του 2 μπορεί να γραφεί ως άθροισμα δύο πρώτων αριθμών, έτσι ώστε για κάθε n ≧ 2, 2n = p + q, όπου p, q πρώτοι αριθμοί.)

Ευχαριστώ.

Ποτέ μην λες ΠΟΤΕ!!!

Πάντως αν κάποτε αποδειχθεί, θα είναι το γεγονός της χρονιάς...

[Ακριβη]

Η απάντηση ίσως ειναι ευνόητη, ίσως και όχι.Απανταω όμως, και θα σας παρακαλούσα να λαβέ ταξί υπ'οψιν ότι είμαι 13.
"Πρέπει να μάθουμε.Θα μάθουμε". Το θεώρημα μη πληρότητας του Γκεντελ ειναι μια απόδειξη, δεν δηλώνει όμως πως εάν τα μαθηματικά προχωρήσουν θα ειναι αδύνατη η απόδειξη.Αρα, επειδή, κατα την άποψη μου, τα μαθηματικά, ως ορισμός της τελειότητας, αποδυκνειουν τα πάντα, η εν λόγω εικασία ειναι αποδειξιμη.Ας μην ξεχάσαμε πως το τελ.θεωρημα του Φερμα αποδείχθηκε χρόνια μετά απο τον θάνατο του.

[Ακριβη]

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

[ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ]

Μην ανησυχείς .Δεν πρόκειται να ξεμείνουμε από άλυτα προβλήματα.
Αυτός είναι ένας κατάλογος
https://en.wikipedia.org/wiki/List_of_u ... athematics
Υπάρχουν και άλλοι.

[grigkost]

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

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

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

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

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

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



Παρατήρηση: Στα παραπάνω θεωρείται δεδομένη (προφανής) η συνέπεια ενός τυπικού αξιωματικού συστήματος που περιέχει την αριθμητική.

[stranger]

Μερικές σκέψεις μου πάνω σε αυτό το θέμα.Καταρχήν κάπου αναφέρεται ότι "δεν μπορούμε να ξέρουμε αν μια πρόταση εμπίπτει στη μη πληρότητα των μαθηματικών".Αυτό είναι λάθος.Για παράδειγμα ξέρουμε ότι η υπόθεση του συνεχούς εμπίπτει στη μη πληρότητα της ZFC. Βέβαια μπορεί επόμενες γενιές μαθηματικών να βρούνε άλλες προτάσεις που η αλήθεια τους να είναι προφανής και να τις προσθέσουνε σαν αξιώματα και έτσι να μπορεί να αποφασιστεί αν η υπόθεση του συνεχούς ισχύει η όχι.Ο πιο συνηθησμένος τρόπος να αποδείξεις ότι μια πρόταση εμπίπτει στη μη πληρότητα είναι να κατασκευάσεις δυο μοντέλα των αξιωμάτων που στο πρώτο να μην ισχύει η πρόταση και στο δεύτερο να ισχύει.Αυτός είναι ο μόνος τρόπος να είναι μη αποδείξιμη μια πρόταση,γιατί το θεώρημα πληρότητας του Godel λέει ότι μια πρόταση αποδεικνύεται από τα αξιώματα αν και μονο αν ισχύει σε όλα τα μοντέλα των αξιωμάτων.Προσωπικά θεωρώ πιο σημαντικό το θεώρημα πληρότητας του Godel από το θεώρημα μη πληρότητας.
Τώρα για την εικασία του Goldbach αν εμπίπτει στη μη πληρότητα των μαθηματικών αυτο σημαίνει ότι ισχύει στους "αληθινούς" φυσικούς αριθμούς.Αυτό γιατι αν δεν ισχύει σημαίνει ότι υπάρχει αντιπαράδειγμα που μπορεί να βρεθεί,οποτε δεν μπορεί να εμπίπτει στη μη πληρότητα.
Το ίδιο ισχύει και για την υπόθεση του Riemann.Βέβαια αν εμπίπτει στη μη πληρότητα τότε θα υπάρχουν δυο μοντέλα των φυσικών αριθμών που στο ένα ισχύει και στο άλλο δεν ισχύει.Όμως αν συμβαίνει αυτό τότε ξέρουμε ότι ισχύει στο μοντέλο των "αληθινών" φυσικών αριθμών(true arithmetic).

[Demetres]

Αυτό γιατι αν δεν ισχύει σημαίνει ότι υπάρχει αντιπαράδειγμα που μπορεί να βρεθεί,οποτε δεν μπορεί να εμπίπτει στη μη πληρότητα.
Το ίδιο ισχύει και για την υπόθεση του Riemann.

Για την Goldbach ναι αλλά για την Riemann όχι. Για την Riemann μπορεί να υπάρχει αντιπαράδειγμα το οποίο να μην μπορεί να βρεθεί.

[stranger]

Νομίζω πως κάνεις λάθος.Η υπόθεση του Riemann είναι ισοδύναμη με την πρόταση ότι για κάθε .Οπότε αν υπάρχει αντιπαράδειγμα σε αυτή την πρόταση τότε μπορεί να βρεθεί.
Για περισσότερες πληροφορίες δες εδώ: http://mathworld.wolfram.com/RobinsTheorem.html

[Demetres]

Νομίζω πως κάνεις λάθος.Η υπόθεση του Riemann είναι ισοδύναμη με την πρόταση ότι για κάθε .Οπότε αν υπάρχει αντιπαράδειγμα σε αυτή την πρόταση τότε μπορεί να βρεθεί.
Για περισσότερες πληροφορίες δες εδώ: http://mathworld.wolfram.com/RobinsTheorem.html

Δεν το γνώριζα το συγκεκριμένο. Με αυτό ναι έχει δίκαιο ότι αν δεν ισχύει η εικασία τότε μπορούμε να την απορρίψουμε με αντιπαράδειγμα (το οποίο θεωρητικά μπορούμε να το βρούμε). Έχω ένα μικρό ενδοιασμό στην απίθανη περίπτωση που για κάποιο ισχύει η ισότητα.

[stranger]

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

[stranger]

Η υπόθεση του Riemann είναι ψευδής αν και μόνο αν για κάποιο . Οπότε δεν χρειάζεται να ανησηχούμε για την περίπτωση που ισχύει η ισότητα γιατί αν η υπόθεση του Riemann είναι ψευδής μπορούμε πάντα να βρούμε τέτοιο επειδή πάντα μπορούμε να έρθουμε όσο κοντά θέλουμε στους αριθμούς και με έναν υπολογιστή.
Η απόδειξη χρησιμοποιεί το θεώρημα του Lagarias που λέει:
Η υπόθεση του Riemann είναι ισοδύναμη με την πρόταση για κάθε όπου που είναι είναι ισοδύναμη με την για κάθε αφού έχει ελεγθεί για τους αριθμούς απο 1 μέχρι 5041.
Επίσης είναι εύκολο να δείξουμε ότι για κάθε .
Οπότε αν η υπόθεση του Riemann είναι ψευδής τότε υπάρχει ώστε .

Ερώτηση : Αν η υπόθεση του Riemann αποδειχθεί μη αποδείξιμη θα το δεχόσασταν ως απόδειξη ότι ισχύει?

[Demetres]

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

Ερώτηση : Αν η υπόθεση του Riemann αποδειχθεί μη αποδείξιμη θα το δεχόσασταν ως απόδειξη ότι ισχύει?

Ελπίζω να μην λέω κοτσάνες στα πιο κάτω μιας και μπαίνουμε σε δύσκολα χωράφια.

Φαντάζομαι εννοείς μη αποφασίσιμη (undecidable) και όχι μη αποδείξιμη. Από τα πιο πάνω, σίγουρα είναι αποφασίσιμη αν δεν ισχύει. Άρα μέσα στην ZF δεν μπορούμε να δείξουμε (*) ότι είναι μη αποφασίσιμη αφού αν το δείξουμε, αυτομάτως θα ισχύει και άρα θα είναι και αποφασίσιμη.

(*) Εκτός βέβαια και αν η ZF δεν είναι consistent αφού σε αυτήν την περίπτωση μπορούμε να δείξουμε τα πάντα.

Αν τώρα δείξουμε σε κάποιο άλλο πιο ισχυρό σύστημα ότι «Η υπόθεση Riemann δεν είναι αποφασίσιμη στην ZF» τότε αυτό ίσως να επιτρέπεται. Σε αυτήν την περίπτωση νομίζω πρέπει να δεχθούμε ότι η υπόθεση Riemann είναι αληθής. Ίσως να εξαρτάται και από την πίστη μας κατά πόσο αυτό το πιο ισχυρό σύστημα είναι consistent ή όχι.

[stranger]

Άρα μέσα στην ZF δεν μπορούμε να δείξουμε (*) ότι είναι μη αποφασίσιμη αφού αν το δείξουμε, αυτομάτως θα ισχύει και άρα θα είναι και αποφασίσιμη.

(*) Εκτός βέβαια και αν η ZF δεν είναι consistent αφού σε αυτήν την περίπτωση μπορούμε να δείξουμε τα πάντα.

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