Τι είναι η απόδειξη

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

Ο σκοπός των αποδείξεων

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

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

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

Οι αποδείξεις λοιπόν, όταν μαθαίνουμε κάποια ύλη, απαντούν στο ερώτημα «γιατί λειτουργεί έτσι;». Αν καταλάβεις γιατί λειτουργεί κάτι, θα το θυμάσαι ευκολότερα και με τον καιρό θα καταλαβαίνεις την ύλη σίγουρα καλύτερα από κάποιον που την έμαθε «παπαγαλία». Το ερώτημα είναι αν αυτός είναι ο στόχος σου.

Τι είναι η απόδειξη

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

Στην αρχή κάθε απόδειξης πρέπει να έχουμε την πρόταση που θέλουμε να αποδείξουμε. Αυτή την πρόταση τη συμβολίζουμε με το μαγικό σύμβολο ϕ. Επιπλέον θα χρειαστούμε ένα σύνολο αξιωμάτων και υποθέσεων, που το συμβολίζουμε Ax, με τη βοήθεια των οποίων θα αποδείξουμε την πρόταση ϕ. Το σύνολο των αξιωμάτων είναι κάτι που ήδη ξέρουμε, που υποθέτουμε ότι ισχύει. Μπορεί να είναι πράγματα όπως για παράδειγμα «κάθε άρτιος αριθμός διαιρείται ταυτόχρονα με το δύο». Επιπλέον, αυτό το σύνολο μπορεί να περιέχει για παράδειγμα τύπους για μετασχηματισμούς παραστάσεων, που έχουν αποδειχθεί κάπου αλλού και ήδη υποθέτουμε ότι ισχύουν, για παράδειγμα:

$$(a+b{)}^2=a^2+2ab+b^2;a,b\in \mathbb{R}$$

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

$$(a+b{)}^2$$

θα τη μετασχηματίζουμε με ισοδύναμες μετατροπές, μέχρι να πάρουμε την παράσταση του δεύτερου μέλους. Θα το δείξω:

$$(a+b{)}^2=(a+b)\cdot (a+b)=a\cdot a+a\cdot b+b\cdot a+b\cdot b=$$

$$=a\cdot a+2ab+b\cdot b=a^2+2ab+b^2$$

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

Το σημαντικό είναι ότι κάθε μετασχηματισμός πρέπει να είναι έγκυρος, πρέπει να βασίζεται σε κάτι που ήδη γνωρίζουμε. Η μαθηματική απόδειξη είναι κάτι σαν την εξέλιξη – με σταδιακές μικρές αλλαγές παίρνουμε από μια παράσταση μια άλλη.

Τετριμμένες αποδείξεις

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

Ας το δείξουμε με ένα παράδειγμα: έστω το σύνολο των φυσικών αριθμών χωρίς το μηδέν, δηλαδή το σύνολο των αριθμών ℕ^∗ = {1, 2, 3, …}. Τώρα μπορούμε να πούμε ότι κάθε κλάσμα της μορφής:

$$\frac{q}{p};q,p\in {\mathbb{N}}^{\ast }$$

είναι έγκυρο κλάσμα, δηλαδή δεν θα βρούμε κανένα ζεύγος αριθμών q, p, για το οποίο το δοσμένο κλάσμα να μην έχει νόημα. Πώς θα το αποδείξουμε; Πρώτα πρέπει να βρούμε πότε ένα κλάσμα δεν έχει νόημα. Ένα κλάσμα δεν έχει νόημα όταν στον παρονομαστή υπάρχει μηδέν (δεν μπορούμε να διαιρέσουμε με το μηδέν). Πρέπει λοιπόν να αποδείξουμε ότι p ≠ 0 για όλα τα δυνατά p. Εμείς όμως ξέρουμε ότι το p το παίρνουμε από τους φυσικούς αριθμούς, που τους ορίσαμε ως ℕ^∗ = {1, 2, 3, …}. Το σύνολο αυτό δεν περιέχει το μηδέν, άρα ο αριθμός p θα είναι πάντα διαφορετικός από το μηδέν.

$$\mathrm{\forall }p\in {\mathbb{N}}^{\ast }:p\ne 0$$

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

Οι τετριμμένες αποδείξεις συνήθως πράγματι είναι τετριμμένες, αλλά μόνο αν ξέρεις το ευρύτερο πλαίσιο. Για παράδειγμα, αν δεν καταλαβαίνεις την έννοια του συνόλου ή δεν ξέρεις τι σημαίνει ότι το p είναι στοιχείο του συνόλου ℕ^∗, τότε ούτε αυτή η απόδειξη ήταν τετριμμένη για σένα. Οι τετριμμένες αποδείξεις δεν χαρακτηρίζονται λοιπόν από το ότι είναι απλές, όσο από το ότι είναι σύντομες και προκύπτουν εύκολα από κάποιο (οσοδήποτε δύσκολο) πλαίσιο.

Αντιπαράδειγμα

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

