Loading AI tools
จากวิกิพีเดีย สารานุกรมเสรี
การอุปนัยเชิงคณิตศาสตร์ (อังกฤษ: Mathematical induction) เป็นเทคนิคการพิสูจน์เชิงคณิตศาสตร์ที่ใช้เพื่อพิสูจน์ว่าข้อความ P(n) เป็นจริงสำหรับจำนวนธรรมชาติทุกจำนวน n = 0, 1, 2, 3, . . . ; แปลว่าข้อความทั้งสิ้นเป็นลำดับของกรณี P(0), P(1), P(2), P(3), . . . . จำนวนมากไม่สิ้นสุด เราสามารถใช้คำอุปมาเพื่ออธิบายเทคนิคนี้ได้อย่างอรูปนัยด้วยการเทียบกับโดมิโนที่ล้มตาม ๆ กันหรือการปีนบันได:
"การอุปนัยเชิงคณิตศาสตร์พิสูจน์ว่าเราสามารถปีนบันไดสูงเท่าไหร่ก็ได้ พิสูจน์โดยการปีนขึ้นขั้นแรก (ฐานของบันได) และจากนั้นก็สามารถปีนขึ้นขั้นต่อไปจากขั้นไหนก็ได้"[lower-alpha 1]
— 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]
รูปแบบการอุปนัยเชิงคณิตศาสตร์ที่ง่ายและพบเจอได้มากที่สุดอนุมานว่าข้อความใด ๆ ที่มีการใช้จำนวนธรรมชาติ (นั้นคือจำนวนเต็ม หรือ 1) เป็นจริงสำหรับค่า ใด ๆ การพิสูจน์ประกอบด้วยสองขั้นตอนคือ:
สมมติฐานในขั้นตอนการอุปนัยที่กล่าวว่าข้อความเป็นจริงกับค่า ค่าหนึ่งเรียกว่า สมมติฐานอุปนัย ต้องมีการสมุมติสมมติฐานอุปนัยสำหรับค่า และใช้สมมติฐานนี้เพื่อพิสูจน์ว่าข้อความนั้นเป็นจริงสำหรับ เพื่อพิสูจน์ขั้นตอนอุปนัย
ผู้ที่นิยมนิยามของจำนวนธรรมชาติซึ่งเริ่มจาก 0 จะใช้จำนวนนี้ในกรณีฐาน ผู้ที่นิยมนิยามของจำนวนธรรมชาติซึ่งเริ่มจาก 1 จะใช้จำนวนนี้แทน
การอุปนัยเชิงคณิตศาสตร์สามารถนำมาใช้เพื่อพิสูจน์ข้อความ P(n) ดังต่อไปนี้สำหรับจำนวนธรรมชาติ n ทุกจำนวนได้
นี่เป็นสูตรทั่วไปสำหรับผลบวกของจำนวนธรรมชาติที่น้อยกว่าหรือเท่ากับจำนวนที่กำหนด ซึ่งเป็นอนุกรมของข้อความจำนวนมากเป็นอนันต์โดยพฤตินัย: , , , ฯลฯ
ประพจน์ สำหรับจำนวน ใด ๆ,
การพิสูจน์ ให้ P(n) เป็นข้อความ และเราพิสูจน์โดยการอุปนัยกับ n
กรณีฐาน: แสกงให้เห็นว่าข้อความนี้เป็นจริงกับจำนวนธรรมชาติที่น้อยทีสุด n = 0.
P(0) เป็นจริงอย่างชัดเจน:
ขั้นตอนอุปนัย: แสดงให้เห็นว่าสำหรับค่า k ≥ 0 ใด ๆ หาก P(k) เป็นจริงแล้ว P(k+1) จะเป็นจริงด้วย
สมมุติสมมติฐานอุปนัยว่าสำหรับค่า k ค่าหนึ่ง กรณีที่ n = k เป็นจริง หมายความว่า P(k) เป็นจริงด้วย:
ดังนั้น:
ฝั่งขวาสามารถทำให้ง่ายด้วยวิธีการทางพีชคณิตเป็น:
จับฝั่งซ้ายและฝั่งขวาเข้าสมการ เรานิรนัยได้ว่า:
นั่นคือข้อความว่า P(k+1) เป็นจริงด้วย เป็นการแสดงขั้นตอนอุปนัย
ข้อสรุป: เนื่องจากทั้งกรณีฐานและขั้นตอนอุปนัยถูกพิสูจน์แล้วว่าเป็นจริง ข้อความ P(n) จึงเป็นจริงสำหรับจำนวนธรรมชาติ n ทุกจำนวนด้วยการอุปนัยเชิงคณิตศาสตร์ ∎
อสมการมักถูกพิสูจน์ด้วยการอุปนัย เราจะพิสูจน์ว่า สำหรับจำนวนจริง และจำนวนธรรมชาติ ใด ๆ
แวบแรกที่มอง รูปแบบของสมการที่ทั่วไปกว่า สำหรับจำนวนจริง ใด ๆ อาจดูเหมือนว่าสามารถพิสูจน์ได้โดยไม่ต้องอุปนัย แต่กรณีที่ แสดงให้เห็นว่าข้อความนี้สามารถเป็นเท็จได้สำหรับค่า ที่ไม่ใช่จำนวนเต็ม ทำให้เราต้องพิจารณาข้อความสำหรับจำนวน ที่เป็นจำนวนธรรมชาติโดยเฉพาะและการอุปนัยเป็นเครื่องมือที่พร้อมนำมาใช้ที่สุด
ประพจน์. สำหรับค่า ใด ๆ, .
การพิสูจน์ กำหนดจำนวนจริง ค่าใด ๆ ค่าหนึ่ง, และให้ เป็นข้อความ . และเราพิสูจน์โดยการอุปนัยกับ .
กรณีฐาน: การคำนวณ พิสูจน์ว่า เป็นจริง.
ขั้นตอนอุปนัย: เราจะแสดงว่า สำหรับจำนวนธรรมชาติ ใด ๆ. สมมุติสมมติฐานอุปนัยว่าสำหรับค่า กรณีของ จะเป็นจริง เรานิรนัยโดยใช้สูตรผลบวกของมุมและอสมการอิงรูปสามเหลี่ยมได้:
อสมการระหว่างฝั่งซ้ายและฝั่งขวาแสดงให้เห็นว่า เป็นจริง ขั้นตอนอุปนัยจึงเสร็จสมบูรณ์
ข้อสรุป: ประพจน์ เป็นจริงสำหรับเลขจำนวนธรรมชาติ ทุกค่า ∎
ในทางปฏิบัติ การพิสูจน์โดยการอุปนัยมักมีแบบแผนที่ต่างกันซึ่งขึ้นอยู่กับลักษณะของคุณสมบัติที่เราต้องการจะพิสูจน์ รูปแปรผันของการอุปนัยทุกรูปแบบเป็นกรณีพิเศษของการอุปนัยเชิงอนันต์ ดูด้านล่าง
หากเราไม่ประสงค์จะพิสูจน์ข้อความหนึ่งสำหรับจำนวนธรรมชาติทุกจำนวน แต่ต้องการพิสูจน์เพียงสำหรับจำนวน n ทุกจำนวนที่มีค่ามากกว่าหรือเท่ากับค่า b เท่านั้นแล้ว การพิสูจน์ด้วยการอุปนัยจะประกอบด้วย:
เราสามารถนำวิธีนี้มาใช้เพื่อแสดงให้เห็นว่า สำหรับ
เราสามารถพิสูจน์ได้ว่าข้อความ ข้อความหนึ่งเป็นจริงสำหรับค่า หรือแม้แต่สำหรับค่า การอุปนัยเชิงคณิตศาสตร์รูปแบบนี้ความจริงแล้วเป็นกรณีพิเศษของรูปแบบก่อนหน้าเพราะหากข้อความที่ถูกพิสูจน์คือ แล้ว การพิสูจน์ด้วยกฎสองข้อนี้ก็เท่ากับการพิสูจน์ข้อความ สำหรับจำนวนธรรมชาติ ทุกจำนวนโดยมีกรณีฐานอุปนัยกับค่า [17]
สมมติว่าเรามีเหรียญสี่บาทและเหรียญห้าบาทจำนวนไม่จำกัด เราสามารถใช้การอุปนัยเพื่อพิสูจน์ได้ว่าจำนวนเต็มของเงินบาทใด ๆ ที่มากกว่าหรือเท่ากับ สามารถใช้เหรียญสี่บาทและห้าบาทมารวมกันได้จำนวนนั้น ให้ เป็นข้อความว่า "จำนวนเงิน บาทสามารถรวมมาจากเหรียญสี่บาทและเหรียญห้าบาท" การพิสูจน์ว่า เป็นจริงสำหรับค่า ทุกค่าสามารถทำได้ด้วยการอุปนัยกับ ดังนี้:
กรณีฐาน: การแสดงให้เห็นว่า เป็นจริงสำหรับ ง่ายมาก เพียงแค่มีเหรียญสี่บาทสามเหรียญ
ขั้นตอนอุปนัย: กำหนดให้ เป็นจริงสำหรับค่า ค่าหนึ่ง (สมมติฐานอุปนัย) พิสูจน์ว่า เป็นจริงด้วย:
เพราะฉะนั้น เป็นจริงสำหรับค่า ทุกค่าด้วยหลักของการอุปนัย และการพิสูจน์จึงสมบูรณ์
แม้ จะเป็นจริงสำหรับค่า ในตัวอย่างนี้ด้วย เราไม่สามารถดัดแปลงค่าต่ำสุด ให้น้อยไปกว่านี้ได้อีกเป็นค่า ในการพิสูจน์ข้างบน สำหรับ กรณีฐานเป็นเท็จ สำหรับ กรณีที่สองในขั้นตอนอุปนัยจะใช้ไม่ได้ (การแทนเหรียญห้าบาทเป็นเหรียญสี่บาททำไม่ได้) ส่วนสำหรับค่า ที่น้อยกว่านี้ก็ไม่จำเป็นต้องเอ่ยถึงเลย
บางครั้งก็เป็นการดีกว่าที่จะใช้จำนวนธรรมชาติสองจำนวน 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 ทุกจำนวน
รูปแบบของการพิสูจน์โดยการอุปนัยเชิงคณิตศาสตร์ที่พบได้ทั่วไปที่สุดมีความจำเป็นให้พิสูจน์ในขั้นตอนอุปนัยว่า
ซึ่งต่อจากนั้นหลักการอุปนัยจะ "ทำโดยอัตโนมัติ" (automate) การใช้ขั้นตอนนี้จำนวน n ครั้งเพื่อไปจาก P(0) สู่ P(n) นี่เรียกได้ว่าเป็น "การอุปนัยตัวนำหน้า" เพราะในแต่ละขั้นตอนก็เป็นการพิสูจน์บางสิ่งเกี่ยวกับเลขตัวหนึ่งจากบางสิ่งที่เกี่ยวกับเลขที่นำหน้าเลขตัวนั้น
สิ่งหนึ่งซึ่งได้รับความสนใจในเรื่องความซับซ้อนในการคำนวณคือ "การอุปนัยตัวเติมหน้า" (อังกฤษ: prefix induction) ซึ่งเป็นการพิสูจน์ข้อความดังต่อไปนี้ในขั้นตอนอุปนัย
หรือซึ่งสมมูลกัน
แล้วหลักการอุปนัยจึง "ทำโดยอัตโนมัติ" การใช้การอนุมานนี้จำนวน 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) ในการอุปนัยอย่างเข้มก่อนที่การอ้างเหตุผลแบบทั่วไปจะใช้ได้ อย่างเช่นตัวอย่างของจำนวนฟีโบนัชชี Fn ด้านล่าง
แม้รูปแบบที่เพิ่งอธิบายไปให้ต้องพิสูจน์กรณีฐาน เราไม่จำเป็นต้องพิสูจน์หากสามารถพิสูจน์ 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) เท่านั้น
การอุปนัยอย่างเข้มมีประโยชน์สูงสุกเมื่อต้องใช้สมมติฐานอุปนัยหลาย ๆ รอบต่อขั้นตอนอุปนัยขั้นคอนหนึ่ง เช่นเราสามารถการอุปนัยอย่างเข้มเพื่อแสดงให้เห็นว่า
ซึ่ง เป็นจำนวนฟีโบนัชชีจำนวนที่ n, (อัตราส่วนทอง) และ เป็นรากของพหูพจน์ เอกลักษณ์ด้านบนสามารถถูกพิสูจน์ยืนยันด้วยการคำนวณ โดยตรงหากเราสมมุติว่า and เป็นจริงอยู่แล้วด้วยการใช้ข้อเท็จจริงว่า สำหรับ แต่ละตัว เพื่อให้การพิสูจน์เสร็จสมบูรณ์ เอกลักษณ์จะต้องถูกพิสูจน์ยืนยันในกรณีฐานทั้งสองกรณี: และ
การพิสูจน์ด้วยการอุปนัยอย่างเข้มอีกอันหนึ่งใช้สมมติฐานว่าข้อความเป็นจริงสำหรับจำนวน ทุกค่าที่น้อยกว่าอย่างถี่ถ้วนกว่า พิจารณาข้อความที่ว่า "จำนวนธรรมชาติทุกจำนวนซึ่งมากกว่า 1 เป็นผลคูณของจำนวนเฉพาะ (หนึ่งจำนวนหรือมากกว่า)" ซึ่งเป็นส่วน "การมีจริง" (existence) ของทฤษฎีบทมูลฐานของเลขคณิต สำหรับการพิสูจน์ขั้นตอนอุปนัยสมมติฐานอุปนัยคือสำหรับค่า ซึ่งกำหนดมาข้อความจะเป็นจริงสำหรับค่า ซึ่งน้อยกว่าทุกค่า หาก เป็นจำนวนเฉพาะแล้วมันเป็นผลคูณของจำนวนเฉพาะอย่างแน่นอน และหากไม่ใช่แล้วก็จะเป็นผลคูณ โดยนิยามโดยตัวประกอบทั้งสองไม่เท่ากับ 1 ดังนั้นทั้งสองจึงไม่เท่ากับ เพราะฉะนั้นทั้งสองจึงมากกว่าหนึ่งและน้อยกว่า สมมติฐานอุปนัยตอนนี้ใช้ได้กับ และ ดังนั้นทั้งสองแต่ละตัวเป็นผลคูณของจำนวนเฉพาะ ฉะนั้น เป็นผลคูณของผลคูณของจำนวนเฉพาะและจึงเป็นผลคูณของจำนวนเฉพาะเองโดยการขยาย
เราสมควรที่จะดูการพิสูจน์ตัวอย่างเดียวกับด้านบนครั้งนี้ด้วย การอุปนัยอย่างเข้ม ข้อความยังคงเดิม:
แต่ทว่าโครงสร้างและสมมติฐานของการพิสูจน์จะมีความแตกต่างเล็กน้อย เริ่มจากกรณีฐานแบบขยาย:
กรณีฐาน: แสดงให้เห็นว่า เป็นจริงสำหรับค่า .
กรณีฐานเป็นจริง
สมมติฐานอุปนัย: กำหนดจำนวน ค่าหนึ่ง สมมติว่า เป็นจริงสำหรับค่า ทุกค่าโดย .
ขั้นตอนอุปนัย: พิสูจน์ว่า เป็นจริง
การเลือกค่า และสังเกตว่า แสดงให้เห็นว่า เป็นจริงโดยสมมติฐานอุปนัย นั่นคือผลบวก สามารถถูกสร้างขึ้นมาด้วยส่วนผสมของเหรียญ และ บาท แล้วดังนั้นเพียงแค่เพิ่มเหรียญ บาทลงไปในกองเหรียญนั้นแล้วก็จะให้ผลเป็นผลบวก นั่นก็คือ เป็นจริง ∎
บางครั้งการนิรนัยถอยหลังคือการพิสูจน์ข้อความสำหรับ เมื่อพิจารณาความสมเหตุสมผลของมันสำหรับ จะสะดวกกว่า อย่างไรก็ตามการไม่พิสูจน์ความสมเหตุสมผลของข้อความสำหรับเลขตัวใดเพียงพอเพื่อสร้างกรณีฐาน เราต้องพิสูจน์ข้อความสำหรับเซตย่อยของจำนวนธรรมชาติไม่มีสิ้นสุดแทน เช่น โอกุสแต็ง-หลุยส์ โกชี (Augustin Louis Cauchy) ใช้การอุปนัยคืบหน้า (ปรกติ) เพื่อพิสูจน์อสมการมัชฌิมเลขคณิต-เรขาคณิต (inequality of arithmetic and geometric means) สำหรับกำลังของ 2 ทุกค่า แล้วใช้การอุปนัยถอยหลังเพื่อแสดงให้เห็นว่าเป็นจริงสำหรับจำนวนธรรมชาติทุกจำนวนด้วย [19][20]
ขั้นตอนอุปนัยจะต้องถูกพิสูจน์สำหรับ n ทุกค่า เพื่อแสดงสิ่งนี้ให้เห็น โจเอล อี. โคเฮน ได้นำเสนอการอ้างเหตุผลว่าสามารถพิสูจน์ว่าม้าทุกตัวมีสีเดียวกัน (All horses are the same color) ได้ด้วยการอุปนัยเชิงคณิตศาสตร์ได้ดังต่อไปนี้:[21]
กรณีฐาน เป็นเรื่องธรรมดา (เพราะไม่ว่าม้าตัวไหนก็จะมีสีเดียวกับตัวมันเอง) และขั้นตอนอุปนัยถูกต้องในกรณีที่ ทุกกรณี แต่ทว่าตรรกะของขั้นตอนอุปนัยสำหรับค่า ไม่ถูกต้องเพราะข้อความที่ว่า "ทั้งสองเซตเหลื่อมกัน" เป็นเท็จ (มีม้าเพียง ตัวทั้งก่อนและหลังการเอาม้าตัวหนึ่งออกจากเซต เซตของม้าตัวเดียวจึงไม่เหลื่อมกัน)
เราสามารถเขียน "สัจพจน์ของการอุปนัย" ในตรรกะอันดับสอง (second-order logic) ได้ดังนี้:
ซึ่ง 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) พูดถึงประเด็นนี้เพิ่มเติม
สัจพจน์ของการอุปนัยเชิงโครงสร้างสำหรับจำนวนธรรมชาติถูกกำหนดรูปเป็นครั้งแรกโดยเปอาโนผู้ซึ่งใช้มันเพื่อระบุจำนวนธรรมชาติเข้าด้วยกันด้วยสัจพจน์อื่นสี่ข้อดังต่อไปนี้:
การบ่งปริมาณกับภาคแสดงทำไม่ได้ในทฤษฎีเซตแซร์เมโล-เฟรนเคิลอันดับหนึ่ง (Zermelo-Fraenkel set theory) แต่เรายังสามารถแสดงการอุปนัยด้วยการบ่งปริมาณกับเซต:
เราสามารถอ่าน เป็นเซตซึ่งแทนประพจน์และมีจำนวนธรรมชาติสำหรับที่ประพจน์เป็นจริง นี่ไม่ใช่สัจพจน์แต่เป็นทฤษฎีบทคล้ายกับของเปอาโน โดยกำหนดว่าจำนวนธรรมชาติถูกนิยามในภาษาของทฤษฎีเซต ZFC ด้วยสัจพจน์
(อังกฤษ: Transfinite induction) เราสามารถนำหลักการของการอุปนัยอย่างเข้มมาใช้กับข้อความเกี่ยวกับสมาชิกของเซตรากฐานดี (Well-founded set) เซตใด ๆ ได้ด้วยนอกเหนือจากข้อความเกี่ยวกับจำนวนธรรมชาติเท่านั้น นั่นคือเซตซึ่งมีความสัมพันธ์ไม่สะท้อน (irreflexive relation) ซึ่งไม่มีเซตอันดับทุกส่วนลดหลั่นอนันต์ (infinite descending chain) เซตของจำนวนเชิงการนับเซตใด ๆ เป็นเซตรากฐานดีซึ่งรวมไปถึงเซตของจำนวนธรรมชาติ เมื่อนำไปประยุกต์กับเซตรากฐานดีก็สามารถกำหนดรูปใหม่เป็นขั้นตอนเดียวได้ว่า:
เมื่อนำการอุปนัยรูปนี้ไปประยุกต์ใช้กับเซตของจำนวนเชิงอันดับที่แล้ว (ซึ่งทำให้เกิดคลาสอันดับดี (well-order) และจึงเป็นคลาสรากฐานดี) ก็จะเรียกว่าการอุปนัยเชิงอนันต์ นี่เป็นเทคนิคการพิสูจน์ที่สำคัญในทฤษฎีเซต ทอพอโลยีและสาขาวิชาอื่น ๆ
การพิสูจน์โดยการอุปนัยเชิงอนันต์โดยปกติแล้วจะจำแนกกรณีเป็นสามกรณี:
หากพูดให้ชัดเจน มันไม่จำเป็นที่จะต้องพิสูจน์กรณีฐานในการอุปนัยเชิงอนันต์เพราะมันเป็นกรณีพิเศษว่างเปล่า (Vacuous truth) ของประพจน์ว่าหาก P เป็นจริงสำหรับค่า n < m ทุกค่าแล้ว P จะเป็นจริงสำหรับ m มันเป็นจริงอย่างว่างเปล่าก็เป็นเพราะว่าไม่มีค่า n < m ค่าใดซึ่งสามารถทำหน้าที่เป็นตัวอย่างขัดแย้งได้
หลักการอุปนัยเชิงคณิตศาสตร์มักถูกกล่าวว่าเป็นสัจพจน์ข้อหนึ่งของจำนวนธรรมชาติ (ดูที่สัจพจน์เปอาโน) หลักการนี้แรงกว่าหลักการจัดอันดับดี (Well-ordering principle) ในบริบทของสัจพจน์เปอาโนอื่น ๆ สมมุติสิ่งต่าง ๆ ดังต่อไปนี้:
จากนั้นก็จะสามารถพิสูจน์ด้วยสัจพจน์ที่ทำรายการไว้ด้านบนได้ว่าการอุปนัยบอกเป็นนัยถึงหลักการจัดอันดับดี การพิสูจน์ดังต่อไปนี้ใช้การอุปนัยอย่างเข้มและสัจพจน์ข้อที่หนึ่งและสี่
การพิสูจน์ สมมติว่ามีเซตของจำนวนธรรมชาติที่ไม่มีสมาชิกเล็กสุด 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∈ℕ} ซึ่งแสดงอยู่ในรูปมีอันดับดี[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] หลักการจัดอันดับดีบอกเป็นนัยสัจพจน์อุปนัยในบริบทของสัจพจน์ซึ่งเรียงลำดับไว้ด้านบนสองข้อแรกและ
ข้อผิดพลาดซึ่งพบได้บ่อยในการพิสูจน์ซึ่งเข้าใจผิดคือการสมมติว่า n − 1 เป็นจำนวนธรรมชาติที่เป็นได้อย่างเดียวและถูกนิยามไว้อย่างดีซึ่งเป็นคุณสมบัติที่สัจพจน์เปอาโนข้ออื่น ๆ ไม่ได้บอกเป็นนัย[22]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.