Μαθηματική επαγωγή

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

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

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

$1+2+3+\cdots +\nu ={\frac {\nu (\nu +1)}{2}}$

Ιστορική Αναδρομή

Εχουν διατυπωθεί διάφορες θεωρίες και απόψεις σχετικά με το ποιος ανακάλυψε για πρώτη φορά τη διαδικασία της μαθηματικής επαγωγής. Οι περισσότεροι πάντως θεωρούν τον Γάλλο μαθηματικό Πασκάλ ως τον πρώτο μαθηματικό που διατύπωσε τη μαθηματική επαγωγή με σαφή και συστηματικό τρόπο. Ιστορικά, η άποψη αυτή επικρατούσε κατά τον 19ο αιώνα μέχρι και τις αρχές του 20ου αιώνα. Το 1909 δημοσιεύθηκε ένα άρθρο τριών σελίδων του Ιταλού μαθηματικού George Vacca, ο οποίος υποστήριζε ότι ο πρώτος μαθηματικός που χρησιμοποίησε την επαγωγή συστηματικά ήταν ο Ιταλός βενεδικτίνος μοναχός Φραγκίσκος Μαυρόλυκος το 1557. Μάλιστα έγινε γνωστό ότι ο Πασκάλ αναφέρθηκε στο έργο του Μαυρόλυκου (σε ιδέες σχετικές με την επαγωγή), σε μια επιστολή του. Το σχόλιο του Πασκάλ αφορά την απόδειξη της πρότασης ότι το διπλάσιο του n-οστού τριγωνικού αριθμού μείον το n ισούται με $n^{2}$. Σε αυτό το σημείο ο Πασκάλ αναφέρει ότι η απόδειξη της σχέσης είναι εύκολη κατά τον Μαυρόλυκο, δείχνοντας έτσι ότι μάλλον γνώριζε το έργο του. Αξίζει να σημειωθεί ότι ο Μαυρόλυκος (1494-1575) ήταν ελληνικής καταγωγής μαθηματικός που είχε εντρυφήσει στη μελέτη της ελληνικής γραμματείας και βοήθησε ιδιαίτερα στην απορρόφηση αυτών των γνώσεων στη Δύση.

Μερικές δεκαετίες αργότερα (1953) ο Ολλανδός μαθηματικός (γερμανικής καταγωγής) Hans Freudenthal μελέτησε το εν λόγω βιβλίο του Μαυρόλυκου και κατέληξε στο συμπέρασμα ότι όντως σε μερικά σημεία του βιβλίου φαίνεται πως χρησιμοποιείται μια διαδικασία παρόμοια με τη μαθηματική επαγωγή. Παρόλα αυτά ο Freudenthal υποστήριξε ότι η μαθηματική επαγωγή δεν ορίζεται συστηματικά και με ακριβή τρόπο από τον Μαυρόλυκο, αλλά πως ο Πασκάλ ήταν ο πρώτος που όρισε τη διαδικασία με αυστηρότητα και τη χρησιμοποίησε με συστηματικό τρόπο. Φαίνεται ότι o Freudenthal πίστευε πως ο Μαυρόλυκος δεν είχε ξεκάθαρη εικόνα της μαθηματικής επαγωγής, αλλά ότι ο Πασκάλ συνέχισε και τελειοποίησε το έργο του Μαυρόλυκου. ΄Αλλοι ερευνητές εντόπισαν δείγματα μαθηματικής επαγωγής σε παλαιότερα έργα όπως αυτό του ραββίνου Γερσονίδη (1288-1344) ή των Αράβων μαθηματικών αλ-Καράτζι (953-1029) και αλ-Σαμαβάλ (1130-1180). Πολλοί είναι εκείνοι που πιστεύουν ότι οι πρώτες αναφορές σε ιδέες που σχετίζονται με τη μαθηματική επαγωγή γίνονται στο έργο του Ευκλείδη και στον Παρμενίδη του Πλάτωνα . ΄Ισως αυτά τα έργα να ήταν πηγή έμπνευσης για τον Μαυρόλυκο (που ξέρουμε ότι τα γνώριζε) και τους υπολοίπους.

Περιγραφή της μεθόδου

Είναι βολικό να μιλούμε για την πρόταση προς απόδειξη συμβολίζοντας την με P(ν) και αντικαθιστώντας όπου ν τον αριθμό που θέλουμε.

Η πιο απλή και πιο συνήθης μορφή της μεθόδου είναι αυτή που αποδεικνύει ότι μια πρόταση P(ν) είναι αληθής για όλους τους φυσικούς αριθμούς ν και αποτελείται από τα παρακάτω τρία βήματα:

1. Βασικό βήμα: δείχνουμε ότι η πρόταση P(ν) ισχύει για ν = 1.

2. Επαγωγική υπόθεση: υποθέτουμε ότι η πρόταση P(ν) είναι αληθής για κάποιο ν = κ, δηλαδή ότι ισχύει P(κ).

