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

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

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

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

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

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

การพิสูจน์โดยปริยายด้วยการอุปนัยเชิงคณิตศาสตร์แรก ๆ ในประเทศอินเดียปรากฏอยู่ใน "จักรวาลวิธี" (Chakravala method) ของภาสคาราที่ 2 (Bhāskara II) แปล: "กระบวนการให้เหตุผลซึ่งเรียกว่า 'การอุปนัยเชิงคณิตศาสตร์' มีจุดกำเนิดอิสระที่หลากหลาย ตั้งแต่ชาวสวิส ยาคอบ แบร์นูลลี, ชาวฝรั่งเศส แบลซ ปัสกาล และ ปีแยร์ เดอ แฟร์มา และชาวอิตาลี ฟรันเชสโก เมาโรลีโก [...] เราสามารถพบร่องรอยของการอุปนัยเชิงคณิตศาสตร์ได้เก่ากว่าเดิมหากอ่านตีความสักหน่อย ไม่ว่าในงานเขียนของชาวฮินดูและกรีก ตัวอย่างเช่น 'จักรวาลวิธี' ของภาสคารา และในการพิสูจน์ว่าจำนวนเฉพาะมีจำนวนมากเป็นอนันต์ของยุคลิด" และใน อัลฟะครี (al-Fakhri) ซึ่งถูกเขียนขึ้นในประมาณปี ค.ศ. 1000 โดยอัลกะระญี (al-Karaji) ซึ่งเขานำมาประยุกต์ใช้กับอนุกรมเลขคณิตเพื่อพิสูจน์ทฤษฎีบททวินามและคุณสมบัติของสามเหลี่ยมปัสกาล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 ในงานของนักคณิตศาสตร์ชาวเปอร์เซีย อัลกะระญี"

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

สมมติฐานการอุปนัยนี้ยังถูกนำมาใช้โดย ยาคอบ แบร์นูลลี (Jakob Bernoulli) และก็กลายเป็นที่รู้จักตั้งแต่นั้นมา การปฏิบัติต่อหลักการนี้อย่างรูปนัยแบบสมัยใหม่มีขึ้นในคริสตศตวรรษที่ 19 โดย จอร์จ บูล"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, ) แปล: "บางครั้งก็จำเป็นจะต้องพิสูจน์ทฤษฎีบทบทหนึ่งว่าเป็นจริงสำหรับค่า n ซึ่งเป็นจำนวนเต็มใด ๆ ส่วนวิธีการพิสูจน์นั้นมักจะมีชนิดดังต่อไปนี้ หนึ่ง ทฤษฎีบทบทนั้นจะถูกพิสูจน์ว่าเป็นจริงเมื่อ n = 1 สอง มันจะถูกพิสูจน์ว่าหากทฤษฎีบทนี้เป็นจริงเมื่อ n เป็นจำนวนเต็มใด ๆ มันก็จะเป็นจริงสำหรับ n จำนวนต่อไปที่มากกว่าด้วย ดังนั้นแล้วทฤษฎีบทนี้จึงเป็นจริงโดยสากล . .. การอ้างเหตุผลชนิดนี้สามารถเรียกได้ว่าเป็น โซริเตส  (Polysyllogism) ต่อเนื่อง" ออกัสตัส เดอ มอร์แกน (Augustus de Morgan), ชารลส์ แซนเดอรส์ เพิร์ซ (Charles Sanders Peirce), 
จูเซ็ปเป เปอาโน (Giuseppe Peano) และ ริชาร์ด เดเดคินด์ (Richard Dedekind)

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

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

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

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

นี่เป็นสูตรทั่วไปสำหรับผลบวกของจำนวนธรรมชาติที่น้อยกว่าหรือเท่ากับ  ซึ่งประกอบไปด้วยข้อความที่มีจำนวนมากเป็นอนันต์: ,  ,  , ฯลฯ

ประพจน์  สำหรับ  ใด ๆ,  

การพิสูจน์  ให้ P(n) เป็นข้อความ  เราจะพิสูจน์โดยการอุปนัยบน 

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

P(0) เป็นจริงอย่างชัดเจน:  

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

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

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

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

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

อสมการตรีโกณมิติ
อสมการมักถูกพิสูจน์ด้วยการอุปนัย เราจะพิสูจน์ว่า  สำหรับจำนวนจริง  และจำนวนธรรมชาติ  ใด ๆ  

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

ประพจน์.  สำหรับค่า  ใด ๆ,  .  

การพิสูจน์  กำหนดจำนวนจริง  ค่าใด ๆ ค่าหนึ่ง, และให้  เป็นข้อความ . และเราพิสูจน์โดยการอุปนัยกับ .  

กรณีฐาน: การคำนวณ  พิสูจน์ว่า  เป็นจริง. 

ขั้นตอนอุปนัย: เราจะแสดงว่า  สำหรับจำนวนธรรมชาติ  ใด ๆ.  สมมุติสมมติฐานอุปนัยว่าสำหรับค่า  กรณีของ  จะเป็นจริง เรานิรนัยโดยใช้สูตรผลบวกของมุมและอสมการอิงรูปสามเหลี่ยมได้: 

อสมการระหว่างฝั่งซ้ายและฝั่งขวาแสดงให้เห็นว่า  เป็นจริง ขั้นตอนอุปนัยจึงเสร็จสมบูรณ์

ข้อสรุป: ประพจน์  เป็นจริงสำหรับเลขจำนวนธรรมชาติ  ทุกค่า ∎

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

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

เราสามารถพิสูจน์ได้ว่าข้อความ  ข้อความหนึ่งเป็นจริงสำหรับค่า  หรือแม้แต่สำหรับค่า  การอุปนัยเชิงคณิตศาสตร์รูปแบบนี้ความจริงแล้วเป็นกรณีพิเศษของรูปแบบก่อนหน้าเพราะหากข้อความที่ถูกพิสูจน์คือ  แล้ว การพิสูจน์ด้วยกฎสองข้อนี้ก็เท่ากับการพิสูจน์ข้อความ  สำหรับจำนวนธรรมชาติ  ทุกจำนวนโดยมีกรณีฐานอุปนัยกับค่า Ted Sundstrom, Mathematical Reasoning, p. 190, Pearson, 2006, 

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

กรณีฐาน: การแสดงให้เห็นว่า  เป็นจริงสำหรับ  ง่ายมาก เพียงแค่มีเหรียญสี่บาทสามเหรียญ 

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

เพราะฉะนั้น  เป็นจริงสำหรับค่า  ทุกค่าด้วยหลักการอุปนัย และการพิสูจน์จึงสมบูรณ์

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

เมื่อ  เป็นจำนวนฟีโบนัชชีลำดับที่ n,  (อัตราส่วนทอง) และ  เป็นรากทั้งสองของพหุนาม  เราสามารถพิสูจน์เอกลักษณ์ข้างต้นด้วยการคำนวณ  ตรง ๆ หากเราสมมุติว่าเอกลักษณ์ดังกล่าวเป็นจริงสำหรับ  และ  และใช้ข้อเท็จจริงว่า  สำหรับทุก  

เพื่อให้การพิสูจน์โดยการอุปนัยอย่างเข้มเสร็จสมบูรณ์ เราจะต้องพิสูจน์เอกลักษณ์ในกรณีฐานสองกรณี ได้แก่  และ  

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

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

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

กรณีฐาน: แสดงให้เห็นว่า  เป็นจริงสำหรับค่า 



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

สมมติฐานอุปนัย: กำหนดจำนวน  ค่าหนึ่ง สมมติว่า  เป็นจริงสำหรับค่า  ทุกค่าที่ .

ขั้นตอนอุปนัย: จะพิสูจน์ว่า  เป็นจริง

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

