ดูต้นฉบับสำหรับ การอุปนัยเชิงคณิตศาสตร์

{{distinguish|การอนุมานแบบอุปนัย|การให้เหตุผลแบบอุปนัย}}

[[ไฟล์:Dominoeffect.png|thumb|right|alt=ภาพของโดมิโนซึ่งตั้งเรียงต่อกัน เมื่อโดมิโนตัวหนึ่งถูกผลักล้มตัวอื่น ๆ จะล้มตามมา นี่ถูกนำมาเปรียบเทียบกับกระบวนการอุปนัยเชิงคณิตศาสตร์|การอุปนัยเชิงคณิตศาสตร์สามารถถูกแสดงให้เห็นอย่างอรูปนัยได้ด้วยการเทียบกับผลกระทบลูกโซ่แบบ[[ทฤษฎีโดมิโน|โดมิโน]]ที่ล้มทับกัน<ref>Matt DeVos, [https://www.sfu.ca/~mdevos/notes/graph/induction.pdf ''Mathematical Induction''], [[Simon Fraser University]]</ref><ref>Gerardo con Diaz, ''[http://www.math.harvard.edu/archive/23a_fall_05/Handouts/induction.pdf Mathematical Induction]{{Webarchive|url=https://web.archive.org/web/20130502163438/http://www.math.harvard.edu/archive/23a_fall_05/Handouts/induction.pdf |date=2 May 2013 }}'', [[Harvard University]]</ref>]]

'''การอุปนัยเชิงคณิตศาสตร์''' ({{langx|en|Mathematical induction}}) เป็นเทคนิค[[การพิสูจน์เชิงคณิตศาสตร์]]ที่ใช้พิสูจน์ว่า[[ข้อความ (ตรรกศาสตร์)|ข้อความ]] ''P''(''n'') เป็นจริงสำหรับทุกจำนวน[[จำนวนธรรมชาติ]] ''n''&nbsp;=&nbsp;0,&nbsp;1,&nbsp;2,&nbsp;3,&nbsp;. . .  นั่นคือกรณีต่าง ๆ ''P''(0), ''P''(1), ''P''(2), ''P''(3), . . . . ของข้อความดังกล่าวที่มีจำนวนมากไม่สิ้นสุดเป็นจริงทั้งหมด การอุปนัยเริ่มจากการพิสูจน์กรณีที่ง่ายก่อน แล้วพิสูจน์ว่าหากข้อความเป็นจริงในกรณีใดแล้ว กรณีถัดไปจะเป็นจริงด้วย เราสามารถใช้คำอุปมาเพื่ออธิบายการอุปนัยอย่างคร่าว โดยเทียบกับโดมิโนที่ล้มตามกันหรือการปีนบันได:

{{quote 
|"การอุปนัยเชิงคณิตศาสตร์พิสูจน์ว่าเราสามารถปีนบันไดสูงเท่าไหร่ก็ได้ โดยพิสูจน์ว่าสามารถปีนขึ้นขั้นแรกได้ และพิสูจน์ว่าจากแต่ละขั้นสามารถปีนขึ้นขั้นต่อไปได้"{{efn|"Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step)."}}
|''[[Concrete Mathematics]]'', ริมกระดาษหน้า 3
}}

'''การพิสูจน์ด้วยการอุปนัย''' (proof by induction) ประกอบไปด้วยกรณีสองกรณี กรณีแรกคือ '''กรณีฐาน''' (base case หรือ basis) เป็นการพิสูจน์สำหรับข้อความที่ ''n ='' 0 โดยไม่ต้องรู้อะไรเกี่ยวกับกรณีอื่น ๆ เลย กรณีที่สองคือ '''ขั้นตอนอุปนัย''' (induction step) เป็นการพิสูจน์ว่า''ถ้า''ข้อความเป็นจริงสำหรับ ''n = k'' ใด ๆ ''แล้ว'' มันก็ต้องเป็นจริงสำหรับกรณี&nbsp;''n''  = ''k'' + 1 ถัดไปด้วย ขั้นตอนสองขั้นตอนนี้แสดงให้เห็นว่าข้อความนั้นเป็นจริงสำหรับจำนวนธรรมชาติ ''n'' ทุกจำนวน<ref>{{Cite web|url=https://mathvault.ca/math-glossary/#induction|title=The Definitive Glossary of Higher Mathematical Jargon — Proof by Induction|last=|first=|date=2019-08-01|website=Math Vault|language=en-US|url-status=live|archive-url=|archive-date=|access-date=2019-10-23}}</ref> กรณีฐานไม่จำเป็นต้องเริ่มด้วย ''n ='' 0 แต่มักจะเริ่มด้วย ''n ='' 1 และก็เป็นไปได้ที่จะใช้จำนวนธรรมชาติ ''n = N'' คงที่ใด ๆ เพื่อแสดงให้เห็นว่าข้อความเป็นจริงสำหรับจำนวนธรรมชาติ ''n ≥ N'' ทุกตัว

วิธีการนี้สามารถนำมาขยายใช้เพื่อพิสูจน์ข้อความเกี่ยวกับโครงสร้าง[[ความสัมพันธ์รากฐานดี|รากฐานดี]] (well-founded) ที่ทั่วไปมากขึ้นเช่น[[ต้นไม้ (ทฤษฎีเซต)|ต้นไม้]] (tree (set theory)) การวางนัยทั่วไปนี้ซึ่งมีชื่อว่า[[การอุปนัยเชิงโครงสร้าง]] (structural induction) ถูกใช้ใน[[คณิตตรรกศาสตร์]]และ[[วิทยาการคอมพิวเตอร์]] การอุปนัยเชิงคณิตศาสตร์ในความหมายแบบขยายมีความใกล้เคียงกับ[[การเรียกซ้ำ]] การอุปนัยเชิงคณิตศาสตร์เป็น[[กฏการอนุมาน]] (rule of inference) ที่ถูกใช้ใน[[การพิสูจน์เชิงรูปนัย]] (formal proof) และในบางรูปแบบก็เป็นรากฐานของ[[การทวนสอบเชิงรูปนัย|การพิสูจน์ความถูกต้องของโปรแกรมคอมพิวเตอร์]] (formal verification) ทั้งหมด<ref>
{{cite book|last = Anderson|first = Robert B.|title = Proving Programs Correct|publisher = John Wiley & Sons|year = 1979|location = New York|page = [https://archive.org/details/provingprogramsc0000ande/page/1 1]|language = en|url = https://archive.org/details/provingprogramsc0000ande|url-access = registration|isbn = 978-0471033950}}</ref> 

แม้ชื่อจะคล้ายกันแต่ไม่ควรสับสนการอุปนัยเชิงคณิตศาสตร์กับ[[การให้เหตุผลแบบอุปนัย]]ที่ใช้ใน[[ปรัชญา]] (ดู[[ปัญหาของการอุปนัย]] (Problem of induction)) ซึ่งเป็นการสรุปผลที่อาจเป็นไปได้จากตัวอย่างจำนวนมาก การอุปนัยเชิงคณิตศาสตร์เป็นวิธีการทางคณิตศาสตร์ที่ตรวจสอบกรณีจำนวนมากเป็นอนันต์เพื่อพิสูจน์ข้อความทั่วไปข้อหนึ่ง แต่ทำเช่นนั้นด้วย[[การให้เหตุผลแบบนิรนัย]]จำนวนจำกัดข้อความซึ่งใช้[[ตัวแปร (คณิตศาสตร์)|ตัวแปร]] ''n'' แทนค่าจำนวนได้มากเป็นอนันต์ ผลที่ได้เป็นบทพิสูจน์ที่รัดกุม และไม่ใช่ว่าข้อความนั้นน่าจะเป็นอย่างใดอย่างหนึ่ง<ref>{{cite web|url=http://www.earlham.edu/~peters/courses/logsys/math-ind.htm|title=Mathematical Induction|last=Suber|first=Peter|publisher=Earlham College|accessdate=26 March 2011|archive-date=2011-05-24|archive-url=https://web.archive.org/web/20110524104121/http://www.earlham.edu/~peters/courses/logsys/math-ind.htm|url-status=dead}}</ref>

==ประวัติ==
ในปี 370 ก่อนคริสต์ศักราช [[พาร์เมนิดีส (บทสนทนา)|พาร์เมนิเดส]]ของ[[เพลโต]]มีตัวอย่างแรก ๆ ของการพิสูจน์แบบอุปนัยโดยปริยาย{{sfn|Acerbi|2000}} การนำการอุปนัยเชิงคณิตศาสตร์มาใช้อย่างชัดเจนเป็นครั้งแรกที่สุดสามารถพบได้ในการพิสูจน์ของ[[ยุคลิด]]<ref>{{cite web|url=http://primes.utm.edu/notes/proofs/infinite/euclids.html|title=Euclid's Proof of the Infinitude of Primes (c. 300 BC)|author=Chris K. Caldwell|work=utm.edu|accessdate=2016-02-28}}</ref>ที่บอกว่ามีจำนวนเฉพาะมากเป็นอนันต์ เทคนิคการทำซ้ำซึ่งตรงข้ามกันใช้การนับ''ลง''แทนการนับเพิ่มขึ้นที่ละหนึ่งและสามารถพบได้ใน[[ปฏิทรรศน์กองทราย]] (sorites paradox) ซึ่งมีการอ้างเหตุผลว่าหากทราย 1,000,000 เม็ดก่อตัวเป็นกองทรายและการเอาทรายออกเม็ดหนึ่งกองนั้นก็ยังถูกนับได้ว่าเป็นกองทรายแล้ว ทรายเพียงเม็ดเดียว (หรือไม่มีสักเม็ดเลย) ก็เป็นกองทรายเช่นเดิม{{sfn|Hyde|Raffman|2018}}

การพิสูจน์โดยปริยายด้วยการอุปนัยเชิงคณิตศาสตร์แรก ๆ ในประเทศอินเดียปรากฏอยู่ใน "[[จักรวาลวิธี]]" (Chakravala method) ของ[[ภาสคาราที่ 2]] (Bhāskara II)<ref name="Induction Bussey">{{harvp|Cajori|1918|p=197|ps=: 'The process of reasoning called "Mathematical Induction" has had several independent origins. It has been traced back to the Swiss Jakob (James) Bernoulli, the Frenchman B. Pascal and P. Fermat, and the Italian F. Maurolycus. [...] By reading a little between the lines one can find traces of mathematical induction still earlier, in the writings of the Hindus and the Greeks, as, for instance, in the "cyclic method" of Bhaskara, and in Euclid's proof that the number of primes is infinite.'}} '''แปล''': "กระบวนการให้เหตุผลซึ่งเรียกว่า 'การอุปนัยเชิงคณิตศาสตร์' มีจุดกำเนิดอิสระที่หลากหลาย ตั้งแต่ชาวสวิส ยาคอบ แบร์นูลลี, ชาวฝรั่งเศส แบลซ ปัสกาล และ ปีแยร์ เดอ แฟร์มา และชาวอิตาลี ฟรันเชสโก เมาโรลีโก [...] เราสามารถพบร่องรอยของการอุปนัยเชิงคณิตศาสตร์ได้เก่ากว่าเดิมหากอ่านตีความสักหน่อย ไม่ว่าในงานเขียนของชาวฮินดูและกรีก ตัวอย่างเช่น 'จักรวาลวิธี' ของภาสคารา และในการพิสูจน์ว่าจำนวนเฉพาะมีจำนวนมากเป็นอนันต์ของยุคลิด"</ref> และใน ''อัลฟะครี'' (al-Fakhri) ซึ่งถูกเขียนขึ้นในประมาณปี ค.ศ. 1000 โดย[[อัลกะระญี]] (al-Karaji) ซึ่งเขานำมาประยุกต์ใช้กับ[[อนุกรมเลขคณิต]]เพื่อพิสูจน์[[ทฤษฎีบททวินาม]]และคุณสมบัติของ[[สามเหลี่ยมปัสกาล]]{{sfn|Rashed|1994|p=62-84}}<ref>[https://books.google.fr/books?id=HGMXCgAAQBAJ&pg=PA193&lpg=PA193&dq=Al-Karaji+binomial+theorem&source=bl&ots=MftTUxaHoM&sig=4BBQVIkt7eALPJfJ_89MTuNGezY&hl=fr&sa=X&ved=0ahUKEwjhoLuPnu3aAhXCXRQKHb2tBMM4ChDoAQhqMAk#v=onepage&q=Al-Karaji%20binomial%20theorem&f=false/ Mathematical Knowledge and the Interplay of Practices] "The earliest implicit proof by mathematical induction was given around 1000 in a work by the Persian mathematician Al-Karaji" '''แปล''': "การพิสูจน์โดยปริยายด้วยการอุปนัยเชิงคณิตศาสตร์แรกสุดทำขึ้นเมื่อประมาณ ค.ศ. 1000 ในงานของนักคณิตศาสตร์ชาวเปอร์เซีย อัลกะระญี"</ref>

[[เกร์โซนิเดส]] (Gersonides) (ค.ศ. 1288-1344) เป็นผู้ใช้การอุปนัยอย่างเคร่งครัดเป็นครั้งแรก{{sfn|Simonson|2000}}{{sfn|Rabinovitch|1970}} [[แบลซ ปัสกาล]] บัญญัติหลักของการอุปนัยอย่างชัดแจ้งเป็นครั้งแรกใน ''Traité du triangle arithmétique'' (ค.ศ. 1665) ชาวฝรั่งเศสอีกคนหนึ่งชื่อ [[ปีแยร์ เดอ แฟร์มา]] นำหลักการที่เกี่ยวข้องมาใช้: การพิสูจน์อ้อมด้วย[[การพิสูจน์ด้วยการลดหลั่นอนันต์|การลดหลั่นอนันต์]] (Proof by infinite descent)

สมมติฐานการอุปนัยนี้ยังถูกนำมาใช้โดย [[ยาคอบ แบร์นูลลี]] (Jakob Bernoulli) และก็กลายเป็นที่รู้จักตั้งแต่นั้นมา การปฏิบัติต่อหลักการนี้อย่างรูปนัยแบบสมัยใหม่มีขึ้นในคริสตศตวรรษที่ 19 โดย [[จอร์จ บูล]]<ref>"It is sometimes required to prove a theorem which shall be true whenever a certain quantity ''n'' which it involves shall be an integer or whole number and the method of proof is usually of the following kind. ''1st''. The theorem is proved to be true when&nbsp;''n''&nbsp;=&nbsp;1. ''2ndly''. It is proved that if the theorem is true when ''n'' is a given whole number, it will be true if ''n'' is the next greater integer. Hence the theorem is true universally. . .. This species of argument may be termed a continued ''[[Polysyllogism|sorites]]''" (Boole circa 1849 ''Elementary Treatise on Logic not mathematical'' pages 40–41 reprinted in [[Ivor Grattan-Guinness|Grattan-Guinness, Ivor]] and Bornet, Gérard (1997), ''George Boole: Selected Manuscripts on Logic and its Philosophy'', Birkhäuser Verlag, Berlin, {{isbn|3-7643-5456-9}}) '''แปล''': "บางครั้งก็จำเป็นจะต้องพิสูจน์ทฤษฎีบทบทหนึ่งว่าเป็นจริงสำหรับค่า ''n'' ซึ่งเป็นจำนวนเต็มใด ๆ ส่วนวิธีการพิสูจน์นั้นมักจะมีชนิดดังต่อไปนี้ ''หนึ่ง'' ทฤษฎีบทบทนั้นจะถูกพิสูจน์ว่าเป็นจริงเมื่อ&nbsp;''n''&nbsp;=&nbsp;1 ''สอง'' มันจะถูกพิสูจน์ว่าหากทฤษฎีบทนี้เป็นจริงเมื่อ ''n'' เป็นจำนวนเต็มใด ๆ มันก็จะเป็นจริงสำหรับ ''n'' จำนวนต่อไปที่มากกว่าด้วย ดังนั้นแล้วทฤษฎีบทนี้จึงเป็นจริงโดยสากล . .. การอ้างเหตุผลชนิดนี้สามารถเรียกได้ว่าเป็น ''[[พหุตรรกบท|โซริเตส ]]'' (Polysyllogism) ต่อเนื่อง"</ref> [[ออกัสตัส เดอ มอร์แกน]] (Augustus de Morgan), [[ชารลส์ แซนเดอรส์ เพิร์ซ]] (Charles Sanders Peirce),{{sfn|Peirce|1881}}{{sfn|Shields|1997}} 
[[จูเซ็ปเป เปอาโน]] (Giuseppe Peano) และ [[ริชาร์ด เดเดคินด์]] (Richard Dedekind)<ref name="Induction Bussey"/>

==คำบรรยาย==
รูปแบบการอุปนัยเชิงคณิตศาสตร์ที่ง่ายและพบเจอได้มากที่สุดอนุมานว่าข้อความใด ๆ ที่มีเกี่ยวข้องกับ[[จำนวนธรรมชาติ]] <math>n</math> (นั้นคือจำนวนเต็ม <math>n\geq0</math> หรือ 1) เป็นจริงสำหรับค่า <math>n</math> ใด&nbsp;ๆ การพิสูจน์ประกอบด้วยสองขั้นตอนคือ:
# {{anchor|กรณีฐาน}} '''กรณีฐาน''' หรือ '''กรณีต้น''': พิสูจน์ว่าข้อความเป็นจริงสำหรับค่า 0 หรือ 1
# {{anchor|ขั้นตอนการอุปนัย}} '''ขั้นตอนอุปนัย''' หรือ '''กรณีขั้นตอน''': พิสูจน์ว่าสำหรับทุกค่า <math>n</math> หากข้อความเป็นจริงสำหรับ <math>n</math> แล้วข้อความจะเป็นจริงสำหรับ <math>n+1</math> ด้วย หรือพูดอีกแบบคือให้สมมุติว่าข้อความเป็นจริงสำหรับจำนวนธรรมชาติ ''<math>n</math>'' สักตัว แล้วพิสูจน์ว่าข้อความนั้นเป็นจริงสำหรับ <math>n+1</math>  

สมมติฐานในขั้นตอนอุปนัยที่สมมติว่าข้อความเป็นจริงกับค่า ''<math>n</math>'' ค่าหนึ่งเรียกว่า '''สมมติฐานอุปนัย''' ต้องมีการสมุมติสมมติฐานอุปนัยสำหรับค่า <math>n</math> และใช้สมมติฐานนี้เพื่อพิสูจน์ว่าข้อความนั้นเป็นจริงสำหรับ <math>n+1</math> เพื่อพิสูจน์ขั้นตอนอุปนัย

ผู้ที่นิยมนิยามของจำนวนธรรมชาติซึ่งเริ่มจาก 0 จะใช้จำนวนนี้ในกรณีฐาน ผู้ที่นิยมนิยามของจำนวนธรรมชาติซึ่งเริ่มจาก 1 จะใช้จำนวนนี้แทน

==ตัวอย่าง==
===ผลบวกของจำนวนธรรมชาติที่ต่อเนื่องตามลำดับ===
การอุปนัยเชิงคณิตศาสตร์สามารถใช้พิสูจน์ข้อความ <math>P(n)</math> ดังต่อไปนี้สำหรับทุกจำนวนธรรมชาติ ''<math>n</math>'' ได้

:<math>P(n)\!:\ \ 0 + 1 + 2 + \cdots + n \,=\, \frac{n(n + 1)}{2}</math>

นี่เป็นสูตรทั่วไปสำหรับผลบวกของจำนวนธรรมชาติที่น้อยกว่าหรือเท่ากับ ''<math>n</math>'' ซึ่งประกอบไปด้วยข้อความที่มีจำนวนมากเป็นอนันต์: <math>0 = \tfrac{(0)(0+1)}2</math>,  <math>0+1 = \tfrac{(1)(1+1)}2</math>,  <math>0+1+2 = \tfrac{(2)(2+1)}2</math>, ฯลฯ

'''<u>ประพจน์</u>'''  สำหรับ <math>n\in\mathbb{N}</math> ใด ๆ,  <math>0 + 1 + 2 + \cdots + n = \tfrac{n(n + 1)}{2}</math>

'''การพิสูจน์'''  ให้ ''P''(''n'') เป็นข้อความ <math>0 + 1 + 2 + \cdots + n = \tfrac{n(n + 1)}{2}</math> เราจะพิสูจน์โดยการอุปนัยบน ''<math>n</math>''

''<u>กรณีฐาน</u>:'' แสดงให้เห็นว่าข้อความนี้เป็นจริงกับจำนวนธรรมชาติที่น้อยทีสุด ''n'' = 0

''P''(0) เป็นจริงอย่างชัดเจน:  <math>0 = \tfrac{0(0 + 1)}{2} </math>

''<u>ขั้นตอนอุปนัย</u>:'' แสดงให้เห็นว่าสำหรับค่า ''k ≥'' 0 ใด ๆ หาก ''P''(''k'') เป็นจริงแล้ว ''P''(''k''+1) จะเป็นจริงด้วย 

สมมุติสมมติฐานอุปนัยว่าสำหรับค่า ''k'' ค่าหนึ่ง ให้ ''n = k'' เป็นจริง นั่นคือหมายความว่า ''P''(''k'') เป็นจริง:<blockquote><math>0 + 1 + \cdots + k \ =\ \frac{k(k{+}1)}2.</math></blockquote>ดังนั้น:

:<math>(0 + 1 + 2 + \cdots + k )+ (k{+}1) \ =\  \frac{k(k{+}1)}2 + (k{+}1).</math>

ฝั่งขวาสามารถจัดรูปด้วยวิธีการทางพีชคณิตได้เป็น:

:<math>
\begin{align}
\frac{k(k{+}1)}{2} + (k{+}1) & \ =\ \frac {k(k{+}1)+2(k{+}1)} 2 \\
& \ =\ \frac{(k{+}1)(k{+}2)}{2} \\
& \ =\ \frac{(k{+}1)((k{+}1) + 1)}{2}.
\end{align}
</math>

ฝั่งซ้ายมือสุดและฝั่งขวาสุดเท่ากันตรงกลาง เรานิรนัยได้ว่า:<blockquote><math>0 + 1 + 2 + \cdots + k + (k{+}1) \ =\  \frac{(k{+}1)((k{+}1)+1)}2.</math></blockquote>นั่นคือข้อความว่า ''P''(''k+''1) เป็นจริงด้วย เป็นการแสดงขั้นตอนอุปนัย

<u>''ข้อสรุป''</u>: เนื่องจากทั้งกรณีฐานและขั้นตอนอุปนัยถูกพิสูจน์แล้วว่าเป็นจริง ข้อความ ''P''(''n'') จึงเป็นจริงสำหรับทุกจำนวนธรรมชาติ ''n'' ด้วยการอุปนัยเชิงคณิตศาสตร์ [[ซ.ต.พ.|∎]]

===อสมการตรีโกณมิติ===
อสมการมักถูกพิสูจน์ด้วยการอุปนัย เราจะพิสูจน์ว่า <math>|\!\sin nx|\leq n|\!\sin x|</math> สำหรับจำนวนจริง <math>x</math> และจำนวนธรรมชาติ <math>n</math> ใด ๆ  

แวบแรกที่มอง รูปแบบของสมการที่ทั่วไปกว่า <math>|\!\sin nx|\leq n\,|\!\sin x|</math> สำหรับจำนวน''จริง'' <math>n,x</math> ใด ๆ อาจดูเหมือนว่าสามารถพิสูจน์ได้โดยไม่ต้องอุปนัย แต่กรณีที่ <math display="inline">n=\frac{1}{2},\, x=\pi</math> แสดงให้เห็นว่าข้อความนี้สามารถเป็นเท็จได้สำหรับค่า <math>n</math> ที่ไม่ใช่จำนวนเต็ม ทำให้เราต้องพิจารณาข้อความสำหรับจำนวน <math>n</math> ที่เป็นจำนวน''ธรรมชาติ''โดยเฉพาะและการอุปนัยเป็นเครื่องมือที่พร้อมนำมาใช้ที่สุด

'''<u>ประพจน์</u>.'''  สำหรับค่า <math>x\in \mathbb{R},n\in\mathbb{N}</math> ใด ๆ,  <math>|\!\sin nx|\leq n\,|\!\sin x|</math>.  

'''การพิสูจน์'''  กำหนดจำนวนจริง <math>x</math> ค่าใด ๆ ค่าหนึ่ง, และให้ <math>P(n)</math> เป็นข้อความ <math>|\!\sin nx|\leq n\,|\!\sin x|</math>. และเราพิสูจน์โดยการอุปนัยกับ <math>n</math>.  

''<u>กรณีฐาน:</u>'' การคำนวณ <math>|\!\sin 0x| = 0 \leq 0 = 0\,|\!\sin x|</math> พิสูจน์ว่า <math>P(0)</math> เป็นจริง. 

''<u>ขั้นตอนอุปนัย:</u>'' เราจะแสดงว่า <math>P(k)\implies P(k{+}1)</math> สำหรับจำนวนธรรมชาติ <math>k</math> ใด ๆ.  สมมุติสมมติฐานอุปนัยว่าสำหรับค่า <math>n=k\geq 0</math> กรณีของ <math>P(k)</math> จะเป็นจริง เรานิรนัยโดยใช้[[รายการเอกลักษณ์ตรีโกณมิติ|สูตรผลบวกของมุม]]และ[[ค่าสัมบูรณ์|อสมการอิงรูปสามเหลี่ยม]]ได้: 

:<math>\begin{array}{rcll} 
|\sin(k{+}1)x| 
& = & |\sin kx\,\cos x+\sin x\,\cos kx\,| & \text{(ผลบวกของมุม)}
\\ 
& \leq & |\!\sin kx\,\cos x| + |\!\sin x\,\cos kx| & \text{(อสมการอิงรูปสามเหลี่ยม)}
\\ 
& = & |\!\sin kx|\,|\!\cos x|+|\!\sin x|\,|\!\cos kx|& 
\\ 
& \leq & |\!\sin kx| + |\!\sin x| & (\,|\!\cos t|\leq 1)
\\ 
& \leq &
k\,|\!\sin x|+|\!\sin x| & \text{(สมมติฐานอุปนัย})\\ 
& \ =\ & (k{+}1)\,|\!\sin x|. & 
\end{array}</math>

อสมการระหว่างฝั่งซ้ายและฝั่งขวาแสดงให้เห็นว่า <math>P(k{+}1)</math> เป็นจริง ขั้นตอนอุปนัยจึงเสร็จสมบูรณ์

<u>''ข้อสรุป''</u>: ประพจน์ <math>P(n)</math> เป็นจริงสำหรับเลขจำนวนธรรมชาติ <math>n</math> ทุกค่า ∎

==รูปแบบอื่น==
ในทางปฏิบัติ การพิสูจน์โดยการอุปนัยมักมีแบบแผนที่ต่างกันซึ่งขึ้นอยู่กับลักษณะของคุณสมบัติที่เราต้องการจะพิสูจน์ รูปแบบอื่น ๆ ของการอุปนัยทุกรูปแบบเป็นกรณีพิเศษของการอุปนัยเชิงอนันต์ ดู[[#การอุปนัยเชิงอนันต์|ด้านล่าง]]

===ฐานของการอุปนัยนอกเหนือจาก 0 หรือ 1===
หากเราไม่ประสงค์จะพิสูจน์ข้อความหนึ่งสำหรับจำนวนธรรมชาติทุกจำนวน แต่ต้องการพิสูจน์เพียงสำหรับจำนวน ''n'' ทุกจำนวนที่มีค่ามากกว่าหรือเท่ากับค่า ''b'' เท่านั้นแล้ว การพิสูจน์ด้วยการอุปนัยจะประกอบด้วย:
# การแสดงให้เห็นว่าข้อความเป็นจริงเมื่อ <math>n=b</math>
# การแสดงให้เห็นว่าหากข้อความเป็นจริงสำหรับค่า <math display="inline">n \geq b</math> ค่าหนึ่งแล้ว ข้อความเดียวกันนี้ก็จะเป็นจริงสำหรับค่า <math>n+1</math> ด้วย
เราสามารถนำวิธีนี้มาใช้เพื่อแสดงให้เห็นว่า <math display="inline">2^n \geq n + 5</math> สำหรับ <math>n \geq 3</math>

เราสามารถพิสูจน์ได้ว่าข้อความ <math>P(n)</math> ข้อความหนึ่งเป็นจริงสำหรับค่า <math>n \geq 1</math> หรือแม้แต่สำหรับค่า <math>n \geq -5</math> การอุปนัยเชิงคณิตศาสตร์รูปแบบนี้ความจริงแล้วเป็นกรณีพิเศษของรูปแบบก่อนหน้าเพราะหากข้อความที่ถูกพิสูจน์คือ <math>P(n)</math> แล้ว การพิสูจน์ด้วยกฎสองข้อนี้ก็เท่ากับการพิสูจน์ข้อความ <math>P(n+b)</math> สำหรับจำนวนธรรมชาติ <math>n</math> ทุกจำนวนโดยมีกรณีฐานอุปนัยกับค่า <math>0</math><ref>Ted Sundstrom, ''Mathematical Reasoning'', p. 190, Pearson, 2006, {{isbn|978-0131877184}}</ref>

==== {{anchor|จำนวนเงินบาท}}ตัวอย่าง: การใช้เหรียญบาทต่าง ๆ เพื่อให้รวมได้จำนวนเงินจำนวนหนึ่ง ====
สมมติว่าเรามีเหรียญสี่บาทและเหรียญห้าบาทจำนวนไม่จำกัด เราสามารถใช้การอุปนัยเพื่อพิสูจน์ได้ว่าจำนวนเต็มของเงินบาทใด ๆ ที่มากกว่าหรือเท่ากับ <math>12</math> สามารถใช้เหรียญสี่บาทและห้าบาทมารวมกันได้จำนวนนั้น ให้ <math>S(k)</math> เป็นข้อความว่า "''จำนวนเงิน <math>k</math> บาทสามารถรวมมาจากเหรียญสี่บาทและเหรียญห้าบาท''" การพิสูจน์ว่า <math>S(k)</math> เป็นจริงสำหรับค่า <math>k \geq 12</math> ทุกค่าสามารถทำได้ด้วยการอุปนัยกับ <math>k</math> ดังนี้:

''กรณีฐาน'': การแสดงให้เห็นว่า <math>S(k)</math> เป็นจริงสำหรับ <math>k=12</math> ง่ายมาก เพียงแค่มีเหรียญสี่บาทสามเหรียญ 

''ขั้นตอนอุปนัย'': กำหนดให้ <math>S(k)</math> เป็นจริงสำหรับค่า <math>k \geq 12</math> ค่าหนึ่ง (''สมมติฐานอุปนัย'') พิสูจน์ว่า <math>S(k+1)</math> เป็นจริงด้วย: 
:สมมติให้ <math>S(k)</math> เป็นจริงสำหรับค่า <math>k\geq 12</math> ใด ๆ หากมีคำตอบสำหรับจำนวน <math>k</math> บาทที่มีเหรียญสี่บาทอยู่อย่างน้อยหนึ่งเหรียญ เพียงแค่เปลี่ยนเหรียญสี่บาทเป็นเหรียญห้าบาทหนึ่งเหรียญก็จะได้จำนวนเงิน <math>k+1</math> บาท หรือหากในคำตอบมีแต่เหรียญห้าบาท แล้ว <math>k</math> จำต้องเป็นพหุคูณของ 5 เพราะฉะนั้นต้องมีค่าเท่ากับ 15 เป็นอย่างน้อย เราจึงสามารถแทนเหรียญห้าบาทสามเหรียญเป็นเหรียญสี่บาทสี่เหรียญเพื่อให้ได้จำนวนเงิน <math>k+1</math> บาท ในกรณีแต่ละกรณีข้อความ <math>S(k+1)</math> เป็นจริง

เพราะฉะนั้น <math>S(k)</math> เป็นจริงสำหรับค่า <math>k\geq 12</math> ทุกค่าด้วยหลักการอุปนัย และการพิสูจน์จึงสมบูรณ์

แม้ <math>S(k)</math> จะเป็นจริงสำหรับค่า <math>k \in \{ 4, 5, 8, 9, 10 \}</math> ในตัวอย่างนี้ด้วย เราไม่สามารถดัดแปลงค่าต่ำสุด <math>12</math> ให้น้อยไปกว่านี้ได้อีกเป็นค่า <math>m</math> ในการพิสูจน์ข้างบน 
สำหรับ <math>m=11</math> กรณีฐานเป็นเท็จ 
สำหรับ <math>m=10</math> กรณีที่สองในขั้นตอนอุปนัยจะใช้ไม่ได้ (การแทนเหรียญห้าบาทเป็นเหรียญสี่บาททำไม่ได้) 
ส่วนสำหรับค่า <math>m</math> ที่น้อยกว่านี้ก็ไม่จำเป็นต้องเอ่ยถึงเลย

===การอนุมานกับตัวนับมากกว่าหนึ่งตัว===
บางครั้งการใช้จำนวนธรรมชาติสองจำนวน ''n'' กับ ''m'' เพื่อพิสูจน์ข้อความข้อหนึ่งด้วยการทำกระบวนการอุปนัยซ้ำนั้นดีกว่า นั่นคือการพิสูจน์กรณีฐานและขั้นตอนอุปนัยบนตัวแปร ''n'' และในแต่ละขั้นตอนอุปนัยก็พิสูจน์อุปนัยบนตัวแปร ''m'' ด้วย ดูตัวอย่างได้ใน[[การพิสูจน์ที่เกี่ยวข้องกับการบวกจำนวนธรรมชาติ|
การพิสูจน์สมบัติการสลับที่]] (Proofs involving the addition of natural numbers) ซึ่งเป็นส่วนหนึ่งของ''[[การบวก]]จำนวนธรรมชาติ'' การอ้างเหตุผลที่ซับซ้อนกว่านี้อาจมีตัวนับได้ถึงสามตัวหรือมากกว่า

===การลดหลั่นอนันต์===
{{Main|การลดหลั่นอนันต์}}

วิธีการการลดหลั่นอนันต์ ({{langx|en|Infinite descent}}) เป็นรูปแบบหนึ่งของการอุปนัยเชิงคณิตศาสตร์ที่ [[ปีแยร์ เดอ แฟร์มา]] ใช้เพื่อแสดงให้เห็นว่าข้อความ ''Q''(''n'') ข้อหนึ่งเป็นเท็จสำหรับจำนวนธรรมชาติ ''n'' ทุกจำนวน รูปแบบดั้งเดิมประกอบไปด้วยการแสดงว่าถ้า ''Q''(''n'') เป็นจริงสำหรับจำนวนธรรมชาติ ''n'' ค่าหนึ่งก็จะเป็นจริงสำหรับค่า ''m'' ที่น้อยกว่า ''n'' โดยแท้ แต่เพราะลำดับของจำนวนธรรมชาติที่มีค่าลดหลั่นลงอย่างไม่สิ้นสุดไม่มีอยู่จริงจึงทำให้สถานการณ์นี้เป็นไปไม่ได้ และดังนั้นจึงเป็นการแสดง (โดยข้อขัดแย้ง) ว่า ''Q''(''n'') ไม่สามารถเป็นจริงได้สำหรับค่า ''n'' ใด ๆ

เราสามารถพิสูจน์ยืนยันความสมเหตุสมผลของวิธีการนี้ได้จากหลักปกติของการอุปนัยเชิงคณิตศาสตร์ ด้วยการใช้การอุปนัยเชิงคณิตศาสตร์กับข้อความ ''P''(''n'') ซึ่งถูกนิยามไว้ว่า "''Q''(''m'') เป็นเท็จสำหรับจำนวนธรรมชาติ ''m'' ทุกค่าที่น้อยกว่าหรือเท่ากับ ''n''" จึงแสดงว่า ''P''(''n'') เป็นจริงสำหรับ ''n'' ทุกค่า ซึ่งแปลว่า ''Q''(''n'') เป็นเท็จสำหรับจำนวนธรรมชาติ ''n'' ทุกจำนวน

===การอุปนัยตัวเติมหน้า===
รูปแบบของการพิสูจน์โดยการอุปนัยเชิงคณิตศาสตร์ที่พบได้ทั่วไปที่สุดมีความจำเป็นให้พิสูจน์ในขั้นตอนอุปนัยว่า

:<math>\forall k (P(k) \to P(k+1))</math>

ซึ่งต่อจากนั้นหลักการอุปนัยจะ "ทำโดยอัตโนมัติ" (automate) การใช้ขั้นตอนนี้จำนวน ''n'' ครั้งเพื่อไปจาก ''P''(0) สู่ ''P''(''n'') นี่เรียกได้ว่าเป็น "การอุปนัยตัวนำหน้า" เพราะในแต่ละขั้นตอนก็เป็นการพิสูจน์บางสิ่งเกี่ยวกับเลขตัวหนึ่งจากบางสิ่งที่เกี่ยวกับเลขที่นำหน้าเลขตัวนั้น

สิ่งหนึ่งซึ่งได้รับความสนใจในเรื่อง[[ทฤษฎีความซับซ้อนในการคำนวณ|ความซับซ้อนในการคำนวณ]]คือ "การอุปนัยตัวเติมหน้า" ({{langx|en|prefix induction}}) ซึ่งเป็นการพิสูจน์ข้อความดังต่อไปนี้ในขั้นตอนอุปนัย 

:<math>\forall k (P(k) \to P(2k) \land P(2k+1))</math>

หรือซึ่งสมมูลกัน

:<math>\forall k \left( P \left(\left\lfloor \frac{k}{2} \right\rfloor \right) \to P(k) \right)</math>

แล้วหลักการอุปนัยจึง "ทำโดยอัตโนมัติ" การใช้การอนุมานนี้จำนวน log ''n'' ครั้งเพื่อไปจาก ''P''(0) สู่ ''P''(''n'') ที่เรียกว่า "การอุปนัยตัวเติมหน้า" เพราะแต่ละขั้นตอนเป็นการพิสจน์บางสิ่งเกี่ยวกับเลขตัวหนึ่งจากบางสิ่งที่เกี่ยวกับ "ตัวเติมหน้า" (prefix) ของเลขตัวนั้นซึ่งถูกสร้างขึ้นจากการตัดปลายบิต (bit) ส่วนต่ำของการแทนเลขแบบฐานสอง และยังสามารถมองเป็นการประยุกต์การอุปนัยแบบดั้งเดิมกับความยาวของการแทนแบบฐานสอง

หากการอุปนัยตัวนำหน้าถูกตีความทางคำนวณว่าเป็นวงวน (loop) ''n'' ขั้นตอนแล้ว การอุปนัยตัวเติมหน้าก็จะสมนัยกับวงวน log ''n'' ขั้นตอน เพราะฉะนั้นการพิสูจน์โดยใช้การอุปนัยตัวเติมหน้าจึง "สรรค์สร้างอย่างเป็นไปได้" (feasibly constructive) มากกว่าการพิสูจน์ซึ่งใช้การอุปนัยตัวนำหน้า

การอุปนัยตัวนำหน้าสามารถจำลองการอุปนัยตัวเติมหน้ากับข้อความเดียวกันได้อย่างชัด การอุปนัยตัวเติมหน้าสามารถจำลองการอุปนัยตัวนำหน้าได้แต่ต้องแลกมาด้วยการทำให้วากยสัมพันธ์ของข้อความซับซ้อนขึ้น (เพิ่ม[[ตัวบ่งปริมาณ (ทั้งหมด)|ตัวบ่งปริมาณทั้งหมด]]ซึ่งมีขอบเขต) ผลลัพธ์ซึ่งแสดงความสัมพันธ์ของการอุปนัยตัวเติมหน้ากับการคำนวณซึ่งใช้เวลาพหูพจน์ (polynomial time) จึงขึ้นอยู่กับการเอาตัวบ่งปริมาณซึ่งไม่มีขอบเขตออกไปทั้งหมดและการจำกัดจำนวนการสับเปลี่ยนระหว่างตัวบ่งปริมาณทั้งหมดซึ่งมีขอบเขตกับ[[ตัวบ่งปริมาณ (บางตัว)|ตัวบ่งปริมาณบางตัว]]ที่อนุญาตให้ทำในข้อความ<ref name=Buss:BA>{{cite book|last=Buss|first=Samuel|title=Bounded Arithmetic|date=1986|publisher=Bibliopolis|location=Naples}}</ref>

=== {{anchor|การอุปนัยอย่างเข้ม}} การอุปนัยอย่างเข้ม===
รูปแบบอื่นอีกรูปหนึ่งเรียกว่า '''การอุปนัยอย่างเข้ม''' ({{langx|en|Complete induction หรือ Strong induction}}) (ในทางตรงกันข้าม รูปแบบของการอุปนัยที่ได้กล่าวไปก่อนหน้านี้บางครั้งเรียกว่า '''การอุปนัยอย่างอ่อน''' (weak induction)) ทำให้ขั้นตอนอุปนัยพิสูจน์ได้ง่ายขึ้นด้วยการใช้สมมติฐานที่แรงขึ้น: เราพิสูจน์ข้อความ {{nowrap|''P''(''m'' + 1)}} ภายใต้สมมติฐานว่า ''P''(''n'') เป็นจริงสำหรับจำนวนธรรมชาติ ''n'' ทุกจำนวนซึ่งน้อยกว่า {{nowrap|''m'' + 1}} ในขณะที่รูปแบบพื้นฐานของการอุปนัยสมมุติเพียงแค่ว่า ''P''(''m'') เป็นจริง ชื่อ "การอุปนัยอย่างเข้ม" ไม่หมายความว่าวิธีนี้สามารถพิสูจน์ทฤษฎีบทได้เยอะกว่า "การอุปนัยแบบอ่อน" แต่หมายถึงเพียงสมมติฐานที่ถูกใช้ในขั้นตอนอุปนัยที่แรงขึ้น

ความจริงแล้วเราสามารถแสดงให้เห็นว่าทั้งสองวิธีนั้นสมมูลกันตามที่อธิบายไว้ด้านล่าง ในการอุปนัยอย่างเข้มยังต้องพิสูจน์กรณีฐาน ''P''(0) และอาจจำเป็นต้องพิสูจน์กรณีฐานเพิ่มเติมด้วยเช่น ''P''(1) ก่อนที่การอ้างเหตุผลจะใช้ได้ อย่างเช่นในตัวอย่างของ[[จำนวนฟีโบนัชชี]] ''F<sub>n</sub>'' ด้านล่าง

แม้การอุปนัยอย่างเข้มต้องพิสูจน์กรณีฐาน เราไม่จำเป็นต้องพิสูจน์หากสามารถพิสูจน์ ''P''(''m'') (โดยสมมติ ''P''(''n'') สำหรับค่า ''n'' ที่น้อยกว่าทุกค่า) ได้สำหรับค่า {{nowrap|''m'' ≥ 0}} ทุกตัว นี่เป็นกรณีพิเศษของ[[#การอุปนัยเชิงอนันต์|การอุปนัยเชิงอนันต์]]อย่างที่อธิบายไว้ด้านล่าง ในรูปแบบนี้กรณีฐานถูกรวมอยู่ในกรณี {{Nowrap|1=''m'' = 0}} ซึ่ง  ''P''(0) ถูกพิสูจน์โดยไม่มีการสมมติ ''P''(''n'') อื่น เราอาจต้องจัดการกับกรณีนี้แยกไปแต่บางครั้งการอ้างเหตุผลเดียวกันใช้ได้กับ ''m''&nbsp;=&nbsp;0 และ {{nowrap|''m'' > 0}} ซึ่งทำให้การพิสูจน์เรียบง่ายและสวยงามกว่า อย่างไรก็ตามสิ่งที่สำคัญคือต้องมั่นใจว่าการพิสูจน์ ''P''(''m'') ไม่ได้สมมติโดยนัยว่า {{nowrap|''m'' > 0}} เช่นด้วยการบอกว่า "เลือกจำนวน {{nowrap|''n'' < ''m''}} ค่าหนึ่ง" หรือด้วยการสมมติว่าเซตซึ่งมีสมาชิกจำนวน ''m'' มีสมาชิกอย่างน้อยหนึ่งตัว

การอุปนัยอย่างเข้มสมมูลกับการอุปนัยเชิงคณิตศาสตร์แบบธรรมดาอย่างที่อธิบายไว้ด้านบนในแง่ที่สามารถแปลงการพิสูจน์ด้วยวิธีการหนึ่งไปเป็นการพิสูจน์ด้วยอีกวิธีได้ สมมุติว่ามีการพิสูจน์ ''P''(''n'') ด้วยการอุปนัยอย่างเข้ม ให้ Q(''n'') หมายถึง "''P''(''m'') เป็นจริงสำหรับค่า ''m'' ใด ๆ โดยที่ {{nowrap|0 ≤ ''m'' ≤ ''n''}}" แล้ว Q(''n'') จะเป็นจริงสำหรับ ''n'' ทุกค่า[[ก็ต่อเมื่อ]] P(''n'') เป็นจริงสำหรับ ''n'' ทุกค่า และการพิสูจน์ ''P''(''n'') ของเราก็ถูกแปลงเป็นการพิสูจน์ Q(''n'') ได้อย่างง่ายดายด้วยการอุปนัย (แบบธรรมดา) ในทางกลับกันหาก ''P''(''n'') ได้ถูกพิสูจน์โดยการอุปนัยธรรมดาแล้ว การพิสูจน์นั้นกลายเป็นอันที่ทำด้วยการอุปนัยแบบเข้มแล้วโดยประสิทธิผล: ''P''(0) ถูกพิสูจน์ในกรณีฐานโดยไม่ใช้สมมติฐานและ {{nowrap|''P''(''n'' + 1)}} ถูกพิสูจน์ในขั้นตอนอุปนัยแล้วซึ่งอาจมีการสมมุติกรณีก่อนหน้านี้ทั้งหมดแต่ต้องใช้เพียงกรณี ''P''(''n'') เท่านั้น

====ตัวอย่าง: จำนวนฟีโบนัชชี====
การอุปนัยอย่างเข้มมีประโยชน์เมื่อต้องใช้สมมติฐานอุปนัยหลาย ๆ รอบต่อขั้นตอนอุปนัยขั้นตอนหนึ่ง เช่นเราสามารถการอุปนัยอย่างเข้มเพื่อแสดงให้เห็นว่า
:<math> F_n = \frac{\varphi^n - \psi^n}{\varphi - \psi}</math> สำหรับทุก ''n''

เมื่อ <math>F_n</math> เป็น[[จำนวนฟีโบนัชชี]]ลำดับที่ ''n'', <math display="inline">\varphi = {{1 + \sqrt 5} \over 2}</math> ([[อัตราส่วนทอง]]) และ <math display="inline">\psi = {{1 - \sqrt 5} \over 2}</math> เป็นรากทั้งสองของพหุนาม <math>x^2-x-1</math> เราสามารถพิสูจน์เอกลักษณ์ข้างต้นด้วยการคำนวณ <math display="inline">F_{n+2}</math> ตรง ๆ หากเราสมมุติว่าเอกลักษณ์ดังกล่าวเป็นจริงสำหรับ <math display="inline">F_{n+1}</math> และ <math display="inline">F_n</math> และใช้ข้อเท็จจริงว่า <math>F_{n+2} = F_{n+1} + F_{n}</math> สำหรับทุก <math>n \in \Bbb{N}</math> 

เพื่อให้การพิสูจน์โดยการอุปนัยอย่างเข้มเสร็จสมบูรณ์ เราจะต้องพิสูจน์เอกลักษณ์ในกรณีฐานสองกรณี ได้แก่ <math>n=0</math> และ <math display="inline">n=1</math> 

====ตัวอย่าง: การแยกตัวประกอบเฉพาะ====
การพิสูจน์ด้วยการอุปนัยอย่างเข้มอีกอันหนึ่งใช้สมมติฐานว่าข้อความเป็นจริงสำหรับจำนวน <math>n</math> ''ทุกค่าที่น้อยกว่า'' พิจารณาข้อความที่ว่า "[[จำนวนธรรมชาติ]]ทุกจำนวนซึ่งมากกว่า 1 เป็นผลคูณของ[[จำนวนเฉพาะ]]หนึ่งจำนวนหรือมากกว่า" ซึ่งเป็นส่วน "การมีอย฿าจริง" (existence) ของ[[ทฤษฎีบทมูลฐานของเลขคณิต]] ในการพิสูจน์ขั้นตอนอุปนัย สมมติฐานอุปนัยคือ "สำหรับค่า <math>m>1</math> ที่กำหนดมาให้ เราสมมติว่าข้อความเป็นจริงทุกจำนวนนับ <math>n>1</math> ซึ่งน้อยกว่า <math>m</math>" หาก <math>m</math> เป็นจำนวนเฉพาะแล้วมันเป็นผลคูณของจำนวนเฉพาะหนึ่งตัวอย่างแน่นอน และหากไม่ใช่แล้ว <math>m</math> จะเท่ากับผลคูณ <math>m=n_1 n_2</math> ตามนิยามของจำนวนประกอบ โดยตัวประกอบทั้งสองไม่เท่ากับ 1 ดังนั้นทั้ง <math>n_1, n_2 </math> จึงไม่เท่ากับ <math>m</math> เพราะฉะนั้นทั้งสองจึงมากกว่าหนึ่งและน้อยกว่า <math>m</math> เราสามารถใช้สมมติฐานอุปนัยกับ <math>n_1</math> และ <math>n_2</math> ดังนั้นทั้งสองแต่ละตัวเป็นผลคูณของจำนวนเฉพาะ ฉะนั้น <math>m</math> เป็นผลคูณของผลคูณของจำนวนเฉพาะและจึงเป็นผลคูณของจำนวนเฉพาะเอง

==== ตัวอย่าง: กลับมาหาจำนวนเงินบาท ====
เราจะดูการพิสูจน์ตัวอย่างเดียวกับ[[#จำนวนเงินบาท|ด้านบน]] ครั้งนี้ด้วย ''การอุปนัยอย่างเข้ม'' แต่ข้อความยังคงเดิม:

<math>S(n): \,\,n\geq12 \to \,\exists\, a,b\in\mathbb{N}. \,\, n=4a+5b</math>

แต่ทว่าโครงสร้างและสมมติฐานของการพิสูจน์จะมีความแตกต่างเล็กน้อย เริ่มจากกรณีฐานที่ขยายจำนวนกรณี:

'''กรณีฐาน''': แสดงให้เห็นว่า <math>S(k)</math> เป็นจริงสำหรับค่า <math>k=12,13,14,15</math>

: <math>\begin{align}
4 \cdot 3+5 \cdot 0=12\\
4 \cdot 2+5 \cdot 1=13\\
4 \cdot 1+5 \cdot 2=14\\
4 \cdot 0+5 \cdot 3=15
\end{align}</math>

ฉะนั้นกรณีฐานเป็นจริง

'''สมมติฐานอุปนัย''': กำหนดจำนวน <math>j>15</math> ค่าหนึ่ง สมมติว่า <math>S(m)</math> เป็นจริงสำหรับค่า <math>m</math> ทุกค่าที่ <math>12\leq m< j</math>.

'''ขั้นตอนอุปนัย''': จะพิสูจน์ว่า <math>S(j)</math> เป็นจริง

เลือกค่า <math>m=j-4</math> และสังเกตว่า <math>15< j \to 12\leq j-4<j</math> แสดงให้เห็นว่า <math>S(j-4)</math> เป็นจริงโดยสมมติฐานอุปนัย นั่นคือผลบวก <math>j-4</math> สามารถถูกสร้างขึ้นมาด้วยส่วนผสมของเหรียญ <math>4</math> และ <math>5</math> บาท แล้วดังนั้นเพียงแค่เพิ่มเหรียญ <math>4</math>บาทลงไปในกองเหรียญนั้น แล้วจะให้ผลบวกค่าเหรียญทั้งหมดเท่ากับ <math>j</math> นั่นคือ <math>S(j)</math> เป็นจริง [[ซ.ต.พ.|∎]]

===การอุปนัยเดินหน้า-ถอยหลัง===
บางครั้งการพิสูจน์ถอยหลัง หรือการพิสูจน์ข้อความในกรณี <math>n-1</math> เมื่อทราบว่าข้อความเป็นจริงในกรณี <math>n</math> จะสะดวกกว่า อย่างไรก็ตามไม่มีเลขตัวใดเพียงตัวเดียวที่เหมาะสมจะเป็นกรณีฐานของการอุปนัยได้ เราต้องพิสูจน์ข้อความสำหรับเซตย่อยอนันต์ของจำนวนธรรมชาติบางตัวแทน เช่น [[โอกุสแต็ง-หลุยส์ โกชี]]ใช้การอุปนัยเดินหน้า (หรือการอุปนัยปรกติ) เพื่อพิสูจน์[[อสมการมัชฌิมเลขคณิต-เรขาคณิต]] (inequality of arithmetic and geometric means) ในกรณีจำนวนตัวแปรเท่ากับกำลังของ 2 ทุกค่า แล้วใช้การอุปนัยถอยหลังเพื่อแสดงให้เห็นว่าเป็นจริงสำหรับจำนวนธรรมชาติทุกจำนวนด้วย <ref>{{Cite web|url=https://brilliant.org/wiki/forward-backwards-induction/|title=Forward-Backward Induction {{!}} Brilliant Math & Science Wiki|website=brilliant.org|language=en-us|access-date=2019-10-23}}</ref><ref>Cauchy, Augustin-Louis (1821). [http://visualiseur.bnf.fr/Visualiseur?Destination=Gallica&O=NUMM-29058 ''Cours d'analyse de l'École Royale Polytechnique, première partie, Analyse algébrique,''] {{Webarchive|url=https://web.archive.org/web/20171014135801/http://visualiseur.bnf.fr/Visualiseur?Destination=Gallica&O=NUMM-29058 |date=14 October 2017 }} Paris. สามารถพบการพิสูจน์อสมการมัชฌิมเลขคณิต-เรขาคณิตได้ที่หน้า 457ff.</ref>

==ตัวอย่างของความผิดพลาดในขั้นตอนอุปนัย==
{{Main|ม้าทุกตัวมีสีเดียวกัน}}

ขั้นตอนอุปนัยจะต้องถูกพิสูจน์สำหรับ ''n'' ทุกค่า เพื่อแสดงสิ่งนี้ให้เห็น โจเอล อี. โคเฮน ได้นำเสนอการอ้างเหตุผลว่าสามารถพิสูจน์ว่า[[ม้าทุกตัวมีสีเดียวกัน]] (All horses are the same color) ได้ด้วยการอุปนัยเชิงคณิตศาสตร์ ดังต่อไปนี้:<ref>{{citation|title=On the nature of mathematical proof|first=Joel E.|last=Cohen|year=1961|journal=Opus}}. Reprinted in ''A Random Walk in Science'' (R. L. Weber, ed.), Crane, Russak & Co., 1973.</ref>
*กรณีฐาน: ในเซตของม้าแค่หนึ่งตัว จะมีสีแค่หนึ่งสี
*ขั้นตอนอุปนัย: สมมติว่าในเซตของม้า <math>n</math> ตัวเซตใด ๆ ก็จะมีสีเพียงหนึ่งสีเป็นสมมติฐานอุปนัย คราวนี้ดูที่เซตของม้า <math>n+1</math> ตัว ใส่ลำดับเลขแต่ละตัวเป็น: <math>1,\; 2,\; 3,\; \dotsc,\; n,\; n+1</math> พิจารณาเซต <math display="inline">\left\{1,\; 2,\; 3,\; \dotsc,\; n\right\}</math> และ <math display="inline">\left\{2,\;3,\;4,\;\dotsc,\;n+1\right\}</math> แต่ละเซตเป็นเซตของม้า  <math>n</math> ตัวเพราะฉะนั้นจึงมีสีเพียงสีเดียวในแต่ละเซตและทั้งสองเซตเหลื่อมกัน ม้า <math>n+1</math> ตัวทุกตัวจึงจะต้องมีสีเพียงสีเดียวเท่านั้น

กรณีฐาน <math>n=1</math> เป็นเรื่องธรรมดา (เพราะไม่ว่าม้าตัวไหนก็จะมีสีเดียวกับตัวมันเอง) และขั้นตอนอุปนัยถูกต้องในกรณีที่  <math>n > 1</math> ทุกกรณี แต่ทว่าตรรกะของขั้นตอนอุปนัยสำหรับค่า <math>n=1</math> ไม่ถูกต้องเพราะข้อความที่ว่า "ทั้งสองเซตเหลื่อมกัน" เป็นเท็จ (มีม้าเพียง <math>n+1=2</math> ตัวทั้งก่อนและหลังการเอาม้าตัวหนึ่งออกจากเซต เซตของม้าตัวเดียวจึงไม่เหลื่อมกัน)

==การกำหนดรูปนัย {{anchor|สัจพจน์ของการอุปนัย}} ==

เราสามารถเขียน "[[สัจพจน์]]ของการอุปนัย" ใน'''[[ตรรกศาสตร์อันดับสอง|ตรรกะอันดับสอง]]''' (second-order logic) ได้ดังนี้:
: <math>\displaystyle\forall P\Bigl( P(0) \land \forall k \bigl( P(k) \to P(k+1)\bigr ) \to \forall n \bigl(P(n)\bigr)\Bigr)</math>,
ซึ่ง ''P''(.) เป็นตัวแปรของภาคแสดงซึ่งมีจำนวนธรรมชาติหนึ่งตัวเป็นตัวแปรและ ''k'' กับ ''n'' เป็นตัวแปรของ[[จำนวนธรรมชาติ]] 

อธิบายได้ว่า กรณีฐาน ''P''(0) และขั้นตอนอุปนัย (กล่าวคือ สมมติฐานอุปนัย ''P''(''k'') นำไปสู่ ''P''(''k''&nbsp;+&nbsp;1)) ทั้งสองข้อร่วมกันนำไปสู่ข้อความว่า ''P''(''n'') เป็นจริงสำหรับจำนวนธรรมชาติ ''n'' ใด ๆ สัจพจน์ของการอุปนัยยืนยันความสมเหตุสมผลของการอนุมานว่า ''P''(''n'') เป็นจริงสำหรับจำนวนธรรมชาติ ''n'' ใด ๆ จากกรณีฐานและขั้นตอนอุปนัย

ตัวบ่งปริมาณตัวแรกในสัจพจน์ครอบคลุมถึง''ภาคแสดง''แทนที่จะเป็นตัวเลขแต่ละตัว นี่เป็นตัวบ่งปริมาณอันดับสองซึ่งแปลว่าสัจพจน์นี้ถูกกล่าวใน[[ตรรกศาสตร์อันดับสอง|ตรรกะอันดับสอง]] การกำหนดสัจพจน์การอุปนัยเลขคณิตใน[[ตรรกศาสตร์อันดับหนึ่ง|ตรรกะอันดับหนึ่ง]] (first-order logic) จำเป็นต้องใช้[[เค้าร่างสัจพจน์]] (axiom schema) ซึ่งประกอบไปด้วยสัจพจน์หนึ่งอันสำหรับภาคแสดงที่เป็นไปได้แต่ละภาคแสดง บทความ[[สัจพจน์เปอาโน]] (Peano axioms) พูดถึงประเด็นนี้เพิ่มเติม

สัจพจน์ของการอุปนัยเชิงโครงสร้างสำหรับจำนวนธรรมชาติถูกกำหนดเป็นครั้งแรกโดย[[Giuseppe Peano|เปอาโน]] เขาใช้มันเพื่อระบุว่าระบบจำนวนธรรมชาติจะสอดคล้องกับสัพจน์ของการอุปนัยและสัจพจน์อื่นอีกสี่ข้อดังต่อไปนี้:

# 0 เป็นจำนวนธรรมชาติ
# ฟังก์ชันตัวตามหลัง ''s'' ของจำนวนธรรมชาติใด ๆ ให้ผลออกมาเป็นจำนวนธรรมชาติ (''s''(''x'')=''x''+1).
# ฟังก์ชันตัวตามหลังเป็นหนึ่งต่อหนึ่ง 
# 0 ไม่ได้อยู่ใน[[พิสัยของฟังก์ชัน|พิสัย]]ของ ''s''

การบ่งปริมาณกับภาคแสดงทำไม่ได้ใน'''[[ทฤษฎีเซตแซร์เมโล-เฟรนเคิล]][[ตรรกศาสตร์อันดับหนึ่ง|อันดับหนึ่ง]]''' (Zermelo-Fraenkel set theory, '''ZF''') แต่เราสามารถแสดงการอุปนัยด้วยการบ่งปริมาณกับเซต:
: <math>\forall A \Bigl( 0 \in A \land \forall k \in \mathbb{N} \bigl( k \in A \to (k+1) \in A \bigr) \to \mathbb{N}\subseteq A\Bigr)</math>
เราสามารถอ่าน <math>A</math> เป็นเซตซึ่งแทนประพจน์และมีจำนวนธรรมชาติสำหรับที่ประพจน์เป็นจริง นี่ไม่ใช่สัจพจน์แต่เป็นทฤษฎีบทใน '''ZF''' หากนิยามจำนวนธรรมชาติในภาษาของทฤษฎีเซต '''ZF''' ด้วยสัจพจน์ที่คล้ายกับของเปอาโน

==การอุปนัยเชิงอนันต์==
{{Main|การอุปนัยเชิงอนันต์}}
เราสามารถนำหลักการอุปนัยอย่างเข้มมาใช้กับข้อความเกี่ยวกับสมาชิกของ[[สัจพจน์ของความปรกติ|เซตรากฐานดี]] (well-founded set) เซตใด ๆ ที่นอกเหนือไปจากเซตขอจำนวนธรรมชาติเท่านั้น นั่นคือเซตซึ่งมี[[ความสัมพันธ์สะท้อน|ความสัมพันธ์ไม่สะท้อน]] (irreflexive relation) ซึ่งไม่มี[[อันดับทุกส่วน|โซ่ลดหลั่นอนันต์]] (infinite descending chain) เซตของ[[จำนวนเชิงการนับ]]เซตใด ๆ เป็นเซตรากฐานดีซึ่งรวมไปถึงเซตของจำนวนธรรมชาติ
เมื่อนำไปประยุกต์กับเซตรากฐานดีก็สามารถกำหนดรูปใหม่เป็นขั้นตอนเดียวได้ว่า:
#แสดงให้เห็นว่าหากข้อความข้อหนึ่งเป็นจริงสำหรับค่า {{nowrap|''m'' < ''n''}} ค่าใด ๆ แล้วข้อความเดียวกันนั้นก็จะเป็นจริงสำหรับ ''n'' ด้วย

เมื่อนำการอุปนัยรูปนี้ไปประยุกต์ใช้กับเซตของ[[จำนวนเชิงอันดับที่]]แล้ว (ซึ่งทำให้เกิดคลาส[[อันดับดี]] (well-order) และจึงเป็นคลาสรากฐานดี) ก็จะเรียกว่า''[[การอุปนัยเชิงอนันต์]]'' นี่เป็นเทคนิคการพิสูจน์ที่สำคัญใน[[ทฤษฎีเซต]] [[ทอพอโลยี]]และสาขาวิชาอื่น ๆ

การพิสูจน์โดยการอุปนัยเชิงอนันต์โดยปกติแล้วจะจำแนกกรณีเป็นสามกรณี:
# เมื่อ ''n'' เป็นสมาชิกเล็กสุด หรือก็คือไม่มีสมาชิกซึ่งเล็กไปกว่า ''n'' อีก
# เมื่อ ''n'' มีตัวนำหน้าโดยตรง หรือก็คือเซตของสมาชิกซึ่งเล็กกว่า ''n'' มีสมาชิกใหญ่สุด
# เมื่อ ''n'' ไม่มีตัวนำหน้าโดยตรง หรือก็คือ ''n'' เป็นสิ่งที่เรียกกันว่า[[จำนวนเชิงอันดับที่จำกัด|จำนวนเชิงอันดับที่ลิมิต]] (limit ordinal)
หากพูดให้ชัดเจน ไม่จำเป็นที่จะต้องพิสูจน์กรณีฐานในการอุปนัยเชิงอนันต์เพราะมันเป็นกรณีพิเศษ[[ความจริงว่างเปล่า|ว่างเปล่า]] (vacuous truth) ของประพจน์ว่าหาก ''P'' เป็นจริงสำหรับค่า {{nowrap|''n'' < ''m''}} ทุกค่าแล้ว ''P'' จะเป็นจริงสำหรับ ''m'' มันเป็นจริงอย่างว่างเปล่าก็เป็นเพราะว่าไม่มีค่า {{nowrap|''n'' < ''m''}} ค่าใดซึ่งสามารถทำหน้าที่เป็นตัวอย่างขัดแย้งได้

== ความสัมพันธ์กับหลักการจัดอันดับดี{{anchor|การพิสูจน์การอุปนัยเชิงคณิตศาสตร์}} ==
หลักการอุปนัยเชิงคณิตศาสตร์มักถูกระบุว่าเป็น[[สัจพจน์]]ข้อหนึ่งของจำนวนธรรมชาติ (ดูที่[[สัจพจน์เปอาโน]]) หลักการนี้แรงกว่า[[หลักการจัดอันดับดี]] (Well-ordering principle) หากกำหนดสัจพจน์เปอาโนข้ออื่น ๆ มาด้วย 

สมมุติข้อความดังต่อไปนี้:
* สัจพจน์[[ไตรวิภาค (คณิตศาสตร์)|ไตรวิภาค]] (trichotomy (mathematics)): สำหรับจำนวนธรรมชาติ ''n'' และ ''m'' ใด ๆ ''n'' น้อยกว่าหรือเท่ากับ ''m'' ก็ต่อเมื่อ ''m'' ไม่น้อยกว่า ''n'' 
* สำหรับจำนวนธรรมชาติ ''n'' ใด ๆ {{nowrap|''n'' + 1}} {{nowrap|มากกว่า ''n''}} 
* สำหรับจำนวนธรรมชาติ ''n'' ใด ๆ ไม่มีจำนวนธรรมชาติที่อยู่{{nowrap|ระหว่าง ''n''}} และ {{nowrap|''n'' + 1}} 
* ไม่มีจำนวนธรรมชาติที่น้อยกว่าศูนย์

สามารถพิสูจน์ด้วยสัจพจน์ที่สมมติไว้ด้านบนได้ว่า ถ้าการอุปนัยเป็นจริง แล้วการจัดอันดับดีเป็นจริง การพิสูจน์ต่อไปนี้ใช้การอุปนัยอย่างเข้มและสัจพจน์ข้อที่หนึ่งและสี่

''การพิสูจน์'' สมมติว่ามีเซตของจำนวนธรรมชาติ ''S'' ที่ไม่มีสมาชิกเล็กสุดซึ่งไม่ว่างอยู่ ให้ ''P''(''n'') เป็นข้อความว่า ''n'' ไม่อยู่ใน ''S'' แล้ว ''P''(0) จะเป็นจริงเพราะไม่เช่นนั้น ''0'' ก็จะกลายเป็นสมาชิกเล็กสุดของ ''S'' จากนั้นให้ ''n'' เป็นจำนวนธรรมชาติและสมมติว่า ''P''(''m'') เป็นจริงสำหรับจำนวนธรรมชาติ ''m'' ทุกตัวที่มีค่าน้อยกว่า ''n''+1 ฉะนั้นหาก ''P''(''n''+1) เป็นเท็จ ''n''+1 จะอยู่ใน ''S'' และจึงเป็นสมาชิกน้อยสุดของ ''S'' ซึ่งเป็นการขัดแย้ง ดังนั้น ''P''(''n''+1) จึงเป็นจริง เพราะฉะนั้น ''P''(''n'') เป็นจริงสำหรับจำนวนธรรมชาติ ''n'' ทุกตัวโดยหลักการอุปนัยอย่างเข้ม และ ''S'' จึงเป็นเซตว่างซึ่งก็เป็นการขัดแย้ง [[ซ.ต.พ.|∎]]

[[File:OmegaPlusOmega_svg.svg|thumb|600px|alt=ภาพของเส้นจำนวนซึ่งแสดงให้เห็นสมาชิกของเซตของคู่อันดับของศูนย์กับ n ยูเนียนกับเซตของคู่อันดับของหนึ่งกับ n โดย n เป็นจำนวนใด ๆ ซึ่งเป็นสมาชิกของจำนวนธรรมชาติ|"[[เส้นจำนวน]]" สำหรับเซต {{color|#800000|{(0,''n''): ''n''∈ℕ} }} ∪ {{color|#000080| {(1,''n''): ''n''∈ℕ}}} ตัวเลขอ้างอิงถึงส่วนประกอบส่วนที่สองของคู่อันดับ ส่วนประกอบส่วนที่หนึ่งสามารถรู้ได้จากสีหรือตำแหน่ง]]
ในทางกลับกันเซต {(0,''n''): ''n''∈ℕ} ∪ {(1,''n''): ''n''∈ℕ} ซึ่งแสดงอยู่ในรูปมีอันดับดี<ref name=Ohman2019 />{{rp|35lf}}โดย[[อันดับพจนานุกรม]] (lexicographic order) มากไปกว่านั้นยังสอดคล้องกับสัจพจน์เปอาโนทุกประการยกเว้นสัจพจน์อุปนัย โดยค่าคงตัว 0 ของเปอาโนถูกตีความเป็นคู่อันดับ (0,0) และฟังก์ชัน''ตัวตามหลัง''ของเปอาโนถูกนิยามไว้สำหรับคู่อันดับเป็น ''succ''(''x'',''n'')=(''x'',''n''+1) สำหรับ ''x''∈{0,1} และ ''n''∈ℕ ทุกตัว เพื่อเป็นตัวอย่างสำหรับการฝ่าฝืนสัจพจน์อุปนัยให้นิยามภาคแสดง ''P''(''x'',''n'') เป็น (''x'',''n'')=(0,0) หรือ (''x'',''n'')=(''succ''(''y'',''m'')) สำหรับ ''y''∈{0,1} และ ''m''∈ℕ บางตัว แล้วกรณีฐาน ''P''(0,0) จะเป็นจริงโดยธรรมดาและขั้นตอนอุปนัยก็เป็นจริงด้วย: หาก ''P''(''x'',''n'') แล้ว ''P''(''succ''(''x'',''n'')) แต่ทว่ากลับไม่เป็นจริงสำหรับคู่อันดับทุกคู่ในเซต

สัจพจน์ของเปอาโนกับหลักการอุปนัยเป็นโมเดลของจำนวนธรรมชาติเพียงแบบเดียว การเปลี่ยนหลักการอุปนัยเป็นหลักการจัดอันดับดีทำให้สามารถสร้างโมเดลที่แตกต่างออกไปซึ่งยังสอดคล้องกับสัจพจน์ทุกประการ<ref name=Ohman2019>{{cite journal |last1=Öhman |first1=Lars–Daniel |title=Are Induction and Well-Ordering Equivalent? |journal=The Mathematical Intelligencer |date=6 May 2019 |volume=41 |issue=3 |pages=33–40 |doi=10.1007/s00283-019-09898-4|doi-access=free }}</ref>

ในหนังสือและแหล่งข้อมูลหลายแห่งใส่ข้อมูลที่ผิดพลาด<ref name=Ohman2019 />ไว้ว่าหลักการจัดอันดับดีนั้นสมมูลกับสัจพจน์อุปนัย แต่ทว่านี่ไม่เป็นจริงในบริบทของสัจพจน์เปอาโนข้ออื่น ๆ แต่ในสัจพจน์อื่น ๆ จะสมมูลกัน<ref name=Ohman2019 /> หลักการจัดอันดับดีบอกเป็นนัยสัจพจน์อุปนัยในบริบทของสัจพจน์ซึ่งเรียงลำดับไว้ด้านบนสองข้อแรกและ
* จำนวนธรรมชาติทุกจำนวนไม่เป็น 0 ก็เป็น {{nowrap|''n'' + 1}} สำหรับ{{nowrap|จำนวนธรรมชาติ ''n''}} จำนวนใดจำนวนหนึ่ง

ข้อผิดพลาดซึ่งพบได้บ่อยในการพิสูจน์ซึ่งเข้าใจผิดคือการสมมติว่า {{nowrap|''n'' − 1}} เป็นจำนวนธรรมชาติที่เป็นได้อย่างเดียวและถูกนิยามไว้อย่างดีซึ่งเป็นคุณสมบัติที่สัจพจน์เปอาโนข้ออื่น ๆ ไม่ได้บอกเป็นนัย<ref name=Ohman2019 />

==ดูเพิ่ม==
*[[การพิสูจน์เชิงการจัด]] (Combinatorial proof)
*[[ปริศนาอุปนัย]] (Induction puzzles)
*[[การพิสูจน์โดยการแจงกรณี]] (Proof by exhaustion)
*[[การเรียกซ้ำ]]
*[[การเรียกซ้ำ (วิทยาการคอมพิวเตอร์)]] (recursion (computer science))
*[[การอุปนัยเชิงโครงสร้าง]] (Structural induction)
*[[การอุปนัยเชิงอนันต์]] (Transfinite induction)

==หมายเหตุ==
{{รายการหมายเหตุ}}

==อ้างอิง==
{{Reflist}}

==บรรณานุกรม==
{{refbegin|2}}
===บทนำ===
* {{cite book|first1=J.|last1=Franklin|author-link=James Franklin (philosopher)|year=2011|title=Proof in Mathematics: An Introduction|url=http://www.maths.unsw.edu.au/~jim/proofs.html|publisher=Kew Books|location=Sydney|isbn=978-0-646-54509-7|first2=A.|last2=Daoud}} (Ch. 8.)
* {{springer|title=Mathematical induction|id=p/m062640|mode=cs1}}
* {{cite book |first=Hans |last= Hermes |author-link=Hans Hermes|title=Introduction to Mathematical Logic |location=London |publisher=Springer |series=Hochschultext |issn=1431-4657 |isbn=978-3540058199 |year=1973|mr=0345788 }}
* {{cite book|first=Donald E.|last=Knuth|author-link=Donald Knuth|year=1997|title=The Art of Computer Programming, Volume 1: Fundamental Algorithms|title-link=The Art of Computer Programming|edition=3rd|publisher=Addison-Wesley | isbn=978-0-201-89683-1}} (Section 1.2.1: Mathematical Induction, pp.&nbsp;11–21.)
* {{cite book|first1=Andrey N.|last1=Kolmogorov|author-link=Andrey Kolmogorov|others=Silverman, R. A. (trans., ed.)|year=1975|title=Introductory Real Analysis|publisher=Dover|location=New York|isbn=978-0-486-61226-3|first2=Sergei V.|last2=Fomin|author2-link=Sergei Fomin|url=https://archive.org/details/introductoryreal00kolm_0}} (Section 3.8: Transfinite induction, pp.&nbsp;28–29.)

===ประวัติ===
* {{cite journal|journal=[[Archive for History of Exact Sciences]]|volume=55|issue=1|date=Aug 2000|pages=57–76|title=Plato: ''Parmenides'' 149a7-c3. A Proof by Complete Induction?|first=Fabio|last=Acerbi|doi=10.1007/s004070000020|jstor=41134098|s2cid=123045154|url=https://www.academia.edu/8016024}}
* {{cite journal|title=The Origin of Mathematical Induction|first=W. H.|jstor=2974308|last=Bussey|journal=[[The American Mathematical Monthly]]|volume=24|issue=5|year=1917|pages=199–207|doi=10.2307/2974308}}
* {{cite journal|first=Florian|last=Cajori|author-link=Florian Cajori|title=Origin of the Name "Mathematical Induction" | jstor=2972638|journal=[[The American Mathematical Monthly]] | year=1918 |volume=25 |issue=5 |pages=197–201 | doi=10.2307/2972638}}
* {{cite journal|last=Fowler |first=D.|author-link=David Fowler (mathematician)|year=1994|title=Could the Greeks Have Used Mathematical Induction? Did They Use It?|journal=Physis|volume=31|pages=253–265}}
* {{cite journal|first=Hans|last=Freudenthal|author-link=Hans Freudenthal|year=1953|title=Zur Geschichte der vollständigen Induction|journal=[[Archives Internationales d'Histoire des Sciences]]|volume=6|pages=17–37}}
* {{cite book|last=Katz|first= Victor J.|author-link=Victor J. Katz|year=1998|title=History of Mathematics: An Introduction |url=https://archive.org/details/historyofmathema00katz| publisher=[[Addison-Wesley]]|isbn=0-321-01618-1}}
* {{cite journal|last=Peirce|first=Charles Sanders|author-link=Charles Sanders Peirce|title=On the Logic of Number|url=https://books.google.com/books?id=LQgPAAAAIAAJ|journal=[[American Journal of Mathematics]]|volume=4|year=1881|number=1–4|pages=85–95|doi=10.2307/2369151|mr=1507856|jstor=2369151}} Reprinted (CP&nbsp;3.252–288), (W&nbsp;4:299–309)
* {{cite journal|first=Nachum L.|last=Rabinovitch|author-link=Nahum Rabinovitch|title=Rabbi Levi Ben Gershon and the origins of mathematical induction|url=https://archive.org/details/sim_archive-for-history-of-exact-sciences_1970-05-29_6_3/page/n68|journal=Archive for History of Exact Sciences| year=1970| volume=6| issue=3| pages=237–248| doi=10.1007/BF00327237|mr=1554128|s2cid=119948133 }}
* {{cite journal|first=Roshdi|last=Rashed|author-link=Roshdi Rashed|title=L'induction mathématique: al-Karajī, as-Samaw'al|url=https://archive.org/details/sim_archive-for-history-of-exact-sciences_1972-11-24_9_1/page/n2| journal=[[Archive for History of Exact Sciences]]| year=1972| volume=9| issue=1| pages=1–21| doi=10.1007/BF00348537| language=fr| mr=1554160| s2cid=124040444 }}
* {{cite book|title=The Development of Arabic Mathematics: Between Arithmetic and Algebra|volume=156|series=Boston Studies in the Philosophy of Science|publisher=Springer Science & Business Media|first=R.|last=Rashed|year=1994|isbn=9780792325659|url=https://books.google.com/books?id=vSkClSvU_9AC&pg=PA62|contribution=Mathematical induction: al-Karajī and al-Samawʾal|language=en}}
* {{cite book|first=Paul|last=Shields|chapter=Peirce's Axiomatization of Arithmetic|title=Studies in the Logic of Charles S. Peirce|url=https://archive.org/details/studiesinlogicof00nath|url-access=registration|pages=43–52|publisher=Indiana University Press|year=1997|mr=1720827|isbn=0-253-33020-3|editor1-first=Nathan|editor1-last=Houser|editor2-first=Don D.|editor2-last=Roberts|editor3-first=James Van|editor3-last=Evra}}
* {{cite journal | url=http://web.stonehill.edu/compsci/Shai_papers/MathofLevi.pdf | first=Charles G. | last=Simonson | title=The Mathematics of Levi ben Gershon, the Ralbag | journal=Bekhol Derakhekha Daehu | publisher=Bar-Ilan University Press | volume=10 | pages=5&ndash;21 | date=Winter 2000 | access-date=2020-12-27 | archive-date=2017-10-11 | archive-url=https://web.archive.org/web/20171011045341/http://web.stonehill.edu/compsci/Shai_papers/MathofLevi.pdf | url-status=dead }}
* {{cite journal|last=Unguru|first=S.|author-link=Sabetai Unguru|year=1991|title=Greek Mathematics and Mathematical Induction | journal=Physis|volume=28|pages=273–289}}
* {{cite journal|last=Unguru|first=S.|author-link=Sabetai Unguru|year=1994|title=Fowling after Induction | journal=Physis | volume=31|pages=267–272}}
* {{cite journal|first=G.|last=Vacca|title=Maurolycus, the First Discoverer of the Principle of Mathematical Induction | journal=[[Bulletin of the American Mathematical Society]] |year=1909| volume=16| pages=70–73| doi=10.1090/S0002-9904-1909-01860-9| issue=2| doi-access=free| mr=1558845}}
* {{cite journal|title=The Use of Mathematical Induction by Abū Kāmil Shujā' Ibn Aslam (850-930)| first=Mohammad| last=Yadegari| journal=[[Isis (journal)|Isis]]| volume=69| issue=2| year=1978| pages=259–262| doi=10.1086/352009| jstor=230435| s2cid=144112534 }}
{{refend}}

{{คณิตตรรกศาสตร์}}
{{Authority control}}

[[หมวดหมู่:การอุปนัยเชิงคณิตศาสตร์| ]]