Μια Μαθηματική Παγίδα: Όλοι οι Θετικοί Ακέραιοι είναι ίσοι;

Το $1988$, ο μαθηματικός T.I. Ramsamujh του Διεθνούς Πανεπιστημίου της Φλόριντα προσέφερε μια "απόδειξη" που ανατρέπει τη λογική μας:

"Η απόδειξη είναι φυσικά λανθασμένη, αλλά το σφάλμα είναι τόσο όμορφα κρυμμένο που το έργο του εντοπισμού του γίνεται μια ενδιαφέρουσα άσκηση."

Ας δούμε την "απόδειξη":

Έστω $p(n)$ η πρόταση, "Εάν το μέγιστο των δύο θετικών ακεραίων είναι $(n)$, τότε οι ακέραιοι είναι ίσοι."

• Βάση επαγωγής: $p(1)$ είναι αληθές, αφού αν το μέγιστο των ακεραίων είναι $1$, τότε και οι δύο είναι $1$.
• Επαγωγικό βήμα: Υποθέτουμε ότι $p(n)$ ισχύει. Για $u$ και $v$ με μέγιστο $n+1$, το μέγιστο των $u-1$ και $v-1$ είναι $n$. Από την επαγωγική υπόθεση, $u-1=v-1$, άρα $u=v$. 

Επομένως, $p(n+1)$ ισχύει.

Αλλά πού είναι το λάθος;

Το σφάλμα στην απόδειξη:

Η λογική της απόδειξης καταρρέει όταν υποτίθεται ότι, αν το μέγιστο των δύο αριθμών είναι $n+1$, τότε το μέγιστο των $u-1$ και $v-1$ είναι $n$, και από αυτό το συμπέρασμα προκύπτει ότι $u=v$. Ωστόσο, αυτό παραβλέπει μια κρίσιμη περίπτωση.

Ας το δούμε πιο αναλυτικά:

Η επαγωγή υποθέτει ότι αν το μέγιστο των $u$ και $v$ είναι $n+1$, τότε αν αφαιρέσουμε $1$ από καθέναν, το μέγιστο των νέων αριθμών (δηλαδή $u-1$ και $v-1$) θα είναι $n$, και συνεπώς οι δύο αριθμοί $u-1$ και $v-1$ θα είναι ίσοι, άρα και $u=v$.

Το λάθος είναι ότι αυτή η λογική δεν ισχύει σε όλες τις περιπτώσεις. Ειδικότερα, αν κάποιος από τους δύο αριθμούς $u$ ή $v$ είναι ακριβώς $n+1$ και ο άλλος είναι μικρότερος από $n+1$, τότε το μέγιστο των $u-1$ και $v-1$ δεν θα είναι απαραίτητα $n$, και η εξίσωση $u-1=v-1$ δεν θα ισχύει. Αυτό αγνοείται στην επαγωγή, οδηγώντας σε λανθασμένο συμπέρασμα.

Απλοποιημένη εξήγηση:

Η απόδειξη υποθέτει ότι, αν το μέγιστο των δύο αριθμών είναι $n+1$, τότε, όταν αφαιρέσουμε $1$ από καθέναν, το μέγιστο των νέων αριθμών (δηλαδή $u-1$ και $v-1$) θα είναι πάντα $n$. Ωστόσο, στην πραγματικότητα, αν ο ένας αριθμός είναι $n+1$ και ο άλλος είναι μικρότερος από $n+1$, το μέγιστο των $u-1$ και $v-1$ μπορεί να είναι μικρότερο από $n$, και επομένως δεν ισχύει ότι $u=v$.