การอุปนัยเชิงคณิตศาสตร์

ระวังสับสนกับ การอนุมานแบบอุปนัย หรือ การให้เหตุผลแบบอุปนัย

การอุปนัยเชิงคณิตศาสตร์สามารถถูกแสดงให้เห็นอย่างอรูปนัยได้ด้วยการเทียบกับผลกระทบลูกโซ่แบบโดมิโนที่ล้มทับกัน^[1][2]

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

"การอุปนัยเชิงคณิตศาสตร์พิสูจน์ว่าเราสามารถปีนบันไดสูงเท่าไหร่ก็ได้ พิสูจน์โดยการปีนขึ้นขั้นแรก (ฐานของบันได) และจากนั้นก็สามารถปีนขึ้นขั้นต่อไปจากขั้นไหนก็ได้"^[a]

— Concrete Mathematics, ริมกระดาษหน้า 3

การพิสูจน์ด้วยการอุปนัย (proof by induction) ประกอบไปด้วยกรณีสองกรณี กรณีแรกคือ กรณีฐาน (base case หรือ basis) เป็นการพิสูจน์สำหรับข้อความที่ n = 0 โดยไม่ต้องรู้อะไรเกี่ยวกับกรณีอื่น ๆ เลย กรณีที่สองคือ ขั้นตอนอุปนัย (induction step) เป็นการพิสูจน์ว่าถ้าข้อความเป็นจริงสำหรับ n = k ใด ๆ แล้ว มันก็ต้องเป็นจริงสำหรับกรณี n = k + 1 ถัด ๆ ไปด้วย ขั้นตอนสองขั้นตอนนี้แสดงให้เห็นว่าข้อความนั้นเป็นจริงสำหรับจำนวนธรรมชาติ n ทุกจำนวน^[3] กรณีฐานไม่จำเป็นต้องเริ่มด้วย n = 0 แต่มักจะเริ่มด้วย n = 1 และก็เป็นไปได้ที่จะใช้จำนวนธรรมชาติ n = N คงที่ใด ๆ เพื่อแสดงให้เห็นว่าข้อความเป็นจริงสำหรับจำนวนธรรมชาติ n ≥ N ทุกตัว

วิธีการนี้สามารถนำมาขยายใช้เพื่อพิสูจน์ข้อความเกี่ยวกับโครงสร้างรากฐานดี (well-founded) ที่ทั่วไปมากขึ้นเช่นต้นไม้ (tree (set theory)) การวางนัยทั่วไปนี้ซึ่งมีชื่อว่าการอุปนัยเชิงโครงสร้าง (structural induction) ถูกใช้ในคณิตตรรกศาสตร์และวิทยาการคอมพิวเตอร์ การอุปนัยเชิงคณิตศาสตร์ในความหมายแบบขยายมีความใกล้เคียงกับการเรียกซ้ำ การอุปนัยเชิงคณิตศาสตร์เป็นกฏการอนุมาน (rule of inference) ที่ถูกใช้ในการพิสูจน์เชิงรูปนัย (formal proof) และในบางรูปแบบก็เป็นรากฐานของการพิสูจน์ความถูกต้องของโปรแกรมคอมพิวเตอร์ (formal verification) ทั้งหมด^[4]

แม้ชื่อจะคล้ายกันแต่ไม่ควรสับสนการอุปนัยเชิงคณิตศาสตร์กับการให้เหตุผลแบบอุปนัยที่ใช้ในปรัชญา (ดูปัญหาของการอุปนัย (Problem of induction)) วิธีการทางคณิตศาสตร์วิธีนี้ตรวจสอบกรณีจำนวนมากเป็นอนันต์เพื่อพิสูจน์ข้อความทั่วไปข้อหนึ่ง แต่ทำเช่นนั้นด้วยอนุกรมของการให้เหตุผลแบบนิรนัยจำนวนจำกัดซึ่งใช้ตัวแปร n แทนค่าจำนวนได้มากเป็นอนันต์^[5]

ประวัติ

ในปี 370 ก่อนคริสต์ศักราช พาร์เมนิเดสของเพลโตมีตัวอย่างแรก ๆ ของการพิสูจน์แบบอุปนัยโดยปริยาย^[6] การนำการอุปนัยเชิงคณิตศาสตร์มาใช้อย่างชัดเจนเป็นครั้งแรกที่สุดสามารถพบได้ในการพิสูจน์ของยุคลิด^[7]ที่บอกว่ามีจำนวนเฉพาะมากเป็นอนันต์ เทคนิคการทำซ้ำซึ่งตรงข้ามกันใช้การนับลงแทนการนับเพิ่มขึ้นที่ละหนึ่งและสามารถพบได้ในปฏิทรรศน์กองทราย (sorites paradox) ซึ่งมีการอ้างเหตุผลว่าหากทราย 1,000,000 เม็ดก่อตัวเป็นกองทรายและการเอาทรายออกเม็ดหนึ่งกองนั้นก็ยังถูกนับได้ว่าเป็นกองทรายแล้ว ทรายเพียงเม็ดเดียว (หรือไม่มีสักเม็ดเลย) ก็เป็นกองทรายเช่นเดิม^[8]

