Το προφίλ μας στο Google Plus
10

Φτάνουν 4 χρώματα, για όλους τους χάρτες του κόσμου;

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

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

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

Είναι εύκολο να δειχτεί ότι τρία χρώματα δεν αρκούν για έναν ανάλογο χρωματισμό περιοχών του επιπέδου. Για να το δούμε αυτό αρκεί να σχεδιάσουμε μια περιοχή που περικλείεται από περιττό αριθμό περιοχών, οι οποίες συνορεύουν κυκλικά. Έχει ήδη αποδειχτεί, εξάλλου, πως πέντε χρώματα αρκούν για το ζητούμενο τρόπο χρωματισμού. Όμως η απόδειξη για την επάρκεια ή όχι των τεσσάρων χρωμάτων χρειάστηκε πάνω από έναν αιώνα για να ξεκαθαρίσει! Μάλιστα αν δεν επιστρατεύονταν υπολογιστές, ίσως ακόμη και σήμερα τα πράγματα να ήταν… θολά.

Αναγνώριση
Η υπόθεση των τεσσάρων χρωμάτων διατυπώθηκε για πρώτη φορά το 1852 από τον Francis Guthrie, όταν επιχειρώντας να χρωματίσει τις κομητείες της Αγγλίας διαπίστωσε πως τέσσερα χρώματα είναι αρκετά, έτσι ώστε κάθε κομητεία να έχει το δικό της χρώμα και γειτονικές κομητείες να έχουν διαφορετικά χρώματα. Την εποχή εκείνη ο Francis ήταν μαθητής του μαθηματικού και λογικολόγου Augustus De Morgan, στο University College του Λονδίνου. Ο Francis ανέφερε την παρατήρησή του στο μικρότερο αδελφό του, Frederick Guthrie, εικάζοντας πως τέσσερα χρώματα αρκούν για κάθε χάρτη. Αργότερα, όταν ο Francis είχε πάψει να παρακολουθεί τα μαθήματα του De Morgan και κρατούσε θέση μαθηματικού στο Πανεπιστήμιο της Νοτίου Αφρικής, στο Κέιπ Τάουν, ήταν η σειρά του αδελφού του να παρακολουθήσει τον De Morgan. Με την άδεια του Francis, ο Frederick Guthrie γνωστοποίησε στον De Morgan το θεώρημα των τεσσάρων χρωμάτων, μαζί με μια απόδειξη που είχε κατασκευάσει ο μεγαλύτερος αδελφός του.

Ο De Morgan ενθουσιάστηκε με την υπόθεση αλλά βρήκε ανεπαρκή την απόδειξη. Στις 23 Οκτωβρίου του 1852 έγγραψε ένα γράμμα στον φίλο του William Rowan Hamilton, διακεκριμένο Ιρλανδό μαθηματικό και φυσικό, επιχειρώντας να στρέψει την προσοχή του συναδέλφου του στο άκρως ενδιαφέρον, όπως ο ίδιος το εύρισκε, θεώρημα των τεσσάρων χρωμάτων. Ο De Morgan ήλπιζε σε μια θετική αντίδραση από τον Hamilton, ενδεχομένως και σε μια απόδειξη του θεωρήματος. Όμως η στάση του Hamilton ήταν αποκαρδιωτική, αφού στην απάντησή του ξεκαθάρισε πως δεν σκόπευε να ασχοληθεί με το πρόβλημα. Ο De Morgan δεν παραιτήθηκε και βάλθηκε να παρακινήσει το ενδιαφέρον άλλων επιστολογράφων του. Μεταξύ άλλων, γνωστοποίησε το πρόβλημα των τεσσάρων χρωμάτων στον διακεκριμένο φιλόσοφο William Whewell και στον μαθηματικό Robert Ellis.

Η πρώτη γνωστή εμφάνιση του προβλήματος των τεσσάρων χρωμάτων σχετίζεται με μια εργασία του Whewell. Στις 14 Απριλίου του 1860, ένας ανώνυμος κριτικός του βιβλίου “Η φιλοσοφία της ανακάλυψης”, του Whewell, αναφέρθηκε στο πρόβλημα σχολιάζοντας πως ήταν ήδη γνωστό στους χαρτογράφους! Προσεκτική μελέτη του εν λόγω κειμένου φανερώνει ότι ο ανώνυμος κριτικός ήταν ο ίδιος ο Augustus De Morgan. Η κριτική του διέσχισε τον Ατλαντικό, φτάνοντας στα χέρια του Αμερικανού μαθηματικού, λογικολόγου και φιλοσόφου Charles Sanders Peirce. Ο Peirce ενδιαφέρθηκε αμέσως για το πρόβλημα των τεσσάρων χρωμάτων και δεν έπαψε να ασχολείται με αυτό για το υπόλοιπο της ζωής του.

