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

thumb|600px|alt=ภาพของเส้นจำนวนซึ่งแสดงให้เห็นสมาชิกของเซตของคู่อันดับของศูนย์กับ n ยูเนียนกับเซตของคู่อันดับของหนึ่งกับ n โดย n เป็นจำนวนใด ๆ ซึ่งเป็นสมาชิกของจำนวนธรรมชาติ|"เส้นจำนวน" สำหรับเซต  ∪ } ตัวเลขอ้างอิงถึงส่วนประกอบส่วนที่สองของคู่อันดับ ส่วนประกอบส่วนที่หนึ่งสามารถรู้ได้จากสีหรือตำแหน่ง
ในทางกลับกันเซต {(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)

หมายเหตุ