การพิสูจน์โดยปริยายด้วยการอุปนัยเชิงคณิตศาสตร์แรก ๆ ในประเทศอินเดียปรากฏอยู่ใน "จักรวาลวิธี" (Chakravala method) ของภาสคาราที่ 2 (Bhāskara II)^[9] และใน อัลฟะครี (al-Fakhri) ซึ่งถูกเขียนขึ้นในประมาณปี ค.ศ. 1000 โดยอัลกะระญี (al-Karaji) ซึ่งเขานำมาประยุกต์ใช้กับอนุกรมเลขคณิตเพื่อพิสูจน์ทฤษฎีบททวินามและคุณสมบัติของสามเหลี่ยมปัสกาล^[10][11]

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

สมมติฐานการอุปนัยนี้ยังถูกนำมาใช้โดย ยาคอบ แบร์นูลลี (Jakob Bernoulli) และก็กลายเป็นที่รู้จักตั้งแต่นั้นมา การปฏิบัติต่อหลักการนี้อย่างรูปนัยแบบสมัยใหม่มีขึ้นในคริสตศตวรรษที่ 19 โดย จอร์จ บูล^[14] ออกัสตัส เดอ มอร์แกน (Augustus de Morgan), ชารลส์ แซนเดอรส์ เพิร์ซ (Charles Sanders Peirce),^[15][16] จูเซ็ปเป เปอาโน (Giuseppe Peano) และ ริชาร์ด เดเดคินด์ (Richard Dedekind)^[9]

คำบรรยาย

รูปแบบการอุปนัยเชิงคณิตศาสตร์ที่ง่ายและพบเจอได้มากที่สุดอนุมานว่าข้อความใด ๆ ที่มีการใช้จำนวนธรรมชาติ ${\displaystyle n}$ (นั้นคือจำนวนเต็ม ${\displaystyle n\geq 0}$ หรือ 1) เป็นจริงสำหรับค่า ${\displaystyle n}$ ใด ๆ การพิสูจน์ประกอบด้วยสองขั้นตอนคือ:

1. กรณีฐาน หรือ กรณีต้น: พิสูจน์ว่าข้อความเป็นจริงสำหรับค่า 0 หรือ 1
2. ขั้นตอนอุปนัย หรือ กรณีขั้นตอน: พิสูจน์ว่าหากข้อความเป็นจริงสำหรับค่า ${\displaystyle n}$ ทุกค่า ข้อความจะเป็นจริงสำหรับ ${\displaystyle n+1}$ ด้วย หรือพูดอีกแบบคือให้สมมุติว่าข้อความเป็นจริงสำหรับจำนวนธรรมชาติ n ใด ๆ และพิสูจน์ว่าข้อความนั้นเป็นจริงสำหรับค่า ${\displaystyle n+1}$

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

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

ตัวอย่าง

ผลบวกของจำนวนธรรมชาติที่ต่อเนื่องตามลำดับ

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

${\displaystyle P(n)\!:\ \ 0+1+2+\cdots +n\,=\,{\frac {n(n+1)}{2}}.}$

นี่เป็นสูตรทั่วไปสำหรับผลบวกของจำนวนธรรมชาติที่น้อยกว่าหรือเท่ากับจำนวนที่กำหนด ซึ่งเป็นอนุกรมของข้อความจำนวนมากเป็นอนันต์โดยพฤตินัย: ${\displaystyle 0={\tfrac {(0)(0+1)}{2}}}$, ${\displaystyle 0+1={\tfrac {(1)(1+1)}{2}}}$, ${\displaystyle 0+1+2={\tfrac {(2)(2+1)}{2}}}$, ฯลฯ

ประพจน์ สำหรับจำนวน ${\displaystyle n\in \mathbb {N} }$ ใด ๆ, ${\displaystyle 0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.}$

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

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

P(0) เป็นจริงอย่างชัดเจน: ${\displaystyle 0={\tfrac {0(0+1)}{2}}\,.}$

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

สมมุติสมมติฐานอุปนัยว่าสำหรับค่า k ค่าหนึ่ง กรณีที่ n = k เป็นจริง หมายความว่า P(k) เป็นจริงด้วย:

${\displaystyle 0+1+\cdots +k\ =\ {\frac {k(k{+}1)}{2}}.}$

ดังนั้น:

${\displaystyle (0+1+2+\cdots +k)+(k{+}1)\ =\ {\frac {k(k{+}1)}{2}}+(k{+}1).}$

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

