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

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

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

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

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

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

คำบรรยาย

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

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

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

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

ตัวอย่าง

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

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

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

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

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

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

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

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

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

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

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

ดังนั้น:

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

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

$\begin{array}{cc}\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{array}$

ฝั่งซ้ายมือสุดและฝั่งขวาสุดเท่ากันตรงกลาง เรานิรนัยได้ว่า:

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

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

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

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

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

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

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

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

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

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

$\begin{array}{cccc}|\sin (k+1)x|& =& |\sin kx\cos x+\sin x\cos kx|& \text{(ผลบวกของมุม)}\\ & \le & |\sin kx\cos x|+|\sin x\cos kx|& \text{(อสมการอิงรูปสามเหลี่ยม)}\\ & =& |\sin kx||\cos x|+|\sin x||\cos kx|& \\ & \le & |\sin kx|+|\sin x|& (|\cos t|\le 1)\\ & \le & k|\sin x|+|\sin x|& \text{(สมมติฐานอุปนัย})\\ & =& (k+1)|\sin x|.& \end{array}$

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

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

รูปแบบอื่น

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$\mathrm{\forall }k(P(k)\to P(2k)\wedge P(2k+1))$

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

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

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

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

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

แม่แบบ:Anchor การอุปนัยอย่างเข้ม

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

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

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

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

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

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

$F_n=\frac{{\phi }^n-{\psi }^n}{\phi -\psi }$ สำหรับทุก n

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

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

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

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

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

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

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

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

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

$\begin{array}{c}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{array}$

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

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

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

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

การอุปนัยเดินหน้า-ถอยหลัง

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

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

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

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

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

การกำหนดรูปนัย แม่แบบ:Anchor

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

$\mathrm{\forall }P(P(0)\wedge \mathrm{\forall }k(P(k)\to P(k+1))\to \mathrm{\forall }n(P(n)\left)\right)$,

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

อธิบายได้ว่า กรณีฐาน 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, ZF) แต่เราสามารถแสดงการอุปนัยด้วยการบ่งปริมาณกับเซต:

$\mathrm{\forall }A(0\in A\wedge \mathrm{\forall }k\in \mathbb{N}(k\in A\to (k+1)\in A)\to \mathbb{N}\subseteq A)$

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

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

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

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

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

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

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

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

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

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

สมมุติข้อความดังต่อไปนี้:

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

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

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

"เส้นจำนวน" สำหรับเซต แม่แบบ:Color ∪ แม่แบบ:Color} ตัวเลขอ้างอิงถึงส่วนประกอบส่วนที่สองของคู่อันดับ ส่วนประกอบส่วนที่หนึ่งสามารถรู้ได้จากสีหรือตำแหน่ง

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

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

ดูเพิ่ม

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

บรรณานุกรม

บทนำ

• แม่แบบ:Cite book (Ch. 8.)
• แม่แบบ:Springer
• แม่แบบ:Cite book
• แม่แบบ:Cite book (Section 1.2.1: Mathematical Induction, pp. 11–21.)
• แม่แบบ:Cite book (Section 3.8: Transfinite induction, pp. 28–29.)

ประวัติ

• แม่แบบ:Cite journal
• แม่แบบ:Cite journal
• แม่แบบ:Cite journal
• แม่แบบ:Cite journal
• แม่แบบ:Cite journal
• แม่แบบ:Cite book
• แม่แบบ:Cite journal Reprinted (CP 3.252–288), (W 4:299–309)
• แม่แบบ:Cite journal
• แม่แบบ:Cite journal
• แม่แบบ:Cite book
• แม่แบบ:Cite book
• แม่แบบ:Cite journal
• แม่แบบ:Cite journal
• แม่แบบ:Cite journal
• แม่แบบ:Cite journal
• แม่แบบ:Cite journal