Αντίσταση
Μετά τον θάνατο του Augustus De Morgan, το 1871, ο Charles Senders Peirce συνέχισε να ασχολείται με το πρόβλημα των τεσσάρων χρωμάτων — όμως χωρίς επιτυχία. Στην Ευρώπη, πάλι, κανένας ερευνητής δεν έδινε σημασία στο πρόβλημα. Κανένας εκτός από το λαμπρό μαθηματικό Arthur Cayley, έναν από τους ανιψιούς του εφευρέτη και πιονέρου αεροπόρου Sir George Cayley. Στον Arthur Cayley οφείλεται η πρώτη επίσημη έγγραφη αναφορά του προβλήματος, στην εργασία του “Περί του χρωματισμού χαρτών”, που κατέθεσε στη Βασιλική Γεωγραφική Υπηρεσία του Λονδίνου το 1879. Στην εργασία, ο Cayley παραδέχτηκε ότι απέτυχε να κατασκευάσει μια γενική απόδειξη της υπόθεσης.

Όμως ο Cayley δεν ήταν ο μόνος που είχε δυσκολίες με το πρόβλημα των τεσσάρων χωμάτων. Μεταξύ των ανθρώπων που ασχολήθηκαν με το πρόβλημα κι απέτυχαν ήταν ο Λονδρέζος δικηγόρος κι ερασιτέχνης μαθηματικός Alfred Bray Kempe. Η περίπτωση του Kempe έχει ιδιαίτερο ενδιαφέρον, αφού χρειάστηκαν έντεκα χρόνια για να ανακαλυφθεί ότι η απόδειξη που πρότεινε ήταν, απλά, λανθασμένη! Μολαταύτα, η “λύση” του Kempe περιελάμβανε ένα πλήθος πρωτότυπων ιδεών που αργότερα απεδείχθησαν πολύτιμες για την οριστική αντιμετώπιση του προβλήματος.

Η καρδιά της απόδειξης του Kempe βασιζόταν στην εξέταση ενός συνόλου με μόλις τέσσερις “αναπόφευκτους” σχηματισμούς περιοχών, οι οποίοι εμφανίζονται σε κάθε κανονικό χάρτη. Ως “κανονικός” ορίζεται ένας χάρτης στον οποίο α) σε κανένα σημείο δεν συναντώνται περισσότερες από τρεις περιοχές και β) καμία περιοχή δεν περικλείει εξολοκλήρου κάποια άλλη. Με δεδομένο ότι κάθε χάρτης μπορεί να αναχθεί σε έναν κανονικό, που απαιτεί τουλάχιστον το ίδιο πλήθος χρωμάτων, είναι προφανές ότι η εικασία των τεσσάρων χρωμάτων αρκεί να αποδειχτεί μόνο για κανονικούς χάρτες. Ο Kempe δημοσίευσε την εργασία του το 1879. Δυστυχώς η σχετική απόδειξη εμπεριείχε ένα σημαντικό συλλογιστικό λάθος, το οποίο εντόπισε το 1890 ο Percy John Heawood.

Βαρύ πυροβολικό
Από το 1890 έως το 1976 η υπόθεση των τεσσάρων χρωμάτων συγκαταλεγόταν στα εξέχοντα, άλυτα μαθηματικά προβλήματα. Τελικά, τη λύση έδωσαν οι μαθηματικοί Kenneth Appel και Wolfgang Haken, του πανεπιστημίου του Ιλινόις. Αν και η δουλειά τους στηρίχτηκε στις ιδέες του Kempe, αντί για τέσσερις μόλις σχηματισμούς χρειάστηκε να εξετάσουν ένα σύνολο από 1936, πολλοί από τους οποίους ήταν ιδιαίτερα πολύπλοκοι. Έτσι, η ολοκλήρωση της απόδειξης κατέστη δυνατή μόνο με χρήση ενός γρήγορου (για τα δεδομένα του 1976) υπολογιστή, ο οποίος για αρκετές ώρες έλεγχε έναν προς έναν όλους τους σχηματισμούς. Η τυπωμένη απόδειξη των αποτελεσμάτων ξεπερνούσε τις 500 σελίδες. Μετά από εξονυχιστικούς, εξαντλητικούς ελέγχους, οι Appel και Haken δημοσίευσαν τα αποτελέσματα της εργασίας τους. Εξαιτίας της γοητείας του προβλήματος των τεσσάρων χρωμάτων, αλλά κυρίως λόγω της επιστράτευσης υπολογιστή για την παραγωγή μιας μαθηματικής απόδειξης, η δημοσιότητα του γεγονότος ξέφυγε από τους στενούς μαθηματικούς κύκλους, σε βαθμό που οι ίδιοι οι New York Times έγραψαν για το θέμα. Το 1996 οι Neil Robertson, Daniel Sanders, Paul Seymour και Robin Thomas ανακοίνωσαν μία απόδειξη παρόμοια με εκείνη των Appel – Haken, η οποία όμως απαιτούσε την εξέταση 633 σχηματισμών. Μολαταύτα, η χρήση υπολογιστή ήταν και σε αυτή την περίπτωση επιβεβλημένη. Τέλος, το 2004 οι Benjamin Werner και Georges Gonthier τυποποίησαν μία απόδειξη για το θεώρημα των τεσσάρων χρωμάτων μέσα στα πλαίσια του αυτοματοποιημένου συστήματος αποδείξεων Coq. Η συγκεκριμένη προσέγγιση δεν απαιτεί από τον μελετητή να εμπιστευτεί προγράμματα που ελέγχουν σχηματισμούς, απαιτεί όμως εμπιστοσύνη στην ορθή λειτουργία του Coq!