${\displaystyle {\begin{aligned}{\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{aligned}}}$

จับฝั่งซ้ายและฝั่งขวาเข้าสมการ เรานิรนัยได้ว่า:

${\displaystyle 0+1+2+\cdots +k+(k{+}1)\ =\ {\frac {(k{+}1)((k{+}1)+1)}{2}}.}$

นั่นคือข้อความว่า P(k+1) เป็นจริงด้วย เป็นการแสดงขั้นตอนอุปนัย

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

อสมการตรีโกณมิติ

อสมการมักถูกพิสูจน์ด้วยการอุปนัย เราจะพิสูจน์ว่า ${\displaystyle |\!\sin nx|\leq n|\!\sin x|}$ สำหรับจำนวนจริง ${\displaystyle x}$ และจำนวนธรรมชาติ ${\displaystyle n}$ ใด ๆ

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

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

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

กรณีฐาน: การคำนวณ ${\displaystyle |\!\sin 0x|=0\leq 0=0\,|\!\sin x|}$ พิสูจน์ว่า ${\displaystyle P(0)}$ เป็นจริง.

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

${\displaystyle {\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}}}$

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

ข้อสรุป: ประพจน์ ${\displaystyle P(n)}$ เป็นจริงสำหรับเลขจำนวนธรรมชาติ ${\displaystyle n}$ ทุกค่า ∎

รูปแปรผัน

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

ฐานของการอุปนัยนอกเหนือจาก 0 หรือ 1

หากเราไม่ประสงค์จะพิสูจน์ข้อความหนึ่งสำหรับจำนวนธรรมชาติทุกจำนวน แต่ต้องการพิสูจน์เพียงสำหรับจำนวน n ทุกจำนวนที่มีค่ามากกว่าหรือเท่ากับค่า b เท่านั้นแล้ว การพิสูจน์ด้วยการอุปนัยจะประกอบด้วย:

1. การแสดงให้เห็นว่าข้อความเป็นจริงเมื่อ ${\displaystyle n=b}$
2. การแสดงให้เห็นว่าหากข้อความเป็นจริงสำหรับค่า ${\textstyle n\geq b}$ ค่าหนึ่งแล้ว ข้อความเดียวกันนี้ก็จะเป็นจริงสำหรับค่า ${\displaystyle n+1}$ ด้วย

เราสามารถนำวิธีนี้มาใช้เพื่อแสดงให้เห็นว่า ${\textstyle 2^{n}\geq n+5}$ สำหรับ ${\displaystyle n\geq 3}$

เราสามารถพิสูจน์ได้ว่าข้อความ ${\displaystyle P(n)}$ ข้อความหนึ่งเป็นจริงสำหรับค่า ${\displaystyle n\geq 1}$ หรือแม้แต่สำหรับค่า ${\displaystyle n\geq -5}$ การอุปนัยเชิงคณิตศาสตร์รูปแบบนี้ความจริงแล้วเป็นกรณีพิเศษของรูปแบบก่อนหน้าเพราะหากข้อความที่ถูกพิสูจน์คือ ${\displaystyle P(n)}$ แล้ว การพิสูจน์ด้วยกฎสองข้อนี้ก็เท่ากับการพิสูจน์ข้อความ ${\displaystyle P(n+b)}$ สำหรับจำนวนธรรมชาติ ${\displaystyle n}$ ทุกจำนวนโดยมีกรณีฐานอุปนัยกับค่า ${\displaystyle 0}$^[17]

ตัวอย่าง: การใช้เหรียญบาทต่าง ๆ เพื่อให้รวมได้จำนวนเงินจำนวนหนึ่ง

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

กรณีฐาน: การแสดงให้เห็นว่า ${\displaystyle S(k)}$ เป็นจริงสำหรับ ${\displaystyle k=12}$ ง่ายมาก เพียงแค่มีเหรียญสี่บาทสามเหรียญ

ขั้นตอนอุปนัย: กำหนดให้ ${\displaystyle S(k)}$ เป็นจริงสำหรับค่า ${\displaystyle k\geq 12}$ ค่าหนึ่ง (สมมติฐานอุปนัย) พิสูจน์ว่า ${\displaystyle S(k+1)}$ เป็นจริงด้วย:

สมมติให้ ${\displaystyle S(k)}$ เป็นจริงสำหรับค่า ${\displaystyle k\geq 12}$ ใด ๆ หากมีคำตอบสำหรับจำนวน ${\displaystyle k}$ บาทที่อย่างน้อยต้องมีเหรียญสี่บาทอยู่หนึ่งเหรียญ เพียงแค่เปลี่ยนเหรียญสี่บาทเป็นเหรียญห้าบาทสักหนึ่งเหรียญก็จะได้จำนวนเงิน ${\displaystyle k+1}$ บาท หรือหากในคำตอบมีแต่เหรียญห้าบาท ${\displaystyle k}$ จำต้องเป็นจำนวนที่เป็นผลคูณของ 5 เพราะฉะนั้นต้องมีค่าเท่ากับ 15 เป็นอย่างน้อย เราจึงสามารถแทนเหรียญห้าบาททั้งสามเหรียญเป็นเหรียญสี่บาทสี่เหรียญเพื่อให้ได้จำนวนเงิน ${\displaystyle k+1}$ บาท ในกรณีแต่ละกรณีข้อความ ${\displaystyle S(k+1)}$ เป็นจริง

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

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