Παράδειγμα: «κάθε φυσικός αριθμός είναι μεγαλύτερος από το δέκα». Πώς θα αποδείξουμε ότι αυτό δεν είναι αλήθεια; Αντιπαράδειγμα στον ισχυρισμό μας είναι για παράδειγμα ο αριθμός πέντε. Ο αριθμός πέντε είναι φυσικός αριθμός και δεν είναι μεγαλύτερος από το δέκα. Τον ισχυρισμό δεν μπορούμε να τον αποδείξουμε απαριθμώντας μερικούς φυσικούς αριθμούς που είναι μεγαλύτεροι από το δέκα. Δεν μπορείς να πεις «οι φυσικοί αριθμοί 11, 12, 13, 123 και 5345 είναι μεγαλύτεροι από το 10, άρα η δοσμένη πρόταση είναι αληθής». Αυτό δεν γίνεται. Διαλέξαμε απλώς λίγα παραδείγματα για τα οποία ο ισχυρισμός μας ισχύει, αλλά αυτό δεν λέει τίποτα για τους άλλους αριθμούς, που δεν τους αναφέραμε καθόλου.

Δεύτερο παράδειγμα: κάθε άνδρας ψηλότερος από δύο μέτρα έχει καστανά ή μπλε μάτια. Υποθέτω ότι ελάχιστοι είναι σε θέση να βρουν αντιπαράδειγμα. Τι μας λέει αυτό για τη δοσμένη πρόταση; Τίποτα απολύτως. Αν δεν μπορούμε να βρούμε αντιπαράδειγμα, δεν σημαίνει απαραίτητα ότι η δοσμένη πρόταση είναι αληθής. Το αντιπαράδειγμα μπορεί να υπάρχει κάπου, απλώς δεν μπορούμε να το βρούμε αυτή τη στιγμή. Η αδυναμία να βρούμε αντιπαράδειγμα δεν αποδεικνύει ότι ο δοσμένος ισχυρισμός είναι αληθής.

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

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

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

$$A\Rightarrow A_1\Rightarrow A_2\Rightarrow A_3\Rightarrow \dots \Rightarrow A_{\nu }\Rightarrow B$$

Ως παράδειγμα θα αποδείξουμε ότι ισχύει η πρόταση

$$a>1\Rightarrow a^2>1$$

Τώρα βήμα βήμα:

1. Επειδή a>1, σίγουρα ισχύει επίσης a>0 και επίσης a ≠ 0 (ουσιαστικά απλώς εξασθενούμε τη συνθήκη).
2. Επειδή το a δεν είναι ίσο με το μηδέν και είναι θετικό, μπορούμε να πολλαπλασιάσουμε ολόκληρη την ανισότητα με τη μεταβλητή a χωρίς ανησυχία. Αν το a ήταν μηδέν, η αυστηρή ανισότητα δεν θα διατηρούνταν (θα παίρναμε 0>0), αν ήταν αρνητικό, θα έπρεπε να αντιστρέψουμε τη φορά της ανισότητας. Μετά τον πολλαπλασιασμό με τη μεταβλητή a παίρνουμε την ανισότητα a²>a.
3. Αυτή τη στιγμή ξέρουμε ότι a>1 και ταυτόχρονα ξέρουμε ότι a²>a. Αν συνδυάσουμε αυτές τις δύο ανισότητες, παίρνουμε: a²>a>1.
4. Από εδώ απλώς αφαιρούμε τον μεσαίο όρο και έχουμε a²>1. Αυτό μπορούσαμε να το κάνουμε, επειδή το a είναι μεγαλύτερο από το ένα και το a² είναι μεγαλύτερο από το a. Αν το a² είναι μεγαλύτερο από το a και το a είναι ταυτόχρονα μεγαλύτερο από το ένα, τότε σίγουρα το a² είναι μεγαλύτερο από το ένα.

Συμβολικά θα μπορούσαμε να το γράψουμε έτσι:

$$a>1\Rightarrow a>0\Rightarrow a^2>a\Rightarrow a^2>a>1\Rightarrow a^2>1.$$

Έμμεση απόδειξη

Η έμμεση απόδειξη χρησιμοποιεί περισσότερο τις ιδιότητες της συνεπαγωγής. Αν πρέπει να αποδείξουμε μια πρόταση της μορφής A ⇒ B, μπορούμε να χρησιμοποιήσουμε την αντιθετοαντίστροφη πρόταση και να αποδείξουμε

$$\mathrm{\neg }B\Rightarrow \mathrm{\neg }A.$$

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

$$a-b=0\Rightarrow a=b.$$

Τώρα σχηματίζουμε την αντιθετοαντίστροφη συνεπαγωγή:

$$\begin{array}{rcl}\mathrm{\neg }(a=b)& \Rightarrow & \mathrm{\neg }(a-b=0)\\ a\ne b& \Rightarrow & a-b\ne 0\end{array}$$

Αν a ≠ b, μπορούμε να αναλύσουμε το b σε άθροισμα b = a + x, όπου το x παριστάνει την απόσταση του αριθμού b από τον αριθμό a. Η συνεπαγωγή γίνεται:

$$a\ne (a+x)\Rightarrow a-(a+x)\ne 0;x\ne 0$$

Απαλείφουμε τα a όπου μπορούμε:

$$0\ne x\Rightarrow -x\ne 0;x\ne 0$$

Επειδή x ≠ 0, είναι και −x ≠ 0, άρα η συνεπαγωγή ισχύει. Η πρόταση αποδείχθηκε, οπότε ισχύει και η αρχική πρόταση

$$a-b=0\Rightarrow a=b.$$

Άλλες τεχνικές απόδειξης είναι για παράδειγμα η ήδη αναφερθείσα απαγωγή σε άτοπο ή η απόδειξη με επαγωγή.

Άλλες πηγές

• Μαθηματική απόδειξη στη Βικιπαίδεια