Είναι οι υπολογιστές άξιοι για μαθηματικά;
Οι αντιδράσεις μετά την ανακοίνωση για την απόδειξη της υπόθεσης των τεσσάρων χρωμάτων ήταν ποικίλες. Σε γενικές γραμμές, στις τάξεις των μαθηματικών αλλά και των φιλοσόφων επικράτησε σκεπτικισμός. Είναι σωστό να θεωρείται μαθηματική απόδειξη κάτι που παρήχθη από μια μηχανή και, πρακτικά, μόνο από μηχανή μπορεί να επαληθευτεί; Γιατί να εμπιστευτούμε τον υπολογιστή; Οι μαθηματικές αποδείξεις διακρίνονται από την κομψότητα και την οικονομία, στοιχεία που απουσίαζαν παντελώς από την εργασία των Kenneth Appel και Wolfgang Haken. Όπως χαρακτηριστικά σχολιάστηκε για τη λύση τους, “Μια καλή μαθηματική απόδειξη μοιάζει με ποίημα, αυτό εδώ είναι τηλεφωνικός κατάλογος!“. Τη στιγμή μάλιστα που η απόδειξη περιελάμβανε πρόγραμμα υπολογιστή και ένα αποτέλεσμα που προερχόταν από την εκτέλεση του προγράμματος, χωρίς φυσικά να φαίνονται τα ενδιάμεσα βήματα που ακολουθήθηκαν, καταλαβαίνουμε γιατί αρκετοί μαθηματικοί και φιλόσοφοι χαρακτήρισαν την όλη εργασία ως ατελή και σίγουρα όχι ως “αληθινή” μαθηματική απόδειξη.

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

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

Φιλοσοφικές ανησυχίες
Από τα προηγούμενα γίνεται προφανές ότι, τόσο στα εφαρμοσμένα όσο και στα καθαρά μαθηματικά, η θεωρία έρχεται πάντα σε πρώτο πλάνο και η μηχανή χρησιμοποιείται μόνο δευτερευόντως και πάντα παρασκηνιακά. Όμως στην εργασία των Haken και Appel η κατάσταση αλλάζει δραματικά, αφού η απόδειξη που παρουσίασαν ήταν στενά εξαρτημένη από πρόγραμμα υπολογιστή. Επιπρόσθετα, ήταν πρακτικά αδύνατο να ελεγχθεί η ορθότητα της απόδειξης “με το χέρι”.

