Φανταστείτε έναν οποιονδήποτε χάρτη, π.χ., αυτόν της Μακεδονίας, της Ελλάδας ολόκληρης, της Ευρώπης ή του Ανατολικού Τιμόρ. Αν θέλετε σκεφτείτε ακόμη κι ένα χάρτη από κάποιον φανταστικό πλανήτη. Κατά πάσα πιθανότητα ο χάρτης σας χωρίζεται σε διαφορετικές περιοχές, όπως επαρχίες ή νομούς. Πόσα χρώματα πιστεύετε ότι χρειάζονται, ώστε κάθε περιοχή να έχει το δικό της χρώμα αλλά γειτονικές περιοχές να είναι διαφορετικά χρωματισμένες;
Το δημοφιλές στον κόσμο των μαθηματικών Θεώρημα των Τεσσάρων Χρωμάτων,
αξιώνει ότι εάν ένα επίπεδο χωριστεί σε περιοχές, όπως, π.χ., χωρίζεται ένας γεωπολιτικός χάρτης, τότε αρκούν τέσσερα μόλις χρώματα ώστε γειτονικές περιοχές να είναι διαφορετικά χρωματισμένες.
Στα πλαίσια της διατύπωσης, ως «γειτονικές» ορίζονται δύο περιοχές με κοινό σύνορο. Περιοχές που έχουν ένα μόλις κοινό σημείο, π.χ., μία κορυφή, δεν θεωρούνται γειτονικές. Επίσης, κάθε περιοχή πρέπει να είναι συνεχής, δηλαδή να μην διακόπτεται, όπως μερικές φορές συμβαίνει στον πραγματικό κόσμο, π.χ., με την περίπτωση του Αζερμπαϊτζάν. Το θεώρημα των τεσσάρων χρωμάτων στο επίπεδο δουλεύει εξίσου καλά κι επάνω στην επιφάνεια μιας σφαίρας. (Κάθε χάρτης του επιπέδου μπορεί να προβληθεί σε μια σφαίρα κι αντίστροφα, με τη βοήθεια μιας απλής μεθόδου αντιστοίχησης σημείων που ονομάζεται στερεογραφική προβολή.)
Είναι εύκολο να δειχτεί ότι τρία χρώματα δεν αρκούν για έναν ανάλογο χρωματισμό περιοχών του επιπέδου. Για να το δούμε αυτό αρκεί να σχεδιάσουμε μια περιοχή που περικλείεται από περιττό αριθμό περιοχών, οι οποίες συνορεύουν κυκλικά. Έχει ήδη αποδειχτεί, εξάλλου, πως πέντε χρώματα αρκούν για το ζητούμενο τρόπο χρωματισμού. Όμως η απόδειξη για την επάρκεια ή όχι των τεσσάρων χρωμάτων χρειάστηκε πάνω από έναν αιώνα για να ξεκαθαρίσει! Μάλιστα αν δεν επιστρατεύονταν υπολογιστές, ίσως ακόμη και σήμερα τα πράγματα να ήταν… θολά.
Αναγνώριση
Η υπόθεση των τεσσάρων χρωμάτων διατυπώθηκε για πρώτη φορά το 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. Όπως χαρακτηριστικά σχολιάστηκε για τη λύση τους, «Μια καλή μαθηματική απόδειξη μοιάζει με ποίημα, αυτό εδώ είναι τηλεφωνικός κατάλογος!«. Τη στιγμή μάλιστα που η απόδειξη περιελάμβανε πρόγραμμα υπολογιστή και ένα αποτέλεσμα που προερχόταν από την εκτέλεση του προγράμματος, χωρίς φυσικά να φαίνονται τα ενδιάμεσα βήματα που ακολουθήθηκαν, καταλαβαίνουμε γιατί αρκετοί μαθηματικοί και φιλόσοφοι χαρακτήρισαν την όλη εργασία ως ατελή και σίγουρα όχι ως «αληθινή» μαθηματική απόδειξη.
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου