การพิสูจน์โดยข้อขัดแย้ง
การพิสูจน์โดยข้อขัดแย้งเป็นเทคนิคการพิสูจน์ที่นิยมใช้ ถ้าต้องการพิสูจน์ว่าประพจน์หนึ่งเป็นจริง ให้หานิเสธของประพจน์นั้น สมมติว่านิเสธเป็นจริง แล้วพยายามหาข้อขัดแย้ง เป้าหมายคือแสดงว่าข้อสมมติที่เลือกนำไปสู่สิ่งที่เป็นไปไม่ได้
ตัวอย่างที่ชัดเจน
ให้ข้อความ “ไม่มีจำนวนตรรกยะบวกที่น้อยที่สุด” พิสูจน์ข้อความนี้โดยข้อขัดแย้ง โดยเริ่มจากหานิเสธของข้อความก่อน: “มีจำนวนตรรกยะบวกที่น้อยที่สุด” ให้จำนวนนี้เป็น q ถ้า q เป็นจำนวนตรรกยะบวกที่น้อยที่สุด เราจะหาจำนวนตรรกยะบวกที่น้อยกว่านี้ไม่ได้ เพราะถ้าหาได้ q ก็ไม่ใช่จำนวนที่น้อยที่สุด
ใช้ข้อนี้หาข้อขัดแย้ง ถ้าหาจำนวนที่น้อยกว่า q ได้ (จะเลือกจำนวนนั้นอย่างไรก็ได้) ก็จะเกิดข้อขัดแย้ง และนิเสธของข้อความเป็นเท็จ ถ้าเลือกจำนวนที่น้อยที่สุดเป็น เช่น 0.1 จะเห็นว่า 0.01 น้อยกว่า 0.1 ส่วน 0.001 น้อยกว่านั้นอีก และ 0.0001 ก็น้อยกว่าอีก และเป็นอย่างนี้ไปเรื่อย ๆ เพียงนำ q หารด้วยสิบก็ได้จำนวนที่น้อยกว่า ที่จริงหารด้วยจำนวนใดก็ได้ที่มากกว่าหนึ่ง เช่น สอง ครึ่งหนึ่งของ q ย่อมน้อยกว่า q แน่นอน
ดังนั้น q/2 น้อยกว่า q แน่นอน และเป็นจำนวนตรรกยะบวกด้วย จึงเกิดข้อขัดแย้งกับนิเสธของข้อความ นิเสธของข้อความจึงเป็นเท็จ และข้อความเดิมเป็นจริง
จำนวนที่น่าสนใจ
ตัวอย่างขำ ๆ แบบคลาสสิกที่แสดงหลักการของข้อขัดแย้งเป็นดังนี้ สมมติว่ามีจำนวนนับบางจำนวนที่น่าสนใจในแง่ใดแง่หนึ่ง เช่น 2 น่าสนใจ เพราะ 2 × 2 = 2 + 2 ซึ่งเป็นสมบัติที่ไม่ค่อยพบ 1729 น่าสนใจ เพราะเป็นจำนวนนับที่น้อยที่สุดที่เขียนเป็นผลบวกของกำลังสามของจำนวนนับสองจำนวนได้สองแบบ (1729 = 1³ + 12³ = 9³ + 10³) และอื่น ๆ คำถามคือ จำนวนที่น่าสนใจมีมากมายไม่สิ้นสุดหรือไม่
สมมติตรงกันข้าม คือจำนวนที่น่าสนใจมีจำนวนจำกัด และมีบางจำนวนที่ไม่น่าสนใจ นำจำนวนนับที่ไม่น่าสนใจเหล่านี้มารวมเป็นเซตของจำนวนที่ไม่น่าสนใจ แล้วเลือกจำนวนที่ไม่น่าสนใจที่น้อยที่สุด เดี๋ยวก่อน จำนวนที่ไม่น่าสนใจที่น้อยที่สุดหรือ ฟังดูน่าสนใจดีไม่ใช่หรือ :-)
จึงเกิดข้อขัดแย้ง เพราะจำนวนที่ไม่น่าสนใจที่น้อยที่สุดที่จริงก็น่าสนใจพอสมควร จึงไม่มีจำนวนที่ไม่น่าสนใจที่น้อยที่สุด ดังนั้นเซตของจำนวนที่ไม่น่าสนใจต้องเป็นเซตว่าง
แน่นอนว่านี่เป็นเรื่องไร้สาระ เพราะเราไม่ได้นิยามให้ชัดว่าจำนวนที่น่าสนใจคืออะไร แต่วิธีพิสูจน์นั้นถูกต้อง
การพิสูจน์ว่าจำนวนเฉพาะมีมากมายไม่สิ้นสุด
ตัวอย่างนี้ใช้วิธีคล้ายกับหัวข้อก่อนหน้า แต่คราวนี้ถูกต้องทุกประการ
จำนวนเฉพาะคือจำนวนที่มีตัวประกอบที่แตกต่างกันเพียงสองตัว คือตัวมันเองและหนึ่ง สังเกตว่าหนึ่งไม่เป็นไปตามบทนิยาม แต่สองเป็นไปตามบทนิยาม
การแยกตัวประกอบเฉพาะ คือการเขียนจำนวนนับที่ไม่ใช่หนึ่งให้อยู่ในรูปผลคูณของจำนวนเฉพาะ เป็นสมบัติที่น่าสนใจของจำนวนนับ ไม่ว่าจะเลือกจำนวนนับใด (ยกเว้นหนึ่ง) ก็แยกเป็นผลคูณของจำนวนเฉพาะหลายตัว (ซึ่งอาจซ้ำกันได้) ได้เสมอ ตัวอย่าง:
ข้อความเรื่องการแยกตัวประกอบเฉพาะเรียกว่าทฤษฎีบทหลักมูลของเลขคณิต ทฤษฎีบทนี้บอกด้วยว่าการแยกตัวประกอบแบบนี้มีเพียงแบบเดียว คือจำนวนนับหนึ่งจำนวนจะแยกตัวประกอบเฉพาะได้สองแบบที่ต่างกันไม่ได้ นอกจากนี้ มีเพียงจำนวนเฉพาะเท่านั้นที่การแยกตัวประกอบเฉพาะประกอบด้วยจำนวนเพียงตัวเดียว คือตัวมันเอง เช่น การแยกตัวประกอบเฉพาะของเจ็ดคือเจ็ด เราจะใช้ข้อเท็จจริงเหล่านี้ในการพิสูจน์ข้อความต่อไปนี้
ต่อไปจะพิสูจน์ข้อความ “จำนวนเฉพาะมีมากมายไม่สิ้นสุด” หานิเสธของข้อความอีกครั้ง: “จำนวนเฉพาะมีจำนวนจำกัด” สมมติว่าลำดับของจำนวน
คือจำนวนเฉพาะทั้งหมดที่มีอยู่ ถ้าลำดับนี้มีจำนวนเฉพาะครบทุกจำนวน ย่อมหาจำนวนที่เป็นจำนวนเฉพาะแต่ไม่อยู่ในลำดับนี้ไม่ได้ จำนวนเฉพาะทุกจำนวนอยู่ในลำดับ นอกลำดับจะมีจำนวนเฉพาะอีกไม่ได้
ถ้าต้องการให้เกิดข้อขัดแย้ง ต้องสร้างจำนวนเฉพาะที่ไม่อยู่ในลำดับนี้ จำนวน q จะช่วยได้ สร้างจำนวนนี้โดยนำจำนวนเฉพาะทุกจำนวนในลำดับมาคูณกันแล้วบวกหนึ่ง:
ตอนนี้ต้องแสดงว่าจำนวนนี้เป็นจำนวนเฉพาะ หรือทำให้เกิดจำนวนเฉพาะในทางใดทางหนึ่ง เรารู้ว่า q เป็นจำนวนนับ และจำนวนนับทุกจำนวนเขียนเป็นผลคูณของจำนวนเฉพาะได้ แต่ไม่มีจำนวนเฉพาะ ai ใดหาร q ลงตัว เพราะหารแล้วเหลือเศษหนึ่งเสมอ ถ้าพยายามหาร q ด้วย เช่น จำนวนเฉพาะ a2 จะได้ดังนี้:
ก่อนอื่นแยกเศษส่วนเป็นสองเศษส่วน ในเศษส่วนแรกตัด a2 ออก จะเหลือผลคูณของจำนวนเฉพาะ ซึ่งเป็นแค่จำนวนเต็มจำนวนหนึ่งที่ไม่สำคัญ ในเศษส่วนที่สองไม่มีอะไรให้ตัด เศษส่วนนี้ไม่มีทางเป็นจำนวนเต็ม (เพราะตัวส่วนเป็นหนึ่งไม่ได้ หนึ่งไม่ใช่จำนวนเฉพาะ) ผลบวกจึงไม่เป็นจำนวนเต็ม นั่นคือจำนวนเฉพาะ a2 หาร q ไม่ลงตัว
จึงพิสูจน์ได้ว่าไม่มีจำนวนเฉพาะใดในลำดับ an ที่หาร q ลงตัว (หมายเหตุ: แม้จะแสดงไว้สำหรับ a2 เท่านั้น แต่ขยายเป็นกรณีทั่วไปได้ง่าย โดยเปลี่ยน a2 เป็น ai ใด ๆ) แต่เนื่องจากจำนวนนับทุกจำนวนแยกเป็นผลคูณของจำนวนเฉพาะได้ จึงต้องมีจำนวนเฉพาะอื่นที่ไม่อยู่ในลำดับ an แต่เป็นตัวประกอบเฉพาะของ q ทั้งนี้ q เองอาจเป็นจำนวนเฉพาะก็ได้ ซึ่งการแยกตัวประกอบเฉพาะจะมีเพียง q สรุปแนวคิดอีกครั้ง:
- จำนวนนับทุกจำนวนเขียนเป็นผลคูณของจำนวนเฉพาะได้
- ตามข้อสมมติ ลำดับ an มีจำนวนเฉพาะที่มีอยู่ครบทุกจำนวน
- ข้อความแรกจึงกล่าวได้ใหม่ว่า จำนวนนับทุกจำนวนเขียนเป็นผลคูณของพจน์บางพจน์ของลำดับ an ได้ เพราะลำดับนี้มีจำนวนเฉพาะครบทุกจำนวน
- เราพิสูจน์แล้วว่าไม่มีจำนวนใดในลำดับ an ที่หาร q ลงตัว
- จึงเกิดข้อขัดแย้งกับข้อสมมติ → ถ้าจำนวนนับทุกจำนวนต้องแยกเป็นผลคูณของจำนวนเฉพาะได้ และลำดับ an ไม่มีจำนวนใดที่หาร q ลงตัว ต้องมีจำนวนเฉพาะอื่นที่หาร q ลงตัวและเป็นตัวประกอบเฉพาะของ q
เราจึงได้ข้อขัดแย้ง การแยกตัวประกอบเฉพาะของ q มีจำนวนเฉพาะที่ไม่อยู่ในลำดับซึ่งสมมติไว้ว่ามีจำนวนเฉพาะครบทุกจำนวน นิเสธของข้อความจึงเป็นเท็จ และข้อความเดิมเป็นจริง จำนวนเฉพาะมีมากมายไม่สิ้นสุด
สารบัญ: การพิสูจน์คืออะไร, การพิสูจน์โดยข้อขัดแย้ง, อุปนัยเชิงคณิตศาสตร์