ผู้ใช้:Thastp/การอุปนัยเชิงคณิตศาสตร์
From Wikipedia, the free encyclopedia
การอุปนัยเชิงคณิตศาสตร์ (อังกฤษ: Mathematical induction) เป็นเทคนิคการพิสูจน์เชิงคณิตศาสตร์ที่ใช้เพื่อพิสูจน์ว่าข้อความ P(n) เป็นจริงสำหรับจำนวนธรรมชาติทุกจำนวน n = 0, 1, 2, 3, . . . ; แปลว่าข้อความทั้งสิ้นเป็นลำดับของกรณี P(0), P(1), P(2), P(3), . . . . จำนวนมากไม่สิ้นสุด เราสามารถใช้คำอุปมาเพื่ออธิบายเทคนิคนี้ได้อย่างอรูปนัยด้วยการเทียบกับโดมิโนที่ล้มตาม ๆ กันหรือการปีนบันได:
"การอุปนัยเชิงคณิตศาสตร์พิสูจน์ว่าเราสามารถปีนบันไดสูงเท่าไหร่ก็ได้ พิสูจน์โดยการปีนขึ้นขั้นแรก (ฐานของบันได) และจากนั้นก็สามารถปีนขึ้นขั้นต่อไปจากขั้นไหนก็ได้"[lower-alpha 1]
— Concrete Mathematics, ริมกระดาษหน้า 3
![ภาพของโดมิโนซึ่งตั้งเรียงต่อกัน เมื่อโดมิโนตัวหนึ่งถูกผลักล้มตัวอื่น ๆ จะล้มตามมา นี่ถูกนำมาเปรียบเทียบกับกระบวนการอุปนัยเชิงคณิตศาสตร์](http://upload.wikimedia.org/wikipedia/commons/thumb/9/92/Dominoeffect.png/640px-Dominoeffect.png)
การพิสูจน์ด้วยการอุปนัย (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]