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

วิธีอุปนัยเชิงคณิตศาสตร์(Mathematical Induction)

ข้อความในทางคณิตศาสตร์จะมีข้อความที่เกี่ยวกับจำนวนเต็มบวกหลายข้อความ ซึ่งสามารถ
ที่จะพิสูจน์ข้อความเหล่านี้ว่าเป็นจริงโดยใช้วิธีการพิสูจน์ที่เรียกว่าวิธีอุปนัยเชิงคณิตศาสตร์และก่อนที่จะกล่าวถึงวิธีการพิสูจน์แบบนี้จะขอกล่าวถึงคุณสมบัติที่สำคัญของจำนวนเต็มบวกที่จะนำมาใช้ก่อน
1.1 หลักการลำดับอย่างดี (Well-OrderingPrinciple) กล่าวว่า “สำหรับทุก ๆเซตย่อยของจำนวนเต็มบวก
N ที่ไม่เป็นเซตว่างจะมีจำนวนที่มีค่าน้อยที่สุดอยู่หนึ่งตัวเสมอ”
ตัวอย่าง กำหนดให้ A ={2,7,8,11} จะได้ว่า AÌ N และ Aมีสมาชิกที่มีค่าน้อยที่สุด คือ 2

ทฤษฎีบท
1.1.1 กำหนดให้ N เป็นเซตของจำนวนเต็มบวก ถ้าS เป็นเซตที่ S Ì N และมีคุณสมบัติ
ดังต่อไปนี้
1. 1Î S
และ 2. สำหรับจำนวนเต็มบวกk ใด ๆ ถ้า k ÎS แล้วk + 1 ÎS จะได้ว่า S = N
พิสูจน์ สมมติว่า S ¹ N ดังนั้น จะมีจำนวนเต็มบวกอย่างน้อยหนึ่งตัวที่ไม่เป็นสมาชิกของS
ให้ U = { x çx ÎN แต่ x ÏS} จะได้ว่า U Ì N และU Ç S = f
เนื่องจาก
U ¹ f ดังนั้นจากหลักการลำดับอย่างดีจะได้ว่า U จะมีสมาชิกที่มีค่าน้อยที่สุด สมมติว่าเป็นm
นั่นคือ
ถ้า x Î U แล้ว m £ x เนื่องจาก m Î U จะได้ว่า m ÎS และโดยคุณสมบัติ ข้อ 1 จะได้ว่า m ¹ 1
ดังนั้น
m > 1 จะได้ว่า m – 1 > 0 และ m - 1 เป็นจำนวนเต็มบวก เนื่องจาก m เป็นสมาชิกของU ที่มีค่าน้อยที่สุดจะได้ว่า m - 1 เป็นจำนวนเต็มบวกที่ไม่เป็นสมาชิกของ U และ m – 1 < m ดังนั้น m – 1 Î S ให้ k = m – 1 จะได้ว่า k + 1 = m และโดยคุณสมบัติข้อ 2 จะได้ว่า m ÎS จะเห็นว่าm ÏS และ m ÎS ซึ่งเป็นไปไม่ได้
ดังนั้นS=N

ทฤษฎีบท
1.1.2 (หลักการอุปนัยเชิงคณิตศาสตร์ :Principle of Mathematical Induction)
ให้ P(n) แทนข้อความที่เกี่ยวกับจำนวนเต็มบวก n และมีคุณสมบัติดังต่อไปนี้
1. P(1) เป็นจริง
และ 2. สำหรับจำนวนเต็มบวก k ใด ๆ ถ้า P(k) เป็นจริงแล้ว P(k+1) เป็นจริงด้วย
จะได้ว่า P(n) เป็นจริงสำหรับทุก ๆ จำนวนเต็มบวก n

พิสูจน์ ให้ S = {m çP(m) เป็นจริง } จากที่กำหนดให้
จะได้ว่า 1. 1 Î S
และ 2. สำหรับจำนวนเต็มบวก k ใด ๆ ถ้า k Î S แล้ว k + 1 Î S
ดังนั้น โดยทฤษฎีบท 1.1.1
จะได้ว่า S = N
นั่นคือ P(n) เป็นจริงสำหรับทุก ๆ จำนวนเต็มบวก n

ทฤษฎีบท
1.1.3 (หลักอุปนัยเชิงคณิตศาสตร์) ให้ P(n) แทนข้อความที่เกี่ยวกับจำนวนเต็มn
³ n0 เมื่อ n0 เป็นจำนวนเต็ม และมีคุณสมบัติดังต่อไปนี้
1. P(n0) เป็นจริง
และ 2. สำหรับจำนวนเต็ม k> n0 ถ้า P(k) เป็นจริง แล้ว P(k+1) เป็นจริงด้วย
จะได้ว่า P(n) เป็นจริงสำหรับทุก ๆ จำนวนเต็ม n ³ n0
ที่มา:http://th.tni.wikia.com/wiki/