การอนุมานกับตัวนับมากกว่าหนึ่งตัว

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

การลดหลั่นอนันต์

บทความหลัก: การลดหลั่นอนันต์

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

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

การอุปนัยตัวเติมหน้า

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

${\displaystyle \forall k(P(k)\to P(k+1))}$

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

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

${\displaystyle \forall k(P(k)\to P(2k)\land P(2k+1))}$

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

${\displaystyle \forall k\left(P\left(\left\lfloor {\frac {k}{2}}\right\rfloor \right)\to P(k)\right)}$

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

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

การอุปนัยตัวนำหน้าสามารถจำลองการอุปนัยตัวเติมหน้ากับข้อความเดียวกันได้อย่างชัด การอุปนัยตัวเติมหน้าสามารถจำลองการอุปนัยตัวนำหน้าได้แต่ต้องแลกมาด้วยการทำให้วากยสัมพันธ์ของข้อความซับซ้อนขึ้น (เพิ่มตัวบ่งปริมาณทั้งหมดซึ่งมีขอบเขต) ผลลัพธ์ซึ่งแสดงความสัมพันธ์ของการอุปนัยตัวเติมหน้ากับการคำนวณซึ่งใช้เวลาพหูพจน์ (polynomial time) จึงขึ้นอยู่กับการเอาตัวบ่งปริมาณซึ่งไม่มีขอบเขตออกไปทั้งหมดและการจำกัดจำนวนการสับเปลี่ยนระหว่างตัวบ่งปริมาณทั้งหมดซึ่งมีขอบเขตกับตัวบ่งปริมาณบางตัวที่อนุญาตให้ทำในข้อความ^[18]

การอุปนัยอย่างเข้ม

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

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

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

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

ตัวอย่าง: จำนวนฟีโบนัชชี

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

${\displaystyle F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}}$

ซึ่ง ${\displaystyle F_{n}}$ เป็นจำนวนฟีโบนัชชีจำนวนที่ n, ${\textstyle \varphi ={{1+{\sqrt {5}}} \over 2}}$ (อัตราส่วนทอง) และ ${\textstyle \psi ={{1-{\sqrt {5}}} \over 2}}$ เป็นรากของพหูพจน์ ${\displaystyle x^{2}-x-1}$ เอกลักษณ์ด้านบนสามารถถูกพิสูจน์ยืนยันด้วยการคำนวณ ${\textstyle F_{n+2}}$ โดยตรงหากเราสมมุติว่า ${\textstyle F_{n+1}}$ and ${\textstyle F_{n}}$ เป็นจริงอยู่แล้วด้วยการใช้ข้อเท็จจริงว่า ${\displaystyle F_{n+2}=F_{n+1}+F_{n}}$ สำหรับ ${\displaystyle n\in {\mathbb {N}}}$ แต่ละตัว เพื่อให้การพิสูจน์เสร็จสมบูรณ์ เอกลักษณ์จะต้องถูกพิสูจน์ยืนยันในกรณีฐานทั้งสองกรณี: ${\displaystyle n=0}$ และ ${\textstyle n=1}$

ตัวอย่าง: การแยกตัวประกอบเฉพาะ

การพิสูจน์ด้วยการอุปนัยอย่างเข้มอีกอันหนึ่งใช้สมมติฐานว่าข้อความเป็นจริงสำหรับจำนวน ${\displaystyle n}$ ทุกค่าที่น้อยกว่าอย่างถี่ถ้วนกว่า พิจารณาข้อความที่ว่า "จำนวนธรรมชาติทุกจำนวนซึ่งมากกว่า 1 เป็นผลคูณของจำนวนเฉพาะ (หนึ่งจำนวนหรือมากกว่า)" ซึ่งเป็นส่วน "การมีจริง" (existence) ของทฤษฎีบทมูลฐานของเลขคณิต สำหรับการพิสูจน์ขั้นตอนอุปนัยสมมติฐานอุปนัยคือสำหรับค่า ${\displaystyle n>1}$ ซึ่งกำหนดมาข้อความจะเป็นจริงสำหรับค่า ${\displaystyle n>1}$ ซึ่งน้อยกว่าทุกค่า หาก ${\displaystyle m}$ เป็นจำนวนเฉพาะแล้วมันเป็นผลคูณของจำนวนเฉพาะอย่างแน่นอน และหากไม่ใช่แล้วก็จะเป็นผลคูณ ${\displaystyle m=n_{1}n_{2}}$ โดยนิยามโดยตัวประกอบทั้งสองไม่เท่ากับ 1 ดังนั้นทั้งสองจึงไม่เท่ากับ ${\displaystyle m}$ เพราะฉะนั้นทั้งสองจึงมากกว่าหนึ่งและน้อยกว่า ${\displaystyle m}$ สมมติฐานอุปนัยตอนนี้ใช้ได้กับ ${\displaystyle n_{1}}$ และ ${\displaystyle n_{2}}$ ดังนั้นทั้งสองแต่ละตัวเป็นผลคูณของจำนวนเฉพาะ ฉะนั้น ${\displaystyle m}$ เป็นผลคูณของผลคูณของจำนวนเฉพาะและจึงเป็นผลคูณของจำนวนเฉพาะเองโดยการขยาย