Τον Φεβρουάριο του 1979 ο φιλόσοφος Thomas Tymoczko, σε κείμενο που δημοσίευσε στο Journal of Philosophy, αναρωτιέται αν η απόδειξη των Haken και Appel μπορεί να θεωρηθεί ως έγκυρη. Αν και παραδέχεται πως οι δύο μαθηματικοί έδειξαν ότι τέσσερα χρώματα αρκούν για όλους τους χάρτες, έχει την πεποίθηση ότι δεν απέδειξαν κάτι — τουλάχιστον όχι όπως νοούνται οι αποδείξεις στα μαθηματικά. Ο Tymoczko έθεσε ορισμένα κριτήρια για την αναγνώριση μιας αληθινά μαθηματικής απόδειξης. Μεταξύ άλλων, η απόδειξη πρέπει να είναι πειστική και ταυτόχρονα αξιολογήσιμη, υπό την έννοια δηλαδή ότι μπορεί να επαληθευτεί πλήρως. Αν και η εργασία των Haken – Appel είναι πειστική, σίγουρα είναι προβληματική ως προς την επαλήθευση. Η τελευταία αυτή άποψη ενισχύεται κι από το γεγονός ότι το πρόγραμμα για τον υπολογιστή ενδέχεται να περιλαμβάνει λάθη, το ίδιο το υλικό που τρέχει το πρόγραμμα μπορεί να είναι ελαττωματικό ή ακόμη και η έξοδος του υπολογιστή μπορεί να παρερμηνευτεί. Ο Tymoczko συμπεραίνει πως αν χαρακτηρίσουμε την απόδειξη των Haken – Appel ως έγκυρη, τότε τα μαθηματικά κινδυνεύουν να υποβαθμιστούν σε μια εμπειρική επιστήμη υποκείμενη σε σφάλματα, όπως, π.χ., είναι η φυσική. Ο φιλόσοφος καταλήγει εξηγώντας πως σε μια τέτοια περίπτωση η έννοια της μαθηματικής απόδειξης πρέπει να τροποποιηθεί, ώστε να δέχεται τον πειραματισμό ως μέθοδο για την εγκαθίδρυση της μαθηματικής αλήθειας!

Εκτός από φιλοσόφους, δυσπιστία προς τη δουλειά των Haken – Appel έδειξαν και μαθηματικοί. Άξια αναφοράς είναι η στάση του George Spencer-Brown, ο οποίος δούλευε στο πρόβλημα των τεσσάρων χρωμάτων έως το 1964, τη χρονιά που ολοκλήρωσε το έργο του “Laws of Form” (“Νόμοι της Μορφής”, πρόκειται για μια εργασία επάνω στη μαθηματική λογική που συγκέντρωσε πολυποίκιλα σχόλια, όπως “δουλειά ιδιοφυΐας” και “εξεζητημένα ασήμαντο”). Ο Spencer-Brown ισχυρίστηκε πως “…πουθενά στην περιγραφή τους (οι Haken και Appel) δεν παρέχουν στον αναγνώστη ενδείξεις που θα του επιτρέψουν να ελέγξει τα λεγόμενά τους. Είναι εξίσου δυνατό ή αδύνατο να αποδειχτεί το θεώρημα των τεσσάρων χρωμάτων με τον τρόπο που παρουσιάζουν. Αυτό που είναι βέβαιο είναι πως οι ίδιοι δεν το απέδειξαν… Όχι μόνο δεν υπάρχει απόδειξη σε ό,τι δημοσίευσαν, επιπρόσθετα δεν υπάρχει καν κάτι που να αρχίζει να μοιάζει με απόδειξη. Πρόκειται για την πιο γελοία εκδοχή των νέων ρούχων του βασιλιά, που ατίμασε για πάντα την ιστορία των μαθηματικών…”.

Η υπεράσπιση
Οι φιλοσοφικές ανησυχίες αναφορικά με τη συμμετοχή υπολογιστή στη διαδικασία μιας μαθηματικής απόδειξης δεν άγγιξαν όλους τους μαθηματικούς. Μεταξύ αυτών ήταν ο Ted Swart, ο οποίος θεωρούσε τη χρήση υπολογιστή ως προέκταση του χαρτιού με το μολύβι. Όπως ο ίδιος σχολίασε “…δεν νομίζω πως υπάρχει διαχωριστική γραμμή που επιτρέπει τη χρήση χαρτιού και μολυβιού αλλά απαγορεύει τη χρήση υπολογιστή, με το φόβο ότι κάτι τέτοιο θα αλλοίωνε το μαθηματικό χαρακτήρα της απόδειξης. Προσωπικά δεν βλέπω μια τέτοια διαχωριστική γραμμή. Βρίσκω το όλο επιχείρημα κατά της χρήσης υπολογιστή παράξενο”.

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

Στην πορεία των μαθηματικών υπήρξαν –και σίγουρα θα υπάρξουν– αποδείξεις *χωρίς* χρήση υπολογιστή, οι οποίες δημοσιεύτηκαν στο ευρύ κοινό, έγιναν δεκτές με ενθουσιασμό, αλλά αργότερα ανακαλύφθηκε ότι περιείχαν λάθη. Συχνά τα λάθη αυτά ήταν επιδιορθώσιμα, όμως το γεγονός ότι εντοπίστηκαν δείχνει ότι οι παραδοσιακές μαθηματικές αποδείξεις δεν είναι υποχρεωτικά εγκυρότερες από αποδείξεις που επιστρατεύουν υπολογιστή. Ένα τέτοιο παράδειγμα αποτελεί η απόδειξη μιας περίφημης πρότασης της θεωρίας ομάδων (group theory), που εξέδωσαν το 1963 οι Walter Feit και John Thompson. Η απόδειξη εκτεινόταν σε 250 (!) σελίδες. Αν και οι περισσότεροι μαθηματικοί δεν διάβασαν ποτέ όλη ή έστω μέρος αυτής, τη δέχτηκαν ανενδοίαστα, ήσυχοι με τη σκέψη ότι υπήρξαν συνάδελφοι που τη διάβασαν. Τελικά διαπιστώθηκε ότι περιείχε λάθη, τα οποία ευτυχώς διορθώθηκαν. Κάτι παρόμοιο είχε συμβεί και με την απόδειξη του Andrew Wiles για το περίφημο τελευταίο θεώρημα του Fermat, ένα από τα πλέον ατίθασα προβλήματα της θεωρίας αριθμών.

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

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

Πάντως, η απόδειξη των Haken και Appel έχει ένα γνώρισμα που κανείς δεν το αμφισβητεί: της λείπει η ομορφιά και η κομψότητα. Φαίνεται πως τη σκέψη πολλών μαθηματικών στοιχειώνουν οι ιδέες του Godfrey Harold Hardy, από το βιβλίο του Απολογία ενός Μαθηματικού: “…Τα μοτίβα του μαθηματικού, όπως εκείνα του ζωγράφου ή του ποιητή, πρέπει να είναι όμορφα. Οι ιδέες, όπως τα χρώματα ή οι λέξεις, πρέπει να ταιριάζουν αρμονικά μεταξύ τους. Δεν υπάρχει μόνιμη θέση στον κόσμο για άσχημα μαθηματικά”.

Πέντε πρίγκιπες προκαλούν σύγχυση!
Συχνά λέγεται πως τα μαθηματικά είναι η επιστήμη της ακρίβειας. Ο ισχυρισμός δεν είναι άδικος: H παραμικρή, φαινομενικά αθώα παρανόηση εννοιών ή κανόνων, πάντα οδηγεί σε τραγελαφικά συμπεράσματα. Ένα σχετικό περιστατικό συνέβη και με την υπόθεση των τεσσάρων χρωμάτων, όταν το 1885 ο Γερμανός γεωμέτρης Richard Baltzer ανακοίνωσε ότι η αλήθεια του ισχυρισμού προκύπτει ως άμεση συνέπεια της αδυναμίας επίλυσης του προβλήματος των πέντε πριγκίπων.

Το προαναφερθέν πρόβλημα διατυπώθηκε γύρω στο 1840 από τον Γερμανό μαθηματικό κι αστρονόμο August Ferdinand Möbius: “Ζούσε κάποτε στην Ινδία ένας βασιλιάς που είχε ένα μεγάλο βασίλειο και πέντε γιους. Στη διαθήκη του, ο βασιλιάς εξέφρασε την επιθυμία πως μετά το θάνατό του οι γιοι πρέπει να μοιράσουν το βασίλειο με τέτοιο τρόπο, ώστε η περιοχή καθενός να έχει κοινά σύνορα –όχι μεμονωμένα σημεία– με όλες τις άλλες περιοχές. Πώς θα μοιράσουν οι πρίγκιπες τη γη του πατέρα τους;” Όταν οι μαθητές του Möbius επιχείρησαν να λύσουν το πρόβλημα κι απέτυχαν, γύρισαν στον καθηγητή τους και παραπονέθηκαν. Τότε εκείνος ξέσπασε σε γέλια, αφού, όπως αμέσως παραδέχτηκε, αυτό που ζητούσε ο βασιλιάς είναι απλά αδύνατο!

Μια παραλλαγή του προβλήματος των πέντε πριγκίπων διατυπώθηκε λίγα χρόνια αργότερα, από τον μαθηματικό Heinrich Tietze: “…Ο βασιλιάς αξίωσε ότι καθένας από τους γιους του θα πρέπει να χτίσει στη δική του περιοχή ένα παλάτι. Ανά δύο τα παλάτια θα πρέπει να επικοινωνούν με δρόμους, όμως οι δρόμοι αυτοί δεν πρέπει να διασταυρώνονται. Πώς πρέπει να χαραχτούν οι δρόμοι;”. Το πρόβλημα με τους δρόμους είναι επίσης αδύνατο. Τώρα, είναι εύκολο να διαπιστώσουμε ότι εάν το πρόβλημα των πέντε πριγκίπων είχε λύση, τότε λύση θα είχε και το πρόβλημα με τους δρόμους. Πράγματι, αν οι πρίγκιπες μπορούσαν να χωρίσουν τη γη του πατέρα τους σε πέντε αμοιβαία γειτονικές περιοχές, τότε θα ήταν σε θέση να χτίσουν παλάτια σε κάθε περιοχή και δρόμους που διασχίζουν σύνορα, ενώνοντας παλάτια γειτονικών περιοχών και χωρίς να διασταυρώνονται. Αντίστροφα, αν οι πρίγκιπες κατάφερναν να φτιάξουν τα πέντε παλάτια και δρόμους που τα ενώνουν ανά δύο, χωρίς να διασταυρώνονται, τότε θα μπορούσαν να επεκτείνουν κατάλληλα τις περιοχές γύρω από τα παλάτια κι έτσι το κομμάτι του καθενός θα συνόρευε με όλα τα υπόλοιπα.

Εάν ο βασιλιάς είχε τέσσερις γιους αμφότερα τα προβλήματα θα είχαν λύση, μάλιστα εύκολη. Με πέντε γιους, όμως, μόνος τρόπος ικανοποίησης των απαιτήσεων του βασιλιά είναι με διάπραξη μιας μικρής –αλλά σημαντικής– απάτης. Ο ίδιος ο Heinrich Tietze εξηγεί: “Τα πέντε αδέλφια είχαν βυθιστεί στην απελπισία, διότι είχε γίνει πλέον φανερό πως η επιθυμία του πατέρα τους δεν μπορούσε να ικανοποιηθεί. Κάποια μέρα παρουσιάστηκε ενώπιόν τους ένας περιπλανώμενος μάγος, που ισχυριζόταν πως έχει μια λύση. Η ιδέα του μάγου ήταν να ενώσει δύο από τις περιοχές με μια γέφυρα. Οι πέντε πρίγκιπες ενθουσιάστηκαν με την ιδέα και αντάμειψαν το μάγο πλουσιοπάροχα.”

Η γέφυρα του μάγου μοιάζει με σημερινή αερογέφυρα. Το θέμα είναι πως η κατασκευή της συνιστά εξαπάτηση, αφού των πρόβλημα των πέντε πριγκίπων πρέπει να λυθεί στο επίπεδο ή, ισοδύναμα, στην επιφάνεια μιας σφαίρας. Όμως η κατασκευή μιας τέτοιας γέφυρας ισοδυναμεί με την επίλυση του προβλήματος του Möbius (ή του Tietze) στην επιφάνεια ενός τόρου (torus, γεωμετρικό αντικείμενο που δημιουργείται εκ περιστροφής κύκλου και μοιάζει με σαμπρέλα ή ντόνατ). Εάν μάλιστα η γη του βασιλιά ήταν επάνω σε έναν τόρο, τότε η επιθυμία του θα μπορούσε να ικανοποιηθεί ακόμα και αν είχε επτά γιους!

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

p = το πρόβλημα των πέντε πριγκίπων έχει λύση

και

q = το πρόβλημα των τεσσάρων χρωμάτων δεν έχει λύση

η προηγούμενη διατύπωση μπορεί να γραφτεί συμβολικά ως εξής:

p => q

Σύμφωνα με του κανόνες της μαθηματικής λογικής, είναι απόλυτα έγκυρο να γράψουμε

όχι q => όχι p

που με απλά λόγια είναι σαν να λέμε ότι αν το πρόβλημα των τεσσάρων χρωμάτων έχει λύση, τότε το πρόβλημα των πέντε πριγκίπων δεν έχει. Στο σημείο αυτό είναι εύκολο να δημιουργηθεί μεγάλη σύγχυση. Πράγματι, ενώ από την πρόταση

p => q

κάλλιστα μπορούμε να πάμε στην ισοδύναμη

όχι q => όχι p

είναι εντελώς λάθος να πάμε στην

όχι p => όχι q

(τεράστια προσοχή στην θέση των p και q). Αλήθεια, πώς διατυπώνεται στην καθημερινή γλώσσα η (άκυρη) πρόταση “όχι p => όχι q”; Πολύ απλά, ως εξής: «Εάν το πρόβλημα των πέντε πριγκίπων δεν έχει λύση, τότε το πρόβλημα των τεσσάρων χρωμάτων έχει λύση».

