Μαθηματική απόδειξη

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

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

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

Ιστορία της απόδειξης
Ο πρώτος που αναφέρεται ότι εισήγαγε την απόδειξη στα μαθηματικά για να εγκυροποιήσει τους μαθηματικούς συλλογισμούς του ήταν ο Θαλής το 600 π.Χ περίπου. Όμως για το είδος των αποδείξεων του Θαλή δεν γνωρίζουμε σχεδόν τίποτε. Πάντως ο Θαλής και οι Ίωνες φιλόσοφοι της Σχολής της Ιωνίας εφοδίασαν τα μαθηματικά με την απόδειξη που έκτοτε έγινε αναπόσπαστο τμήμα τους.

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

Μέθοδοι απόδειξης

Ευθεία απόδειξη 

Η Ευθεία απόδειξη διακρίνεται στη Συνθετική και την Αναλυτική απόδειξη.

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

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

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

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

Η Αναλυτική απόδειξη εισηγήθηκε απ τον Πλάτωνα και τον Λεωδάμαντα.

Απαγωγή σε άτοπο 

Στην απόδειξη με απαγωγή σε άτοπο (γνωστή και ως εις άτοπον απαγωγή, ή reductio ad absurdum στα Λατινικά), δείχνεται ότι αν κάποια πρόταση ήταν ψευδής, τότε συμβαίνει μια λογική αντίφαση, επομένως η αρχική πρόταση θα πρέπει να είναι αληθής.  Αυτή είναι ίσως η πιο συχνά απαντούμενη μέθοδος σε μαθηματικές αποδείξεις.  Μια διάσημη απόδειξη που κάνει χρήση αυτής της μεθόδου είναι η απόδειξη ότι το  είναι άρρητος:

Έστω ότι ο  είναι ρητός, δηλαδή  όπου a και b είναι μη μηδενικοί ακέραιοι πρώτοι μεταξύ τους (ορισμός ρητών αριθμών).  Έτσι, . Υψώνοντας και τις δυο πλευρές στο τετράγωνο δίνει 2b2 = a2. Αφού το 2 διαιρεί το αριστερό μέρος, θα πρέπει και να διαιρεί το δεξί μέλος της εξίσωσης, μιας και είναι ίσα.  Επομένως, ο a2 είναι άρτιος, που σημαίνει ότι ο a θα πρέπει επίσης να είναι άρτιος.  Μπορούμε δηλαδή να γράψουμε a = 2c, όπου c είναι ακέραιος.  Αντικατάσταση στην αρχική εξίσωση δίνει 2b2 = (2c)2 = 4c2.  Διαιρώντας και τις δυο πλευρές με το 2 δίνει b2 = 2c2.  Αλλά τότε, ακολουθώντας το ίδιο επιχείρημα, το 2 διαιρεί το b2, άρα και το b είναι άρτιος.  Όμως, αν οι a και b είναι και οι δυο άρτιοι, έχουν κοινό διαιρέτη (το 2).  Αυτό έρχεται σε αντίθεση με την υπόθεση ότι είναι πρώτοι μεταξύ τους, άρα πρέπει να συμπεράνουμε ότι ο  είναι άρρητος.

Η Εις άτοπον απαγωγή επινοήθηκε από τους Πυθαγορείους και τους Ελεάτες.

Μαθηματική ή Τέλεια επαγωγή 

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

Η αρχή της μαθηματικής επαγωγής ορίζει ότι:

Έστω N = { 1, 2, 3, 4, ... } το σύνολο των φυσικών αριθμών και P(n) μια μαθηματική πρόταση που περιέχει τον φυσικό αριθμό n που ανήκει στο N, έτσι ώστε
(i) P(1) ισχύει, δηλαδή, P(n) να είναι αλήθεια για n = 1
(ii) P(m + 1) ισχύει όταν P(m) ισχύει, δηλαδή P(m) συνεπάγεται ότι 
P(m + 1).
Τότε, P(n) ισχύει για όλους τους φυσικούς αριθμούς n.

Αντιθετοαντιστροφή ή Αντιμετάθεση 

Η απόδειξη με αντιθετοαντιστροφή ή αντιμετάθεση δείχνει το συμπέρασμα "αν p τότε q" αποδεικνύοντας το ισοδύναμο αντιθετοαντίστροφο "αν όχι q τότε όχι p".

Κατασκευαστική απόδειξη 

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

Απόδειξη με εξάντληση 

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

Πιθανοτική απόδειξη 

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

Συνδυαστική απόδειξη 

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

Μη κατασκευαστική απόδειξη 

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

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

Τέλος απόδειξης 

Στα Ελληνικά μαθηματικά από την εποχή του Ευκλείδη και μετά κάθε απόδειξη περατώνεται με την φράση "ὅπερ ἔδει δειξαι", με αρχικά "Ο.Ε.Δ", που σημαίνει "όπως έπρεπε να αποδειχθεί" . Η σημασία του "Ο.Ε.Δ" είναι ότι αποδείχτηκε το θεώρημα και είμαστε έτοιμοι για την απόδειξη του επόμενου θεωρήματος.

Στα λατινικά η αντίστοιχη έκφραση είναι "Quod Erat Demonstrandum" με αρχικά "Q.E.D.".

Εναλλακτικά στη βιβλιογραφία χρησιμοποιείται ένα τετράγωνο ορθογώνιο, όπως το  ή .  

Μαθηματική λογική
Μαθηματική ορολογία
 
Πηγές γνώσης