ตัวอย่าง: กลับมาหาจำนวนเงินบาท

เราสมควรที่จะดูการพิสูจน์ตัวอย่างเดียวกับด้านบนครั้งนี้ด้วย การอุปนัยอย่างเข้ม ข้อความยังคงเดิม:

${\displaystyle S(n):\,\,n\geq 12\to \,\exists \,a,b\in \mathbb {N} .\,\,n=4a+5b}$

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

กรณีฐาน: แสดงให้เห็นว่า ${\displaystyle S(k)}$ เป็นจริงสำหรับค่า ${\displaystyle k=12,13,14,15}$.

${\displaystyle {\begin{aligned}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{aligned}}}$

กรณีฐานเป็นจริง

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

ขั้นตอนอุปนัย: พิสูจน์ว่า ${\displaystyle S(j)}$ เป็นจริง

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

การอุปนัยคืบหน้า-ถอยหลัง

บางครั้งการนิรนัยถอยหลังคือการพิสูจน์ข้อความสำหรับ ${\displaystyle n-1}$ เมื่อพิจารณาความสมเหตุสมผลของมันสำหรับ ${\displaystyle n}$ จะสะดวกกว่า อย่างไรก็ตามการไม่พิสูจน์ความสมเหตุสมผลของข้อความสำหรับเลขตัวใดเพียงพอเพื่อสร้างกรณีฐาน เราต้องพิสูจน์ข้อความสำหรับเซตย่อยของจำนวนธรรมชาติไม่มีสิ้นสุดแทน เช่น โอกุสแต็ง-หลุยส์ โกชี (Augustin Louis Cauchy) ใช้การอุปนัยคืบหน้า (ปรกติ) เพื่อพิสูจน์อสมการมัชฌิมเลขคณิต-เรขาคณิต (inequality of arithmetic and geometric means) สำหรับกำลังของ 2 ทุกค่า แล้วใช้การอุปนัยถอยหลังเพื่อแสดงให้เห็นว่าเป็นจริงสำหรับจำนวนธรรมชาติทุกจำนวนด้วย ^[19][20]

ตัวอย่างของความผิดพลาดในขั้นตอนอุปนัย

บทความหลัก: ม้าทุกตัวมีสีเดียวกัน

ขั้นตอนอุปนัยจะต้องถูกพิสูจน์สำหรับ n ทุกค่า เพื่อแสดงสิ่งนี้ให้เห็น โจเอล อี. โคเฮน ได้นำเสนอการอ้างเหตุผลว่าสามารถพิสูจน์ว่าม้าทุกตัวมีสีเดียวกัน (All horses are the same color) ได้ด้วยการอุปนัยเชิงคณิตศาสตร์ได้ดังต่อไปนี้:^[21]

• กรณีฐาน: ในเซตของม้าแค่หนึ่งตัว จะมีสีแค่หนึ่งสี
• ขั้นตอนอุปนัย: สมมติว่าในเซตของม้า ${\displaystyle n}$ ตัวเซตใด ๆ ก็จะมีสีเพียงหนึ่งสีเป็นสมมติฐานอุปนัย คราวนี้ดูที่เซตของม้า ${\displaystyle n+1}$ ตัว ใส่ลำดับเลขแต่ละตัวเป็น: ${\displaystyle 1,\;2,\;3,\;\dotsc ,\;n,\;n+1}$ พิจารณาเซต ${\textstyle \left\{1,\;2,\;3,\;\dotsc ,\;n\right\}}$ และ ${\textstyle \left\{2,\;3,\;4,\;\dotsc ,\;n+1\right\}}$ แต่ละเซตเป็นเซตของม้า ${\displaystyle n}$ ตัวเพราะฉะนั้นจึงมีสีเพียงสีเดียวในแต่ละเซตและทั้งสองเซตเหลื่อมกัน ม้า ${\displaystyle n+1}$ ตัวทุกตัวจึงจะต้องมีสีเพียงสีเดียวเท่านั้น

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

การกำหนดรูป

เราสามารถเขียน "สัจพจน์ของการอุปนัย" ในตรรกะอันดับสอง (second-order logic) ได้ดังนี้:

${\displaystyle \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 )}}$,

