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

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

Ιστορία της απόδειξης

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

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

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

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

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

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

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

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

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

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

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

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

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

Απουσία απόδειξης ή ανταπόδειξης

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