การพิสูจน์โดยขัดแย้ง — วิธีทำและตัวอย่างคลาสสิก

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

วิธีนี้มีประโยชน์เมื่อปฏิเสธของข้อความให้สิ่งที่จับต้องได้สำหรับนำมาคิดต่อ ตัวอย่างคลาสสิกคือการพิสูจน์ว่า $\sqrt{2}$ เป็นจำนวนอตรรกยะ: เมื่อสมมติว่ามันเป็นจำนวนตรรกยะ เราจะเขียนมันในรูปเศษส่วนและตามผลที่ตามมาได้

การพิสูจน์โดยขัดแย้งทำงานอย่างไร

สมมติว่าข้อความที่คุณต้องการพิสูจน์คือ $P$

ในการพิสูจน์แบบขัดแย้ง คุณเริ่มจากสมมติว่า $P$ เป็นเท็จ จากนั้นให้เหตุผลต่อจากสมมตินั้นไปเรื่อย ๆ จนได้ข้อขัดแย้ง เช่น

$$1 = 0$$

หรือขัดกับนิยามที่ทราบอยู่แล้ว หรือได้ข้อความที่ไม่สามารถเป็นจริงพร้อมกับขั้นตอนก่อนหน้าได้

เมื่อถึงจุดนั้น ปฏิเสธของ $P$ ย่อมไม่ถูกต้อง ดังนั้น $P$ จึงต้องเป็นจริง

เงื่อนไขสำคัญคือ ข้อขัดแย้งต้องเกิดจากการให้เหตุผลที่ถูกต้องและข้อเท็จจริงที่ยอมรับกัน ผลลัพธ์ที่แค่ดูแปลกยังไม่เพียงพอ มันต้องเป็นสิ่งที่เป็นไปไม่ได้ภายใต้นิยามหรือทฤษฎีบทที่คุณใช้อยู่

ควรใช้การพิสูจน์โดยขัดแย้งเมื่อไร

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

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

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

ตัวอย่างที่ทำครบ: ทำไม $\sqrt{2}$ จึงเป็นอตรรกยะ

การพิสูจน์แบบขัดแย้งที่เป็นคลาสสิกแสดงว่า $\sqrt{2}$ เป็นจำนวนอตรรกยะ

เริ่มจากสมมติสิ่งตรงข้าม:

$$\sqrt{2} \text{ is rational.}$$

ถ้าเป็นจริง $\sqrt{2}$ จะเขียนได้เป็น

$$\sqrt{2} = \frac{a}{b}$$

โดยที่ $a$ และ $b$ เป็นจำนวนเต็ม, $b \neq 0$ และเศษส่วนนี้อยู่ในรูปอย่างต่ำแล้ว

ตอนนี้ยกกำลังสองทั้งสองข้าง:

$$2 = \frac{a^2}{b^2}$$

ดังนั้น

$$a^2 = 2b^2.$$

สิ่งนี้บอกเราว่า $a^2$ เป็นจำนวนคู่ และนั่นบังคับให้ $a$ เป็นจำนวนคู่ด้วย เพราะกำลังสองของจำนวนเต็มคี่จะเป็นคี่ ดังนั้นเขียนได้ว่า

$$a = 2k$$

สำหรับจำนวนเต็มบางตัว $k$

แทนค่านี้ลงใน $a^2 = 2b^2$:

$$(2k)^2 = 2b^2$$ $$4k^2 = 2b^2$$ $$2k^2 = b^2.$$

ตอนนี้ $b^2$ เป็นจำนวนคู่ ดังนั้น $b$ ก็เป็นจำนวนคู่เช่นกัน

แต่ตอนนี้ทั้ง $a$ และ $b$ เป็นจำนวนคู่ นั่นหมายความว่าทั้งคู่หารด้วย $2$ ลงตัว ซึ่งขัดกับสมมติฐานที่ว่า $\frac{a}{b}$ อยู่ในรูปอย่างต่ำแล้ว

ดังนั้นสมมติฐานตั้งต้นจึงเป็นเท็จ เพราะฉะนั้น $\sqrt{2}$ เป็นจำนวนอตรรกยะ

ทำไมข้อขัดแย้งนี้จึงชี้ขาดได้

ข้อขัดแย้งนี้ไม่ใช่แค่ “รู้สึกว่ามีอะไรผิด” แต่มันชัดเจนมาก:

1. สมมติฐานบอกว่า $\sqrt{2} = \frac{a}{b}$ และอยู่ในรูปอย่างต่ำ
2. การคำนวณทางพีชคณิตแสดงว่า $a$ และ $b$ ต้องเป็นจำนวนคู่ทั้งคู่
3. เศษส่วนไม่สามารถอยู่ในรูปอย่างต่ำ และในขณะเดียวกันมีทั้งเศษและส่วนหารด้วย $2$ ลงตัวได้

การปะทะกันตรง ๆ นี้เองคือข้อขัดแย้ง

ข้อผิดพลาดที่พบบ่อยในการพิสูจน์โดยขัดแย้ง

ข้อผิดพลาดที่พบบ่อยอย่างหนึ่งคือสมมติสิ่งตรงข้ามอย่างคลุมเครือ คุณต้องใช้ปฏิเสธที่แท้จริงของข้อความ ไม่ใช่ข้อความใกล้เคียงที่ฟังดูคล้ายกัน

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

ข้อผิดพลาดข้อที่สามคือไม่ระบุให้ชัดว่ากำลังขัดกับข้อเท็จจริงใด การพิสูจน์ที่ดีจะบอกความขัดแย้งอย่างชัดเจน เช่น กฎเรื่องคู่คี่ นิยาม เงื่อนไขความน้อยที่สุด หรือทฤษฎีบทที่พิสูจน์ไว้ก่อนแล้ว

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

แม่แบบง่าย ๆ ของการพิสูจน์โดยขัดแย้ง

สำหรับการพิสูจน์ระดับเริ่มต้นหลายแบบ โครงสร้างมักเป็นดังนี้:

1. สมมติว่าข้อความเป็นเท็จ
2. แปลงสมมตินั้นให้อยู่ในรูปที่เป็นรูปธรรม
3. ไล่ผลที่ตามมาทีละขั้น
4. ไปถึงข้อขัดแย้งกับข้อเท็จจริงที่ทราบอยู่แล้ว
5. สรุปว่าข้อความเดิมเป็นจริง

ถ้าขั้นที่ 2 อ่อน การพิสูจน์ก็มักจะยังคลุมเครือ การพิสูจน์โดยขัดแย้งที่แข็งแรงที่สุดมักเกิดจากการเปลี่ยนปฏิเสธให้เป็นสิ่งที่เป็นรูปธรรมมาก

ลองทำการพิสูจน์แบบขัดแย้งที่คล้ายกัน

ลองพิจารณาข้อความว่า “ไม่มีจำนวนตรรกยะบวกที่น้อยที่สุด” สมมติว่ามีอยู่ตัวหนึ่ง เรียกมันว่า $r$ แล้วถามว่าจะเกิดอะไรขึ้นกับ $\frac{r}{2}$ หากคุณต้องการตรวจสอบเหตุผลของตัวเองทีละขั้นในโจทย์คล้ายกัน ลองเขียนวิธีของคุณเองใน GPAI Solver แล้วเปรียบเทียบแต่ละข้อความกับข้อขัดแย้งที่คุณกำลังมุ่งไปหา