ซึ่ง P(.) เป็นตัวแปรของภาคแสดงซึ่งมีจำนวนธรรมชาติหนึ่งตัวและ k กับ n เป็นตัวแปรของจำนวนธรรมชาติ is a variable

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

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

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

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

การบ่งปริมาณกับภาคแสดงทำไม่ได้ในทฤษฎีเซตแซร์เมโล-เฟรนเคิลอันดับหนึ่ง (Zermelo-Fraenkel set theory) แต่เรายังสามารถแสดงการอุปนัยด้วยการบ่งปริมาณกับเซต:

${\displaystyle \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 )}}$

เราสามารถอ่าน ${\displaystyle A}$ เป็นเซตซึ่งแทนประพจน์และมีจำนวนธรรมชาติสำหรับที่ประพจน์เป็นจริง นี่ไม่ใช่สัจพจน์แต่เป็นทฤษฎีบทคล้ายกับของเปอาโน โดยกำหนดว่าจำนวนธรรมชาติถูกนิยามในภาษาของทฤษฎีเซต ZFC ด้วยสัจพจน์

การอุปนัยเชิงอนันต์

บทความหลัก: การอุปนัยเชิงอนันต์

(อังกฤษ: Transfinite induction) เราสามารถนำหลักการของการอุปนัยอย่างเข้มมาใช้กับข้อความเกี่ยวกับสมาชิกของเซตรากฐานดี (Well-founded set) เซตใด ๆ ได้ด้วยนอกเหนือจากข้อความเกี่ยวกับจำนวนธรรมชาติเท่านั้น นั่นคือเซตซึ่งมีความสัมพันธ์ไม่สะท้อน (irreflexive relation) ซึ่งไม่มีเซตอันดับทุกส่วนลดหลั่นอนันต์ (infinite descending chain) เซตของจำนวนเชิงการนับเซตใด ๆ เป็นเซตรากฐานดีซึ่งรวมไปถึงเซตของจำนวนธรรมชาติ เมื่อนำไปประยุกต์กับเซตรากฐานดีก็สามารถกำหนดรูปใหม่เป็นขั้นตอนเดียวได้ว่า:

1. แสดงให้เห็นว่าหากข้อความข้อหนึ่งเป็นจริงสำหรับค่า m < n ค่าใด ๆ แล้วข้อความเดียวกันนั้นก็จะเป็นจริงสำหรับ n ด้วย

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

การพิสูจน์โดยการอุปนัยเชิงอนันต์โดยปกติแล้วจะจำแนกกรณีเป็นสามกรณี:

1. เมื่อ n เป็นสมาชิกเล็กสุด หรือก็คือไม่มีสมาชิกซึ่งเล็กไปกว่า n อีก
2. เมื่อ n มีตัวนำหน้าโดยตรง หรือก็คือเซตของสมาชิกซึ่งเล็กกว่า n มีสมาชิกใหญ่สุด
3. เมื่อ n ไม่มีตัวนำหน้าโดยตรง หรือก็คือ n เป็นสิ่งที่เรียกกันว่าจำนวนเชิงอันดับที่จำกัด (limit ordinal)

หากพูดให้ชัดเจน มันไม่จำเป็นที่จะต้องพิสูจน์กรณีฐานในการอุปนัยเชิงอนันต์เพราะมันเป็นกรณีพิเศษว่างเปล่า (Vacuous truth) ของประพจน์ว่าหาก P เป็นจริงสำหรับค่า n < m ทุกค่าแล้ว P จะเป็นจริงสำหรับ m มันเป็นจริงอย่างว่างเปล่าก็เป็นเพราะว่าไม่มีค่า n < m ค่าใดซึ่งสามารถทำหน้าที่เป็นตัวอย่างขัดแย้งได้

ความสัมพันธ์กับหลักการจัดอันดับดี

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

• สัจพจน์ไตรวิภาค (trichotomy (mathematics)): n น้อยกว่าหรือเท่ากับ m ก็ต่อเมื่อ m ไม่น้อยกว่า n สำหรับจำนวนธรรมชาติ n และ m ใด ๆ
• n + 1 มากกว่า n สำหรับจำนวนธรรมชาติ n ใด ๆ
• ไม่มีจำนวนธรรมชาติที่อยู่ระหว่าง n และ n + 1 สำหรับจำนวนธรรมชาติ n ใด ๆ
• ไม่มีจำนวนธรรมชาติที่น้อยกว่าศูนย์

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

การพิสูจน์ สมมติว่ามีเซตของจำนวนธรรมชาติที่ไม่มีสมาชิกเล็กสุด 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 จึงเป็นเซตว่างซึ่งก็เป็นการขัดแย้ง ∎

"เส้นจำนวน" สำหรับเซต {(0,n): n∈ℕ} ∪ {(1,n): n∈ℕ} ตัวเลขอ้างอิงถึงส่วนประกอบส่วนที่สองของคู่อันดับ ส่วนประกอบส่วนที่หนึ่งสามารถรู้ได้จากสีหรือตำแหน่ง