การอุปนัยเดินหน้า-ถอยหลัง
บางครั้งการพิสูจน์ถอยหลัง หรือการพิสูจน์ข้อความในกรณี  เมื่อทราบว่าข้อความเป็นจริงในกรณี  จะสะดวกกว่า อย่างไรก็ตามไม่มีเลขตัวใดเพียงตัวเดียวที่เหมาะสมจะเป็นกรณีฐานของการอุปนัยได้ เราต้องพิสูจน์ข้อความสำหรับเซตย่อยอนันต์ของจำนวนธรรมชาติบางตัวแทน เช่น โอกุสแต็ง-หลุยส์ โกชีใช้การอุปนัยเดินหน้า (หรือการอุปนัยปรกติ) เพื่อพิสูจน์อสมการมัชฌิมเลขคณิต-เรขาคณิต (inequality of arithmetic and geometric means) ในกรณีจำนวนตัวแปรเท่ากับกำลังของ 2 ทุกค่า แล้วใช้การอุปนัยถอยหลังเพื่อแสดงให้เห็นว่าเป็นจริงสำหรับจำนวนธรรมชาติทุกจำนวนด้วย Cauchy, Augustin-Louis (1821). Cours d'analyse de l'École Royale Polytechnique, première partie, Analyse algébrique,  Paris. สามารถพบการพิสูจน์อสมการมัชฌิมเลขคณิต-เรขาคณิตได้ที่หน้า 457ff.

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

ขั้นตอนอุปนัยจะต้องถูกพิสูจน์สำหรับ n ทุกค่า เพื่อแสดงสิ่งนี้ให้เห็น โจเอล อี. โคเฮน ได้นำเสนอการอ้างเหตุผลว่าสามารถพิสูจน์ว่าม้าทุกตัวมีสีเดียวกัน (All horses are the same color) ได้ด้วยการอุปนัยเชิงคณิตศาสตร์ ดังต่อไปนี้:. Reprinted in A Random Walk in Science (R. L. Weber, ed.), Crane, Russak & Co., 1973.
กรณีฐาน: ในเซตของม้าแค่หนึ่งตัว จะมีสีแค่หนึ่งสี
ขั้นตอนอุปนัย: สมมติว่าในเซตของม้า  ตัวเซตใด ๆ ก็จะมีสีเพียงหนึ่งสีเป็นสมมติฐานอุปนัย คราวนี้ดูที่เซตของม้า  ตัว ใส่ลำดับเลขแต่ละตัวเป็น:  พิจารณาเซต  และ  แต่ละเซตเป็นเซตของม้า   ตัวเพราะฉะนั้นจึงมีสีเพียงสีเดียวในแต่ละเซตและทั้งสองเซตเหลื่อมกัน ม้า  ตัวทุกตัวจึงจะต้องมีสีเพียงสีเดียวเท่านั้น

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

การกำหนดรูปนัย  

เราสามารถเขียน "สัจพจน์ของการอุปนัย" ในตรรกะอันดับสอง (second-order logic) ได้ดังนี้:
 ,
ซึ่ง P(.) เป็นตัวแปรของภาคแสดงซึ่งมีจำนวนธรรมชาติหนึ่งตัวเป็นตัวแปรและ k กับ n เป็นตัวแปรของจำนวนธรรมชาติ 

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

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

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

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

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

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

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

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

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

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

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

สมมุติข้อความดังต่อไปนี้:
 สัจพจน์ไตรวิภาค (trichotomy (mathematics)): สำหรับจำนวนธรรมชาติ n และ m ใด ๆ n น้อยกว่าหรือเท่ากับ m ก็ต่อเมื่อ m ไม่น้อยกว่า n 
 สำหรับจำนวนธรรมชาติ n ใด ๆ   
 สำหรับจำนวนธรรมชาติ 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∈ℕ} ซึ่งแสดงอยู่ในรูปมีอันดับดีโดยอันดับพจนานุกรม (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)) แต่ทว่ากลับไม่เป็นจริงสำหรับคู่อันดับทุกคู่ในเซต

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

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

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

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

หมายเหตุ

อ้างอิง

บรรณานุกรม

บทนำ
  (Ch. 8.)


  (Section 1.2.1: Mathematical Induction, pp. 11–21.)
  (Section 3.8: Transfinite induction, pp. 28–29.)

ประวัติ






  Reprinted (CP 3.252–288), (W 4:299–309)