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

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

Ένα τετριμμένο παράδειγμα

Έστω ο ισχυρισμός «δεν υπάρχει ελάχιστος θετικός ρητός αριθμός». Αυτόν τον ισχυρισμό τον αποδεικνύουμε με απαγωγή σε άτοπο ως εξής: πρώτα τον αρνούμαστε: «υπάρχει ελάχιστος θετικός ρητός αριθμός» και ονομάζουμε αυτόν τον αριθμό q. Αν το q είναι ο ελάχιστος θετικός ρητός αριθμός, τότε δεν μπορούμε να βρούμε μικρότερο θετικό ρητό αριθμό – γιατί τότε το q δεν θα ήταν ο ελάχιστος.

Αυτό θα το χρησιμοποιήσουμε για να βρούμε το άτοπο. Αν παρ' όλα αυτά βρούμε έναν αριθμό που είναι μικρότερος από το q, το οποίο μπορούμε να το διαλέξουμε ελεύθερα, τότε καταλήξαμε σε άτοπο και η άρνηση του ισχυρισμού δεν ισχύει. Αν διαλέξουμε για ελάχιστο αριθμό για παράδειγμα το 0,1, βλέπουμε ότι το 0,01 είναι μικρότερο. Έπειτα το 0,001 είναι ακόμα μικρότερο, το 0,0001 είναι πάλι μικρότερο και ούτω καθεξής. Αρκεί να διαιρέσουμε τον αριθμό q με το δέκα και παίρνουμε μικρότερο αριθμό. Ουσιαστικά αρκεί να τον διαιρέσουμε με οποιονδήποτε αριθμό μεγαλύτερο από το ένα, για παράδειγμα με το δύο – το μισό του αριθμού q θα είναι σίγουρα μικρότερο από ολόκληρο τον αριθμό q.

Άρα ο αριθμός q/2 είναι σίγουρα μικρότερος από το q και ταυτόχρονα είναι θετικός ρητός αριθμός. Έτσι καταλήξαμε σε άτοπο με την άρνηση του ισχυρισμού, δηλαδή η άρνηση δεν ισχύει και επομένως ισχύει ο αρχικός ισχυρισμός.

Ενδιαφέροντες αριθμοί

Ένα κλασικό αστείο παράδειγμα που δείχνει την αρχή του ατόπου είναι το ακόλουθο. Ας υποθέσουμε ότι υπάρχουν φυσικοί αριθμοί που είναι κατά κάποιον τρόπο ενδιαφέροντες. Για παράδειγμα, ο αριθμός 2 είναι ενδιαφέρων, επειδή ισχύει 2 · 2 = 2 + 2, μια αρκετά ασυνήθιστη ιδιότητα. Ο αριθμός 42 είναι ενδιαφέρων, επειδή είναι η απάντηση σε όλα. Και ούτω καθεξής. Το ερώτημα είναι – υπάρχουν άπειροι ενδιαφέροντες αριθμοί;

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

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

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

Απόδειξη ότι υπάρχουν άπειροι πρώτοι αριθμοί

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

Πρώτος αριθμός είναι ένας αριθμός που διαιρείται μόνο με δύο διαφορετικούς αριθμούς – τον εαυτό του και το ένα. Πρόσεξε ότι τον ορισμό δεν τον ικανοποιεί το ένα, ενώ τον ικανοποιεί το δύο.

Η ανάλυση σε γινόμενο πρώτων παραγόντων είναι η ανάλυση ενός φυσικού αριθμού, εκτός από το ένα, σε γινόμενο πρώτων αριθμών. Είναι μια αρκετά ενδιαφέρουσα ιδιότητα των φυσικών αριθμών. Όποιον φυσικό αριθμό κι αν πάρεις (εκτός από το ένα), ισχύει ότι μπορεί να αναλυθεί σε γινόμενο μερικών (ακόμα και ίδιων) πρώτων αριθμών. Παραδείγματα:

$$\begin{array}{rcl}8& =& 2\cdot 2\cdot 2\\ 15& =& 3\cdot 5\\ 26& =& 2\cdot 13\\ 1800& =& 2^3\cdot 3^2\cdot 5^2\end{array}$$

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

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

$${\alpha }_1,{\alpha }_2,{\alpha }_3,\dots ,{\alpha }_{\nu }$$

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

Αν θέλουμε να καταλήξουμε σε άτοπο, πρέπει λοιπόν να κατασκευάσουμε έναν πρώτο αριθμό που δεν ανήκει σε αυτή την ακολουθία. Σε αυτό θα μας βοηθήσει ο αριθμός q. Τον κατασκευάζουμε πολλαπλασιάζοντας όλους τους πρώτους αριθμούς της ακολουθίας και προσθέτοντας ένα:

$$q={\alpha }_1\cdot {\alpha }_2\cdot {\alpha }_3\cdot \dots \cdot {\alpha }_{\nu }+1$$

Τώρα πρέπει να δείξουμε ότι αυτός ο αριθμός είτε είναι πρώτος είτε με κάποιον τρόπο παράγει πρώτο αριθμό. Ξέρουμε ότι το q είναι φυσικός αριθμός και ότι κάθε φυσικός αριθμός μπορεί να εκφραστεί ως γινόμενο πρώτων αριθμών. Ωστόσο, κανένας πρώτος αριθμός α_i δεν διαιρεί ακριβώς τον αριθμό q, η διαίρεση αφήνει πάντα υπόλοιπο ένα. Αν προσπαθούσαμε να διαιρέσουμε τον αριθμό q για παράδειγμα με τον πρώτο αριθμό α₂, θα είχαμε:

$$\frac{{\alpha }_1\cdot {\alpha }_2\cdot {\alpha }_3\cdot \dots \cdot {\alpha }_{\nu }+1}{{\alpha }_2}=\frac{{\alpha }_1\cdot {\alpha }_2\cdot {\alpha }_3\cdot \dots \cdot {\alpha }_{\nu }}{{\alpha }_2}+\frac{1}{{\alpha }_2}=$$

$$={\alpha }_1\cdot {\alpha }_3\cdot {\alpha }_4\cdot \dots \cdot {\alpha }_{\nu }+\frac{1}{{\alpha }_2}$$

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

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

1. Κάθε φυσικός αριθμός μπορεί να εκφραστεί ως κάποιο γινόμενο πρώτων αριθμών.
2. Σύμφωνα με την υπόθεση, η ακολουθία α_ν περιέχει όλους τους υπάρχοντες πρώτους αριθμούς.
3. Τροποποιούμε την πρώτη πρόταση έτσι ώστε κάθε φυσικός αριθμός να μπορεί να εκφραστεί ως γινόμενο επιλεγμένων όρων της ακολουθίας α_ν, επειδή αυτή περιέχει όλους τους πρώτους αριθμούς.
4. Αποδείξαμε ότι κανένας αριθμός της ακολουθίας α_ν δεν διαιρεί τον αριθμό q.
5. Έτσι προέκυψε άτοπο με την υπόθεση → αν πρέπει να μπορούμε να αναλύσουμε κάθε φυσικό αριθμό σε γινόμενο πρώτων αριθμών και η ακολουθία α_ν δεν περιέχει κανέναν αριθμό που διαιρεί το q, τότε πρέπει να υπάρχουν άλλοι πρώτοι αριθμοί, που διαιρούν το q και αποτελούν την ανάλυση του αριθμού q σε γινόμενο πρώτων παραγόντων.

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