3. Επαγωγικό βήμα: χρησιμοποιώντας την επαγωγική υπόθεση προσπαθούμε να αποδείξουμε ότι αν η πρόταση ισχύει για ν = κ τότε ισχύει και για ν = κ + 1 δηλαδή ότι: ξεκινώντας από την υπόθεση ότι ισχύει P(κ) καταλήγουμε ότι ισχύει P(κ + 1).

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

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

• Αν σπρώξουμε το πρώτο ντόμινο στη σειρά, αυτό θα πέσει.

• Όταν ένα οποιοδήποτε από τα ντόμινο πέσει τότε πέφτει και το επόμενο.

Έτσι μπορούμε να είμαστε απόλυτα βέβαιοι ότι αν σπρώξουμε το πρώτο ντόμινο για να πέσει τότε όλα τα ντόμινο θα πέσουν.

Συμβολικά η βασική μορφή της επαγωγής μπορεί να γραφτεί ως εξής:

$(\underbrace {P(1)} _{\text{Βασικό βήμα}}\wedge \underbrace {\forall \kappa \in \mathbb {N} .P(\kappa )\Rightarrow P(\kappa +1)} _{\text{Επαγωγικό βήμα}})\Leftrightarrow \forall \nu \in \mathbb {N} .P(\nu )$

Παράδειγμα

Ας υποθέσουμε ότι θέλουμε να αποδείξουμε την πιο κάτω μαθηματική πρόταση (την οποία θα συμβολίσουμε με P(ν)) :

$1+2+3+\cdots +\nu ={\frac {\nu (\nu +1)}{2}}$

για κάθε $\nu \in \mathbb {N}$

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

• Ελέγχουμε ότι η πρόταση ισχύει για ν = 1, [επαληθεύουμε δηλαδή ότι ισχύει η P(1)]. Είναι προφανές ότι το άθροισμα των πρώτων 1 φυσικών αριθμών είναι 1.

$1={\frac {1(1+1)}{2}}=1$

• Στη συνέχεια υποθέτουμε ότι η πρόταση είναι αληθής για κάποιο φυσικό αριθμό ν = κ [δηλαδή ότι η P(κ) είναι αληθής].

$1+2+3+\cdots +\kappa ={\frac {\kappa (\kappa +1)}{2}}$, (επαγωγική υπόθεση)

• Τέλος προσπαθούμε να αποδείξουμε ότι, αν η πρόταση ισχύει για ν = κ, τότε ισχύει και για ν = κ + 1, [αν ισχύει η P(κ), τότε ισχύει και η P(κ + 1)] δηλαδή ότι:

$1+2+3+\cdots +\kappa +\kappa +1={\frac {(\kappa +1)(\kappa +2)}{2}}$

Το κάνουμε αυτό χρησιμοποιώντας την επαγωγική υπόθεση. Έχουμε δεχτεί ότι ισχύει:

$1+2+3+\cdots +\kappa ={\frac {\kappa (\kappa +1)}{2}}$

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

$1+2+3+\cdots +\kappa +\kappa +1={\frac {\kappa (\kappa +1)}{2}}+{\frac {2(\kappa +1)}{2}}$$={\frac {(\kappa ^{2}+3\kappa +2)}{2}}$$={\frac {(\kappa +1)(\kappa +2)}{2}}$

Αυτό που έχουμε καταφέρει είναι να δείξουμε ότι, αν η P(κ) είναι αληθής, τότε είναι αληθής και η P(κ + 1). Συμβολικά:

$P(\kappa )\Rightarrow P(\kappa +1)$

Έτσι το μόνο που απομένει για να ολοκληρωθεί η απόδειξη είναι να βρούμε ένα φυσικό αριθμό κ για τον οποίο η P(κ) είναι αληθής. Τον αριθμό αυτό όμως τον έχουμε ήδη βρει και είναι ο αριθμός ν = κ = 1 για τον οποίο αποδείξαμε από την αρχή ότι ισχύει η P(1). Έτσι:

1. Ισχύει η P(1), δηλαδή η πρόταση είναι αληθής αν το ν έχει την τιμή 1.
2. Η P(ν) είναι αληθής αν ν = 1, επομένως η P(κ) είναι αληθής για κ = 1. Έχουμε όμως αποδείξει ότι, αν για κάποιο κ η P(κ) είναι αληθής, τότε είναι αληθής και η P(κ +1). Επομένως και η P(2) είναι αληθής.
3. Αν είναι αληθής η P(2) τότε είναι αληθής και η P(3), άρα και η P(4) και ούτω καθεξής.

4. Η πρόταση P(ν) είναι αληθής για όλους τους φυσικούς αριθμούς ν.

Άλλες μορφές επαγωγής