ในทางกลับกันเซต {(0,n): n∈ℕ} ∪ {(1,n): n∈ℕ} ซึ่งแสดงอยู่ในรูปมีอันดับดี^[22]: 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)) แต่ทว่ากลับไม่เป็นจริงสำหรับคู่อันดับทุกคู่ในเซต

สัจพจน์ของเปอาโนกับหลักการอุปนัยจำลองแบบจำนวนธรรมชาติโดยเฉพาะ การเปลี่ยนหลักการอุปนัยเป็นหลักการจัดอันดับดีทำให้สามารถสร้างแบบจำลองที่แตกต่างมากขึ้นซึ่งสอดคล้องกับสัจพจน์ทุกประการ^[22]

ในหนังสือและแหล่งข้อมูลหลายแห่งใส่ข้อมูลที่ผิดพลาด^[22]ไว้ว่าหลักการจัดอันดับดีนั้นสมมูลกับสัจพจน์อุปนัย แต่ทว่านี่ไม่เป็นจริงในบริบทของสัจพจน์เปอาโนข้ออื่น ๆ แต่ในสัจพจน์อื่น ๆ จะสมมูลกัน^[22] หลักการจัดอันดับดีบอกเป็นนัยสัจพจน์อุปนัยในบริบทของสัจพจน์ซึ่งเรียงลำดับไว้ด้านบนสองข้อแรกและ

• จำนวนธรรมชาติทุกจำนวนไม่เป็น 0 ก็เป็น n + 1 สำหรับจำนวนธรรมชาติ n จำนวนใดจำนวนหนึ่ง

ข้อผิดพลาดซึ่งพบได้บ่อยในการพิสูจน์ซึ่งเข้าใจผิดคือการสมมติว่า n − 1 เป็นจำนวนธรรมชาติที่เป็นได้อย่างเดียวและถูกนิยามไว้อย่างดีซึ่งเป็นคุณสมบัติที่สัจพจน์เปอาโนข้ออื่น ๆ ไม่ได้บอกเป็นนัย^[22]

ดูเพิ่ม

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

หมายเหตุ

1. "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)."

อ้างอิง

