January 13, 2012

Θεώρημα Goodstein ή άθλος ?




Όσοι-ες δεν έχετε "έκνομη" ή έστω "ρομαντική" σχέση με τα Μαθηματικά .. μην αποθαρρυνθείτε. Η ουσία της παρούσας ανάρτησης δεν βρίσκεται στις μαθηματικές λεπτομέρειες !

Ξεκινάμε με κάποιο τυχαίο αριθμό n, ας πούμε το  .. 42. Μπορούμε να γράψουμε τo 42 με βάση τον αριθμό 2, ως εξής: 42 = 25 + 23 + 2.  Αν γράψουμε και τους εκθέτες με βάση το 2,  τότε έχουμε:  a2 =  42 = 222+1 + 22 +1 +2. Ο τρόπος αυτός ονομάζεται  ανάπτυγμα του αριθμού σε υπέρβαση 2. Πρακτικά αυτό σημαίνει ότι γράφουμε το 42 με δυάρια καί άσσους.

Τώρα, αν αντικαταστήσουμε το κάθε 2 με το 3, θα δημιουργηθεί ο αριθμός 333+1 + 33+1 + 3, που προφανώς είναι  πολύ μεγαλύτερος του 42. Αφαιρώντας το 1 ορίζουμε έναν άλλο αριθμό, τον  a3.

Στη συνέχεια, αφού πρώτα γράψουμε τον αριθμό a3 αναπτύσοντάς τον σε υπέρβαση 3, αντικαθιστούμε το κάθε 3 με 4 και αφαιρούμε πάλι το 1 από την τελική απάντηση. Αυτός ο αριθμός είναι ο a4. Με αυτό τον απλό τρόπο κατασκευάζουμε μιά σειρά αριθμών a2, a3, a4, a5 ... κλπ - την περίφημη ακολουθία Goodstein, που σ' αυτή τη περίπτωση ξεκίνησε με τον αριθμό 42.

Διαισθητικά οι περισσότεροι άνθρωποι  συμπεραίνουν ότι οι αριθμοί (όροι) αυτής της ακολουθίας αυξάνονται εκρηκτικά και χωρίς σταματημό !

Η τρομακτική αύξηση της τάξης μεγέθους  των πέντε πρώτων όρων της ακολουθίας Goodstein - για έναν άλλο αρχικό αριθμό (πχ το 26) - φαίνεται στο επόμενο ενδεικτικό παράδειγμα:

a2 = 222 + 22+1 +  2 = 26

a3 = (333 + 33+1 + 3) - 1 = 333 + 33+1 + 2 ~ 1013

a4 = (444 + 44+1 + 2) - 1 = 444 + 44+1 + 1 ~ 10154

a5 = (555 + 55+1 + 1) - 1 = 555 + 55+1 ~ 102184

a6 = (666 + 66+1) - 1 = 666 + 66+1 - 1 ~ 1036305

Όμως, ρίξτε μιά ματιά στο παρακάτω θεώρημα:

Θεώρημα Goodstein: Για οποιοδήποτε αρχικό αριθμό n, η σειρά Goodstein ξεκινά με το n και τερματίζει στο 0 (μηδέν!) μετά από πεπερασμένο αριθμό βημάτων !

Το .. σοκ δεν σταματάει εδώ!  Το 1982 οι Kirby και Paris απέδειξαν ότι το εν λόγω θεώρημα ΔΕΝ  αποδεικνύεται με πρωτοβάθμια αριθμητική, επειδή δεν μπορούμε να περιγράψουμε με αυστηρότητα την εξέλιξη της εκθετικής δομής των όρων μιας ακολουθίας Goodstein στο πλαίσιο της αριθμητικής Peano. To θεώρημα αποδεικνύεται με την επέκταση της περιγραφικής διαδικασίας στη δευτεροβάθμια αριθμητική των διατακτικών (Ο μαθηματικός ξέρει για τι μιλάει - απόδειξη σελ. 28 !)