Η μαθηματική επαγωγή μπορεί να παρουσιάσει διαφορετικές μορφές ανάλογα με την περίπτωση. Αν θέλουμε να αποδείξουμε ότι μία πρόταση για όλους τους φυσικούς αριθμούς με μαθηματική επαγωγή μπορούμε να την αποδείξουμε εξειδικευμένα για κάποιους αριθμούς α,β,γ ή περισσότερους και έπειτα να αποδείξουμε τη συνεπαγωγή ή τις συνεπαγωγές. Η συνεπαγωγή δεν είναι ανάγκη να είναι της μορφής $P(\nu )\Rightarrow P(\nu +1)$, αλλά μπορεί να είναι και της μορφής $P(\nu )\Rightarrow P(\nu -1)$ ή ακόμα και της μορφής $P(\nu )\Rightarrow P(\nu +2)$, αν είναι απαραίτητο. Σημαντικό όμως είναι σε κάθε περίπτωση να εξασφαλιστεί ότι η επαγωγή διατρέχει το σύνολο που θέλουμε είτε είναι το σύνολο των φυσικών αριθμών ή κάποιο υποσύνολό του ή ακόμα και αν αναφέρεται στο σύνολο των ακεραίων.

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

1. Η πρόταση ισχύει για κάποιο φυσικό αριθμό ν₀,
2. Αν η πρόταση ισχύει για κάποιο κ ≥ ν₀ ισχύει και για το κ + 1,

για να έχουμε την πλήρη απόδειξη της πρότασης.

Για παράδειγμα, αυτή την μέθοδο χρησιμοποιούμε όταν θέλουμε να αποδείξουμε ότι: ν² > 2ν για ν ≥ 3.

Πλήρης ή Ισχυρή Επαγωγή

Μια άλλη μορφή της επαγωγής με ισχυρότερη υπόθεση είναι η εξής:

1. Βασικό βήμα: δείχνουμε ότι η πρόταση $P(\nu )$ ισχύει για $\nu =1$ (όπως στην βασική μορφή).

2. Επαγωγική υπόθεση: υποθέτουμε ότι η πρόταση $P(\nu )$ είναι αληθής για κάθε $\nu \leq \kappa$, δηλαδή ότι ισχύει $P(1),P(2),\ldots ,P(\kappa )$ (η υπόθεση εδώ είναι ισχυρότερη από ότι στην βασική μορφή).

3. Επαγωγικό βήμα: χρησιμοποιώντας την επαγωγική υπόθεση προσπαθούμε να αποδείξουμε ότι αν η πρόταση ισχύει για κάθε $\nu \leq \kappa$ τότε ισχύει και για $\nu =\kappa +1$.

Συμβολικά, μπορεί να γραφτεί ως

$(\underbrace {P(1)} _{\text{Βασικό βήμα}}\wedge \underbrace {\forall \kappa \in \mathbb {N} .(\forall m\leq \kappa .P(m))\Rightarrow P(\kappa +1)} _{\text{Επαγωγικό βήμα}})\Leftrightarrow \forall \nu \in \mathbb {N} .P(\nu )$

και είναι (λογικά) ισοδύναμη της βασικής μορφής της επαγωγής.

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

Περαιτέρω ανάγνωση

Εξωτερικοί σύνδεσμοι

• Δ. Φωτάκης, Δ. Σούλιου, Μαθηματική Επαγωγή.
• Μαθηματική επαγωγή και λίστα από εφαρμογές

Ελληνικά άρθρα

• Τουμάσης Χαράλαμπος (1977). «Μια πρόταση της Μαθηματικής Επαγωγής και εφαρμογές αυτής». Ευκλείδης Β΄ (2): 25-27. 
• «Άλγεβρα: Μαθηματική επαγωγή». Ευκλείδης Β΄ (1): 31-34. 1978. http://www.hms.gr/apothema/?s=sa&i=3553. 
• Ματζαβίνος Ν.; Πουλημένος Γ. (1982). «Μερικές σκέψεις για την τέλεια επαγωγή». Ευκλείδης Β΄ (1): 28-31. http://www.hms.gr/apothema/?s=sa&i=3553. 
• Π. Χριστοφόρου (1988). «Για τη μέθοδο της τέλειας επαγωγής». Ευκλείδης Β΄ (1): 38-41. http://www.hms.gr/apothema/?s=sa&i=2839. 

Ξενόγλωσσα άρθρα

• Öhman, Lars–Daniel (Σεπτεμβρίου 2019). «Are Induction and Well-Ordering Equivalent?». The Mathematical Intelligencer 41 (3): 33–40. doi:10.1007/s00283-019-09898-4. 
• Ernest, Paul (Ιουνίου 1982). «Mathematical Induction: A Recurring Theme». The Mathematical Gazette 66 (436): 120–125. doi:10.2307/3617747. https://archive.org/details/sim_mathematical-gazette_1982-06_66_436/page/120. 
• Ernest, Paul (Μαΐου 1984). «Mathematical induction: A pedagogical discussion». Educational Studies in Mathematics 15 (2): 173–189. doi:10.1007/BF00305895. https://archive.org/details/sim_educational-studies-in-mathematics_1984-05_15_2/page/173. 
• Brumfiel, Charles (1974). «A note on mathematical induction». The Mathematics Teacher 67 (7): 616-618. https://www.jstor.org/stable/27959858. 
• Shmuel Avital; Rodney T. Hansen. «Mathematical Induction in the Classroom». Educational Studies in Mathematics 7 (4): 399-411. https://www.jstor.org/stable/3481946.