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

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

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

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

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

Για κάθε δυο άρτιους αριθμούς x και y μπορεί να γραφεί x=2a και y=2b για κάποιους ακέραιους a και b, αφού τόσο το x όσο και το y είναι πολλαπλάσια του 2. Αλλά το άθροισμα x+y = 2a + 2b = 2(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".
Απόδειξη με αντίφαση

Κύριο λήμμα: Εις άτοπον απαγωγή

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ορισμένες φορές, τα αρχικά "Q.E.D." γράφονται για να δείξουν το τέλος μιας απόδειξης Τα αρχικά σημαίνουν "Quod Erat Demonstrandum", που στα Λατινικά σημαίνει "αυτό που έπρεπε να δειχθεί". Εναλλακτικά χρησιμοποιείται ένα τετράγωνο ορθογώνιο, όπως το □ ή ∎. Στα ελληνικά χρησιμοποιείται και το "Ο.Ε.Δ" από το αρχικό αρχαίο ελληνικό "ὅπερ ἔδει δειξαι" με την ίδια σημασία, μετάφραση του οποίου είναι η λατινική έκφραση.
Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα mathematical proof της Αγγλόγλωσσης Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).

Μαθηματική Εγκυκλοπαίδεια

Scientific Library