Για πολλά χρόνια, αρκετοί ερασιτέχνες αλλά και επαγγελματίες μαθηματικοί προσπάθησαν να δείξουν την αλήθεια της υπόθεσης των τεσσάρων χρωμάτων, στηριζόμενοι στην πέρα για πέρα λανθασμένη πρόταση “όχι p => όχι q”. Ένας από τους επαγγελματίες που ξεγελάστηκε ήταν ο Γερμανός γεωμέτρης Richard Baltzer. Σε διάλεξή τους στις 12 Ιανουαρίου του 1885 περιέγραψε το πρόβλημα των πέντε πριγκίπων κι εξήγησε γιατί δεν έχει λύση. Ακολούθως προχώρησε στο …μοιραίο, εξηγώντας πως το θεώρημα των τεσσάρων χρωμάτων προκύπτει ως άμεση συνέπεια της αδυναμίας επίλυσης του προβλήματος των πέντε πριγκίπων (ισχυρίστηκε, δηλαδή, πως “όχι p => όχι q”). Το λάθος του Baltzer εντοπίστηκε το 1897 από τη μαθηματικό Isabel Maddison του κολεγίου Bryn Mawr, στη Φιλαδέλφεια των ΗΠΑ.

Εναλλακτική, σύγχρονη διατύπωση
Μια σύγχρονη διατύπωση του προβλήματος των τεσσάρων χρωμάτων εμπλέκει την έννοια του επίπεδου γραφήματος (planar graph). Αφήνοντας κατά μέρος τον αυστηρό, μαθηματικό ορισμό, ένα επίπεδο γράφημα ή, απλά, γράφημα, μπορούμε να το φανταζόμαστε ως ένα σύνολο σημείων του επιπέδου που ονομάζονται κορυφές (vertices). Ορισμένες κορυφές συνδέονται με άλλες με ευθύγραμμα τμήματα ή καμπύλες, που ονομάζονται ακμές (edges) ή τόξα (arcs). Δύο κορυφές που συνδέονται με μία ακμή ονομάζονται γειτονικές (adjacent). Ένα γράφημα στο οποίο από οποιαδήποτε κορυφή μπορούμε να μεταβούμε σε μια οποιαδήποτε άλλη, διασχίζοντας ένα μονοπάτι (path) από ακμές, ονομάζεται συνεκτικό (connected). Τώρα, το πρόβλημα των τεσσάρων χρωμάτων μπορεί να διατυπωθεί στη γλώσσα των γραφημάτων ως εξής: Δίνονται τέσσερα χρώματα και ζητείται ένας χρωματισμός των κορυφών ενός συνεκτικού γραφήματος, ώστε γειτονικές κορυφές να έχουν διαφορετικά χρώματα.

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

Αβεβαιότητα στα μαθηματικά
Στη δεκαετία του 1950, στις τάξεις των μαθηματικών επικρατούσε η υποψία ότι η υπόθεση των τεσσάρων χρωμάτων είναι ένα από εκείνα τα ερώτημα για τα οποία ποτέ δεν θα πάρουμε τελεσίδικη απάντηση. Οι δύο βασικοί λόγοι που ενίσχυαν αυτή την υποψία ήταν αφενός οι συνεχείς αποτυχίες των μαθηματικών να αποδείξουν την περιβόητη υπόθεση, αφετέρου το Θεώρημα Μη-Πληρότητας, που διετύπωσε ο λογικολόγος Kurt Gödel to 1931.

Κοντολογίς, ο Gödel απέδειξε ότι σε ένα οποιοδήποτε μαθηματικό σύστημα θα υπάρχουν πάντοτε κάποιες προτάσεις, των οποίων η αλήθεια ή το ψεύδος θα είναι αδύνατο να αποδειχτούν στα πλαίσια του ίδιου του συστήματος. Υπερβαίνοντας το αρχικό σύστημα, για την ακρίβεια κατασκευάζοντας ένα ευρύτερο, οι “ατίθασες” προτάσεις θα μπορούν πλέον να αποδειχτούν, μόνο που το νέο υπερσύστημα θα περιλαμβάνει κι αυτό, με τη σειρά του, κάποιες προτάσεις που θα είναι αδύνατο να αποδειχτούν στα νέα, διευρυμένα πλαίσια. Ό,τι και να κάνουμε, λοιπόν, το θεώρημα της μη-πληρότητας του Gödel μας βεβαιώνει ότι πάντα θα είμαστε …αβέβαιοι για την εγκυρότητα ή όχι κάποιων μαθηματικών προτάσεων.

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

10 Responses to “Φτάνουν 4 χρώματα, για όλους τους χάρτες του κόσμου;”

  1. Citr0nella | 24/11/2012 at 22:38

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

    Φαίνεται πως τη σκέψη πολλών μαθηματικών στοιχειώνουν οι ιδέες του Godfrey Harold Hardy, από το βιβλίο του Απολογία ενός Μαθηματικού:”

    Ευχαριστούμε για το όμορφο δωράκι μές στο σ-κ!:)

  2. aLEXk | 27/11/2012 at 13:17

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

    • subZraw | 27/11/2012 at 14:46

      Ναι, αυτό το σχήμα που προτείνεις σίγουρα δείχνει ότι 3 χρώματα δεν αρκούν. Αλλά και το σχήμα που προτείνεται στο κείμενο δουλεύει — με την προϋπόθεση ότι υπάρχουν κι άλλες, “τριγωνικές χώρες” με κοινή κορυφή με το κεντρικό :)

      • aLEXk | 27/11/2012 at 18:05

        Και σε αυτή τη περίπτωση δύο χρώματα είναι αρκετά!!! ;-)

        • subZraw | 27/11/2012 at 23:49

          Ααααα, εσύ δεν τα παρατάς εύκολα μου φαίνεται :) Καλά κάνεις όμως, να μάθω να σκέφτομαι πριν πληκτρολογήσω.

          Ένα αντιπαράδειγμα, λοιπόν, για το ότι 3 χρώματα δεν είναι αρκετά, παίρνουμε όταν έχουμε μια περιοχή που περικλείεται από περιττό αριθμό περιοχών, οι οποίες συνορεύουν κυκλικά.

          Δες, π.χ., αυτό: http://upload.wikimedia.org/wikipedia/commons/a/a4/Four_Colour_Planar_Graph.svg

          ΥΓ. Πάω να διορθώσω και το κυρίως κείμενο!

  3. kissmyarch | 10/12/2012 at 12:16

    Διαβάζω το Engines of Logic του Martin Davis το οποίο είναι σε παρόμοιο ύφος, οπότε διαβάζοντας το άρθρο το ευχαριστήθηκα πολύ :)
    Ωραία η ιστορική αναδρομή. Αν βρεις χρόνο γράψε και άλλα σε τέτοιο στυλ!

    • subZraw | 10/12/2012 at 12:22

      Χαίρομαι που σου άρεσε :)

      Τα άρθρα της κατηγορίας Mind Hacks τα είχα γράψει για το περιοδικό Discovery & Science, το οποίο αν θυμάμαι καλά σταμάτησε να κυκλοφορεί κάπου προς το 2007. Έχω κι άλλα που δεν έχω δημοσιεύσει εδώ. Μόλις βρω λίγο χρόνο μάλλον θα ανεβάσω Το Δίλημμα του Φυλακισμένου (αφού πρώτα το “χτενίσω” λίγο πρώτα).

      • kissmyarch | 10/12/2012 at 15:04

        Yeap! Έχω 14 τεύχη Discovery & Science, το τελευταίο τεύχος το 19 κυκλοφόρησε Δεκέμβριο του ’06, οπότε καλά θυμάσαι :) Θα ξεσκονίσω τα εκεί άρθρα σου. Ένα που είχα διαβάσει πρόσφατα (όταν λέω πρόσφατα εννοώ πριν κανα χρόνο) ήταν αυτό με τα διαφορετικά σύνολα του απείρου. Τελικά το τεύχος με το δίλημμα του φυλακισμένου το έχω (18), οπότε θα το διαβάσω σύντομα, thanks!

        • subZraw | 10/12/2012 at 18:11

          Ααα, τότε να το διαβάσεις από το D&S! Άλλη χάρη το έντυπο — να τα λέμε αυτά!

  4. StavrosH | 26/08/2013 at 12:33

    Πολλά παρακλάδια των Μαθηματικών ξεκίνησαν από απλά ερωτήματα (Για παράδειγμα το πρόβλημα που είχε ένας Βασιλιάς προς τον Μαθηματικό του αν ο Ουρανός θα του πέσει στο Κεφάλι (ή πιο επιστημονικά πόσο ευσταθές είναι το ηλιακό σύστημα για τη Γη) έκανε τον Μαθηματικό να βγάλει ολόκληρο παρακλάδι των Μαθηματικών την Τοπολογία (που ακόμα ψάχνουμε να που να την χρησιμοποιήσουμε – αν και τώρα βλέπουμε ότι έχει μεγάλη σχέση με την επιστήμη του Χάους) ).
    Τα άλυτα μαθηματικά προβλήματα – ερωτήματα έχουν απασχολήσει και τους Αρχαίους Έλληνες (πχ έναν από αυτούς που ζητούσε από τους άλλους να του πουν αν αυτό που ισχυρίζεται είναι αλήθεια: “Όλοι οι Κρήτες είναι ψεύτες”. Αδύνατο να πάρουμε απόφαση δεδομένου του γεγονότος και ότι ο συγκεκριμένος τύπος ήταν και αυτός από την Κρήτη).
    Πολύ ενδιαφέρον άρθρο !!!

Leave a Reply

You must be logged in to post a comment.

Σύνδεση

Αρχείο δημοσιεύσεων