Matematička indukcija
Matematička indukcija je metod matematičkog dokazivanja koji se obično koristi da se utvrdi da je dati iskaz tačan za sve prirodne brojeve. Ovo se vrši
- dokazivanjem da je prvi u beskonačnom nizu iskaza tačan, i zatim
- dokazivanjem da ako je neki iskaz u beskonačnom nizu iskaza tačan, onda je tačan i njemu sledeći iskaz
Matematičku indukciju ne treba shvatati kao oblik induktivnog rezonovanja, koje se smatra ne-rigoroznim u matematici (vidi problem indukcije). U stvari, matematička indukcija je oblik deduktivnog rezonovanja, i potpuno je rigorozna.
Metod se može proširiti da dokaže izjave o opštijim dobro utemeljenim strukturama, kao što su stabla; ova generalizacija, poznata kao strukturna indukcija, koristi se u matematičkoj logici i računarstvu. Matematička indukcija u ovom proširenom smislu je usko povezana sa rekurzijom. Matematička indukcija je pravilo zaključivanja koje se koristi u formalnim dokazima i predstavlja osnovu većine dokaza ispravnosti za kompjuterske programe.[3]
Iako njeno ime može sugerisati drugačije, matematičku indukciju ne treba mešati sa induktivnim rezonovanjem koje se koristi u filozofiji (pogledajte problem indukcije). Matematički metod ispituje beskonačno mnogo slučajeva da bi dokazao opštu tvrdnju, ali to čini pomoću konačnog lanca deduktivnog zaključivanja koji uključuje promenljivu , koja može uzeti beskonačno mnogo vrednosti.[4]
Istorija[uredi | uredi izvor]
Najraniji tragovi matematičke indukcije se mogu naći u Euklidovom dokazu da postoji beskonačno puno prostih brojeva, i Baskarinom ciklidnom metodu[5] Forma dokaza matematičkom indukcijom se javlja u knjizi koju je napisao Al-Karadži oko 1000. godine, koji ju je između ostalog koristio da dokaže binomnu teoremu i Paskalov trougao.[6][7]
Nijedan od ovih starih matematičara nije eksplicitno dao induktivnu hipotezu. Prvo rigorozno izlaganje principa indukcije je dao Frančesko Mauroliko, u svom delu Arithmeticorum libri duo (1575), koji je koristio ovu tehniku da dokaže da je zbir prvih n neparnih celih brojeva jednak n2. Indukciju su takođe nezavisno otkrili Švajcarac Jakob Bernuli i Francuzi Paskal i Ferma.[5]
Formalni opis[uredi | uredi izvor]
Najjednostavniji i najuobičajeniji oblik matematičke indukcije dokazuje da neki iskaz važi za sve prirodne brojeve n. Ovaj dokaz se sastoji iz dva koraka:
- Baza indukcije: pokazuje se da iskaz važi kada je n = 0.
- Induktivni korak: pokazuje se da ako iskaz važi za n = m, onda isti iskaz važi i za n = m + 1.
Korišćenje reči ako u induktivnom koraku se naziva induktivnom hipotezom. Kako bi se sproveo induktivni korak, pretpostavlja se da induktivna hipoteza važi (tačnije da je iskaz tačan za n = m) i onda se koristi ova pretpostavka da se dokaže iskaz za n = m + 1.
Ovaj metod funkcioniše na sledeći način. Prvo se dokaže da je iskaz tačan za početnu vrednost, a zatim se dokaže da je proces prelaska sa neke vrednosti na sledeću ispravan. Ako su oba dokazana, onda se do tačnosti iskaza za svaku vrednost može doći uzastopnim ponavljanjem ovog procesa. Ovo se može posmatrati kao efekat domina; Ako imamo dugačak niz domina, i ako smo sigurni da:
- Prva domina može da padne
- Koja god domina da padne, oboriće i sledeću dominu,
onda se može zaključiti da će sve domine pasti, ukoliko se obori prva domina.
Osnovna pretpostavka ili aksioma indukcije (prihvata se, ne dokazuje) je ispisana logičkim simbolima,
gde je P dati iskaz, a n prirodan broj.
Korak 1. dokazati P(0) - formula važi za ceo broj 0.
Korak 2. dokazati da za svaki prirodan broj k, P(k) implicira P(k+1). Da bi se ovo sprovelo, pretpostavlja se da važi P(k) i pokazuje se da iz ove pretpostavke sledi da važi P(k+1). Ovo ne znači zamenu (k+1) u P(k) - ovo je vrlo česta greška koja se sastoji u pretpostavljanju onoga šta tek treba da se dokaže. Zajedno koraci 1. i 2. impliciraju da P(n) važi za svako n veće ili jednako 0. U opštem slučaju, ako je P(s) dokazano, gde s može biti negativan ceo broj (zamislimo domine numerisane od -20 pa naviše), onda P važi za svako n veće ili jednako s.
Primer[uredi | uredi izvor]
Pretpostavimo da želimo da dokažemo iskaz:
Za sve prirodne brojeve n; obeležimo ovaj iskaz kao P(n). (Ovo je specijalni slučaj Faulhaberove formule.) Ovo je jednostavna formula za sumu pozitivnih prirodnih brojeva manjih ili jednakih broju n. Dokaz da je ovaj iskaz tačan za sve prirodne brojeve n sledi.
Proverimo da li je iskaz tačan za n = 1. Suma samog broja 1 je prosto 1. A 1(1 + 1) / 2 = 1. Znači, iskaz je tačan za n = 1. Dokazali smo da P(1) važi.
Sada moramo da pokažemo da ako iskaz važi kada je n = m, onda on takođe važi i kada je n = m + 1. Ovo se može izvesti na sledeći način.
Pretpostavimo da je iskaz tačan za n = m, tj,
Dodavanjem m + 1 sa obe strane se ne menja jednakost:
Algebarskom manipulacijom, sa desne strane dobijamo
Stoga imamo
Primetimo da je ovo ekvivalentno tvrđenju P(m + 1). Ovaj dokaz je kondicionalan: načinili smo pretpostavku da je P(m) tačno, i iz toga smo izveli P(m + 1). Stoga, ako je P(m) tačno, onda i P(m + 1) mora biti tačno. Simbolički, pokazali smo da
Sada, kako bismo završili, koristimo proces matematičke indukcije:
- Znamo da je P(1) tačno.
- Kako P(1) implicira P(1 + 1), tačno je i P(2).
- Slično, kako P(2) implicira P(2 + 1), dobijamo P(3).
- Sa P(3), dobijamo P(4).
- Iz P(4), sledi P(5).
- I tako dalje. (ovde nastupa aksioma matematičke indukcije.)
- Možemo da zaključimo da P(n) važi za svaki prirodan broj n. Q. E. D.
Vidi još[uredi | uredi izvor]
Izvori[uredi | uredi izvor]
- ^ Matt DeVos, Mathematical Induction, Simon Fraser University
- ^ Gerardo con Diaz, Mathematical Induction Arhivirano 2013-05-02 na sajtu Wayback Machine, Harvard University
- ^ Anderson, Robert B. (1979). Proving Programs Correct. New York: John Wiley & Sons. str. 1. ISBN 978-0471033950.
- ^ Suber, Peter. „Mathematical Induction”. Earlham College. Arhivirano iz originala 24. 5. 2011. g. Pristupljeno 26. 3. 2011.
- ^ a b Cajori (1918), str. 197: Proces rezonovanja koji se naziva matematičkom indukcijom ima nekoliko nezavisnih korena. Može se pratiti do Švajcarca Jakoba (Džejmsa) Bernulija, Francuza B. Paskala i P. Ferma, Italijana F. Maurolicusa. [...] Ako se malo čita između redova, mogu se naći tragovi matematičke indukcije i ranije, u spisima Indusa i Grka, na primer u ciklidnom metodu Baskare i u Euklidovom dokazu da prostih brojeva ima beskonačno mnogo.
- ^ Katz (1998), pp. 255-259.; „Još jedna važna ideja koju je uveo Al-Karadži, a nastavili Al-Samav'al i drugi je bio induktivni argument za rad sa odrećenim aritmetičkim nizovima”
- ^ O'Connor, John J; Edmund F. Robertson "Abu Bekr ibn Muhammad ibn al-Husayn Al-Karaji". MacTutor History of Mathematics archive. „Al-Karadži takođe koristi oblik matematičke indukcije u svojim argumentima, mada zasigurno ne daje rigorozno izlaganje ovog principa.”
Literatura[uredi | uredi izvor]
- Franklin, J.; Daoud, A. (2011). Proof in Mathematics: An Introduction. Sydney: Kew Books. ISBN 978-0-646-54509-7. (Ch. 8.)
- Hazewinkel Michiel, ur. (2001). „Mathematical induction”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104.
- Hermes, Hans (1973). Introduction to Mathematical Logic. Hochschultext. London: Springer. ISBN 978-3540058199. ISSN 1431-4657.
- Knuth, Donald E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd изд.). Addison-Wesley. ISBN 978-0-201-89683-1. (Section 1.2.1: Mathematical Induction, pp. 11–21.)
- Kolmogorov, Andrey N.; Fomin, Sergei V. (1975). Introductory Real Analysis. Silverman, R. A. (trans., ed.). New York: Dover. ISBN 978-0-486-61226-3. (Section 3.8: Transfinite induction, pp. 28–29.)
- Acerbi, Fabio (август 2000). „Plato: Parmenides 149a7-c3. A Proof by Complete Induction?”. Archive for History of Exact Sciences. 55 (1): 57—76. JSTOR 41134098. doi:10.1007/s004070000020.
- Bussey, W. H. (1917). „The Origin of Mathematical Induction”. American Mathematical Monthly. 24 (5): 199—207. JSTOR 2974308. doi:10.2307/2974308.
- Cajori, Florian (1918). „Origin of the Name "Mathematical Induction"”. The American Mathematical Monthly. 25 (5): 197—201. JSTOR 2972638. doi:10.2307/2972638.
- Fowler, D. (1994). „Could the Greeks Have Used Mathematical Induction? Did They Use It?”. Physis. XXXI: 253—265.
- Freudenthal, Hans (1953). „Zur Geschichte der vollständigen Induction”. Archives Internationales d'Histoire des Sciences. 6: 17—37.
- Hyde, Dominic; Raffman, Diana (2018), Zalta, Edward N., ур., „Sorites Paradox”, The Stanford Encyclopedia of Philosophy (Summer 2018 изд.), Metaphysics Research Lab, Stanford University, Приступљено 23. 10. 2019
- Katz, Victor J. (1998). History of Mathematics: An Introduction. Addison-Wesley. ISBN 0-321-01618-1.
- Peirce, Charles Sanders (1881). „On the Logic of Number”. American Journal of Mathematics. 4 (1–4): 85—95. JSTOR 2369151. MR 1507856. doi:10.2307/2369151. Reprinted (CP 3.252-88), (W 4:299-309)
- Rabinovitch, Nachum L. (1970). „Rabbi Levi Ben Gershon and the origins of mathematical induction”. Archive for History of Exact Sciences. 6 (3): 237—248. doi:10.1007/BF00327237.
- Rashed, Roshdi (1972). „L'induction mathématique: al-Karajī, as-Samaw'al”. Archive for History of Exact Sciences (na jeziku: French). 9 (1): 1—21. doi:10.1007/BF00348537.
- Rashed, R. (1994), „Mathematical induction: al-Karajī and al-Samawʾal”, The Development of Arabic Mathematics: Between Arithmetic and Algebra, Boston Studies in the Philosophy of Science (na jeziku: engleski), 156, Springer Science & Business Media, ISBN 9780792325659
- Shields, Paul (1997). „Peirce's Axiomatization of Arithmetic”. Ur.: Houser; et al. Studies in the Logic of Charles S. Peirce.
- Simonson, Charles G. (zima 2000). „The Mathematics of Levi ben Gershon, the Ralbag” (PDF). Bekhol Derakhekha Daehu. Bar-Ilan University Press. 10: 5–21.
- Unguru, S. (1991). „Greek Mathematics and Mathematical Induction”. Physis. XXVIII: 273—289.
- Unguru, S. (1994). „Fowling after Induction”. Physis. XXXI: 267—272.
- Vacca, G. (1909). „Maurolycus, the First Discoverer of the Principle of Mathematical Induction”. Bulletin of the American Mathematical Society. 16 (2): 70—73. doi:10.1090/S0002-9904-1909-01860-9 .
- Yadegari, Mohammad (1978). „The Use of Mathematical Induction by Abū Kāmil Shujā' Ibn Aslam (850-930)”. Isis. 69 (2): 259—262. JSTOR 230435. doi:10.1086/352009.
- Stuhlmüller, A.; Goodman, N.D. (jun 2014). „Reasoning about reasoning by nested conditioning: Modeling theory of mind with probabilistic programs”. Cognitive Systems Research. 28: 80—99. doi:10.1016/j.cogsys.2013.07.003.
- Lucci, Stephen; Kopec, Danny (2015). Artificial Intelligence in the 21st Century (na jeziku: engleski). Stylus Publishing, LLC. ISBN 978-1-944534-53-0.
- Tagiew, Rustam (2008). „Simplest Scenario for Mutual Nested Modeling in Human-Machine-Interaction”. KI 2008: Advances in Artificial Intelligence (na jeziku: engleski). Springer: 364—371. doi:10.1007/978-3-540-85845-4_45.
- Fagin, Ronald; Halpern, Joseph Y.; Moses, Yoram; Vardi, Moshe Y. (mart 1999). „Common knowledge revisited”. Annals of Pure and Applied Logic. 96 (1–3): 89—105. arXiv:cs/9809003 . doi:10.1016/S0168-0072(98)00033-5.
- van der Hoek, Wiebe; van Ditmarsch, Hans (2007). Dynamic epistemic logic. Springer. ISBN 978-1-4020-5838-7.
Spoljašnje veze[uredi | uredi izvor]
- „Forward-Backward Induction | Brilliant Math & Science Wiki”. brilliant.org (na jeziku: engleski). Pristupljeno 23. 10. 2019.
- Cours d'analyse de l'École Royale Polytechnique, première partie, Analyse algébrique, Cauchy, Augustin-Louis (1821).