1. Matt DeVos, Mathematical Induction, Simon Fraser University
2. Gerardo con Diaz, Mathematical Inductionเก็บถาวร 2 พฤษภาคม 2013 ที่ เวย์แบ็กแมชชีน, Harvard University
3. "The Definitive Glossary of Higher Mathematical Jargon — Proof by Induction". Math Vault (ภาษาอังกฤษแบบอเมริกัน). 2019-08-01. สืบค้นเมื่อ 2019-10-23.
4. Anderson, Robert B. (1979). Proving Programs Correct (ภาษาอังกฤษ). New York: John Wiley & Sons. p. 1. ISBN 978-0471033950.
5. Suber, Peter. "Mathematical Induction". Earlham College. คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2011-05-24. สืบค้นเมื่อ 26 March 2011.
6. Acerbi 2000.
7. Chris K. Caldwell. "Euclid's Proof of the Infinitude of Primes (c. 300 BC)". utm.edu. สืบค้นเมื่อ 2016-02-28.
8. Hyde & Raffman 2018. sfn error: no target: CITEREFHydeRaffman2018 (help)
9. Cajori (1918), p. 197: '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.' แปล: "กระบวนการให้เหตุผลซึ่งเรียกว่า 'การอุปนัยเชิงคณิตศาสตร์' มีจุดกำเนิดอิสระที่หลากหลาย ตั้งแต่ชาวสวิส ยาคอบ แบร์นูลลี, ชาวฝรั่งเศส แบลซ ปัสกาล และ ปีแยร์ เดอ แฟร์มา และชาวอิตาลี ฟรันเชสโก เมาโรลีโก [...] เราสามารถพบร่องรอยของการอุปนัยเชิงคณิตศาสตร์ได้เก่ากว่าเดิมหากอ่านตีความสักหน่อย ไม่ว่าในงานเขียนของชาวฮินดูและกรีก ตัวอย่างเช่น 'จักรวาลวิธี' ของภาสคารา และในการพิสูจน์ว่าจำนวนเฉพาะมีจำนวนมากเป็นอนันต์ของยุคลิด"
10. Rashed 1994, p. 62-84.
11. 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 ในงานของนักคณิตศาสตร์ชาวเปอร์เซีย อัลกะระญี"
12. Simonson 2000.
13. Rabinovitch 1970.
14. "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 n = 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 sorites" (Boole circa 1849 Elementary Treatise on Logic not mathematical pages 40–41 reprinted in 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 ซึ่งเป็นจำนวนเต็มใด ๆ ส่วนวิธีการพิสูจน์นั้นมักจะมีชนิดดังต่อไปนี้ หนึ่ง ทฤษฎีบทบทนั้นจะถูกพิสูจน์ว่าเป็นจริงเมื่อ n = 1 สอง มันจะถูกพิสูจน์ว่าหากทฤษฎีบทนี้เป็นจริงเมื่อ n เป็นจำนวนเต็มใด ๆ มันก็จะเป็นจริงสำหรับ n จำนวนต่อไปที่มากกว่าด้วย ดังนั้นแล้วทฤษฎีบทนี้จึงเป็นจริงโดยสากล . .. การอ้างเหตุผลชนิดนี้สามารถเรียกได้ว่าเป็น โซริเตส (Polysyllogism) ต่อเนื่อง"
15. Peirce 1881.
16. Shields 1997.
17. Ted Sundstrom, Mathematical Reasoning, p. 190, Pearson, 2006, ISBN 978-0131877184
18. Buss, Samuel (1986). Bounded Arithmetic. Naples: Bibliopolis.
19. "Forward-Backward Induction | Brilliant Math & Science Wiki". brilliant.org (ภาษาอังกฤษแบบอเมริกัน). สืบค้นเมื่อ 2019-10-23.
20. Cauchy, Augustin-Louis (1821). Cours d'analyse de l'École Royale Polytechnique, première partie, Analyse algébrique, เก็บถาวร 14 ตุลาคม 2017 ที่ เวย์แบ็กแมชชีน Paris. สามารถพบการพิสูจน์อสมการมัชฌิมเลขคณิต-เรขาคณิตได้ที่หน้า 457ff.
21. Cohen, Joel E. (1961), "On the nature of mathematical proof", Opus. Reprinted in A Random Walk in Science (R. L. Weber, ed.), Crane, Russak & Co., 1973.
22. Öhman, Lars–Daniel (6 May 2019). "Are Induction and Well-Ordering Equivalent?". The Mathematical Intelligencer. 41 (3): 33–40. doi:10.1007/s00283-019-09898-4.

บรรณานุกรม

บทนำ

• Franklin, J.; Daoud, A. (2011). Proof in Mathematics: An Introduction. Sydney: Kew Books. ISBN 978-0-646-54509-7. (Ch. 8.)
• Hazewinkel, Michiel, บ.ก. (2001), "Mathematical induction", Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
• Hermes, Hans (1973). Introduction to Mathematical Logic. Hochschultext. London: Springer. ISBN 978-3540058199. ISSN 1431-4657. MR 0345788.
• Knuth, Donald E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). 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 (Aug 2000). "Plato: Parmenides 149a7-c3. A Proof by Complete Induction?". Archive for History of Exact Sciences. 55 (1): 57–76. doi:10.1007/s004070000020. JSTOR 41134098. S2CID 123045154.
• Bussey, W. H. (1917). "The Origin of Mathematical Induction". The American Mathematical Monthly. 24 (5): 199–207. doi:10.2307/2974308. JSTOR 2974308.
• Cajori, Florian (1918). "Origin of the Name "Mathematical Induction"". The American Mathematical Monthly. 25 (5): 197–201. doi:10.2307/2972638. JSTOR 2972638.
• Fowler, D. (1994). "Could the Greeks Have Used Mathematical Induction? Did They Use It?". Physis. 31: 253–265.
• Freudenthal, Hans (1953). "Zur Geschichte der vollständigen Induction". Archives Internationales d'Histoire des Sciences. 6: 17–37.
• 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. doi:10.2307/2369151. JSTOR 2369151. MR 1507856. Reprinted (CP 3.252–288), (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. MR 1554128. S2CID 119948133.
• Rashed, Roshdi (1972). "L'induction mathématique: al-Karajī, as-Samaw'al". Archive for History of Exact Sciences (ภาษาฝรั่งเศส). 9 (1): 1–21. doi:10.1007/BF00348537. MR 1554160. S2CID 124040444.
• 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 (ภาษาอังกฤษ). Vol. 156. Springer Science & Business Media. ISBN 9780792325659.
• Shields, Paul (1997). "Peirce's Axiomatization of Arithmetic". ใน Houser, Nathan; Roberts, Don D.; Evra, James Van (บ.ก.). Studies in the Logic of Charles S. Peirce. Indiana University Press. pp. 43–52. ISBN 0-253-33020-3. MR 1720827.
• Simonson, Charles G. (Winter 2000). "The Mathematics of Levi ben Gershon, the Ralbag" (PDF). Bekhol Derakhekha Daehu. Bar-Ilan University Press. 10: 5–21. คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 2017-10-11. สืบค้นเมื่อ 2020-12-27.
• Unguru, S. (1991). "Greek Mathematics and Mathematical Induction". Physis. 28: 273–289.
• Unguru, S. (1994). "Fowling after Induction". Physis. 31: 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. MR 1558845.
• Yadegari, Mohammad (1978). "The Use of Mathematical Induction by Abū Kāmil Shujā' Ibn Aslam (850-930)". Isis. 69 (2): 259–262. doi:10.1086/352009. JSTOR 230435. S2CID 144112534.