Επιπλέον οι Kirby και Paris επινόησαν το παχνίδι της Λερναίας Ύδρας. Αντί για το μυθικό όν του Ηρακλή η δική τους Ύδρα είναι ένα δένδρο. Ο κάθε επίδοξος Ηρακλής αποκόπτει κάποια απ' τις  "κεφαλές", δηλαδή ένα κλάδο του δένδρου.  Η Ύδρα απαντά με το "φύτρωμα" πεπερασμένου αριθμού κεφαλών, σύμφωνα με ορισμένους κανόνες. Με την ίδια λογική (σελ. 24) της προαναφερθείσας απόδειξης του θεωρήματος Goodstein, οι Kirby και Paris απέδειξαν ότι τελικά η Ύδρα θα σκοτωνόταν οπωσδήποτε, οποιαδήποτε στρατηγική κι' αν επέλεγε ο Ηρακλής !!!

Υπό το φως του νέου δεδομένου τίθεται το αμείλικτο ερώτημα: Μήπως είναι υπερβολή να μιλάμε για .. άθλο ?


ΥΓ1. Αποκεφαλίστε την δική σας "αφηρημένη" Ύδρα .. εδώ !

ΥΓ2. Για μία κομψή και "εύκολη" απόδειξη από τον John Findlay (1941) του εκπληκτικού Θεωρήματος της "μη πληρότητας" του Kurt Gödel, βλ. σελ. 8 του  προαναφερθέντος συνδέσμου. Είναι διατυπωμένη για την φιλοσοφική εκτίμηση του θέματος και συνεπώς μπορούν να την κατανοήσουν ακόμη και .. φιλόλογοι!

ΥΓ3. Κλικάρετε άνευ .. δισταγμού τα 13 links και τις 2 εικόνες

:)


7 comments:

ria said...

μέχρι τη μέση την παρακολούθησα την άναρτηση. μετά το έχασα...

negentropist said...

Tότε να σε .. διευκολύνω ria :)

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

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

«a politician is an arse upon which everyone has sat except a man» (πολιτικός είναι ένας κώλος που απάνω του ο καθείς έχει καθήσει εκτός από ανθρώπους),

τότε αρκετοί σ΄αυτή τη χώρα ΙΣΩΣ να μην επέτρεπαν στους κάθε λογής "ταγούς" να τους αποκεφαλίζουν/ευνουχίζουν σε καθημερινή βάση !

Θέλω να ελπίζω ότι το καλοκαίρι είναι μέσα μας (με την .. Επικούρεια έννοια !)

Reflections of a dream

:)

to alataki said...

Για τιμωρία σου...
Η σιωπή μου προς απάντησίν σου...

(δηλαδή, όχι ότι δεν μπορώ να σε βάλω στη θέση σου απλά δεν... καταδέχομαι. Χα!)

negentropist said...

Άκαρδο κορίτσι !

Ελπίζω να .. εξιλεωθώ κάπως με τα υπέροχα χρώματα του Leonid Afremov και τη φανταστική φωνή της Jane Monheit (δύο σε ένα αγαπητή Ιωάννα!)

Stormy Weather

:)

Alex said...

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

negentropist said...

Όλοι "χανόμαστε" αρκετές φορές Alex!

Xάθηκα

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

:)

negentropist said...

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

Eνώ η πρόσθεση και ο πολ-σμός είναι προσεταιριστικές πράξεις - για παράδειγμα (2+3)+4 = 9 = 2+(3+4) και (2·3)·4 = 24 = 2·(3·4) - η ύψωση σε δύναμη δεν είναι !

Πχ το 2^3 στην 4η κάνει 8^4 ή 4096, ενώ το 2 στην 3^4 κάνει 2^81 ή 2.417.851.639.229.258.349.412.352 !

Όταν δεν υπάρχουν παρενθέσεις ώστε να τροποποιήσουν την ιεραρχία των υπολογισμών, η σειρά εκλαμβάνεται συνήθως από πάνω προς τα κάτω και όχι το ανάποδο !

Πχ το a^b^c = a^(b^c) διαφέρει από το (a^b)^c = a^(b.c)

:)