ทฤษฎีบทความไม่สมบูรณ์ของเกอเดล
ทฤษฎีบทความไม่สมบูรณ์ของเกอเดล (Gödel's incompleteness theorems) เป็นทฤษฎีตรรกะทางคณิตศาสตร์ ที่เกิดขึ้นในปี ค.ศ. 1931 โดย เคิร์ท เกอเดล (Kurt Gödel)
เคิร์ท เกอเดล ซึ่งในขณะนั้นเป็นนักคณิตศาสตร์อยู่ที่มหาวิทยาลัยเวียนนา ได้ตีพิมพ์เปเปอร์ชื่อ "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme" (ต้นฉบับเป็นภาษาเยอรมัน หรือมีชื่อในภาษาอังกฤษว่า "On Formally Undecidable Propositions in Principia Mathematica and Related Systems" หรือ "ว่าด้วยประพจน์ที่ตัดสินไม่ได้อย่างเป็นรูปนัยใน พรินซิเพีย แมเทเมทิกา และระบบอื่นที่เกี่ยวข้อง") ในเปเปอร์นี้ เกอเดลทำการพิสูจน์จนที่สุดแล้วได้ผลลัพธ์เป็นสองทฤษฎีบทที่น่าตื่นตะลึง ซึ่งในภายหลังทฤษฎีบททั้งสองถูกเรียกรวมกันว่าทฤษฎีบทความไม่สมบูรณ์ของเกอเดล ทฤษฎีบทนี้นับว่าเป็นเป็นทฤษฎีบทสำคัญที่เข้าขั้นปฏิวัติวงการ ทั้งในด้านตรรกศาสตร์ ด้านคณิตศาสตร์ ด้านปรัชญา และด้านการแสวงหาความรู้ของมนุษยชาติ รวมทั้งทำให้เกิดบทวิเคราะห์ การตีความ และคำถามต่างๆ ตามมาขึ้นอีกมากมาย
ทฤษฎีบทความไม่สมบูรณ์ของเกอเดลกล่าวถึงข้อจำกัดของวิธีการทางสัจพจน์ ซึ่งเป็นการใช้เหตุผลเชิงนิรนัยเพื่อพิสูจน์และแสวงหาความจริงทางคณิตศาสตร์ที่นับย้อนไปได้ถึงในสมัยกรีกโบราณ ตั้งแต่เมื่อครั้งที่ยุคลิดใช้วิธีการนี้เพื่อพิสูจน์ทฤษฎีบททางเรขาคณิตในหนังสืออีลีเมนท์ส วิธีการทางสัจพจน์เป็นวิธีที่สวยงามทางความคิด ดึงดูดใจใครหลายคน และก็เสมือนได้กลายเป็นวิธีการมาตรฐานในการแสวงหาความรู้ทางคณิตศาสตร์นับจากนั้นเป็นต้นมา
แต่เมื่อมีการค้นพบเรขาคณิตนอกแบบยูคลิดในช่วงศตวรรษที่ 19 ก็ก่อให้เกิดการเปลี่ยนแปลงกระบวนทัศน์ขนานใหญ่ ทำให้นักคณิตศาสตร์ทั้งหลายตระหนักว่าสัจพจน์นั้นไม่ใช่สิ่งที่ประจักษ์ชัดในตัวอีกต่อไป ส่งผลให้วงการคณิตศาสตร์พัฒนาไปในทางที่เป็นนามธรรมและเป็นรูปนัยมากขึ้น ที่เป็นนามธรรมก็เพราะนักคณิตศาสตร์มีอิสระในการเลือกสัจพจน์เพื่อที่จะสร้างสรรค์ระบบคณิตศาสตร์ใดๆ ก็ได้ขึ้นมา ส่วนที่เป็นรูปนัยก็เพราะนักคณิตศาสตร์ตระหนักว่าความจริงที่ได้มาจากการพิสูจน์ทางคณิตศาสตร์นั้นขึ้นอยู่กับการเลือกเลือกสร้างระบบ และระบบนี้ก็ดำเนินไปได้ด้วยตนเอง โดยที่ไม่จำเป็นต้องเกี่ยวข้องหรือต้องอ้างโยงถึงโลกภายนอก หรือต้องอาศัยการรับรู้หรือความเข้าใจของคนหนึ่งคนใด
จนในที่สุด ก็มีแนวคิดที่จะทำให้คณิตศาสตร์กลายเป็นระบบรูปนัยที่สมบูรณ์แบบ แนวคิดนี้เริ่มต้นขึ้นจากความปรารถนาของ ดาฟิด ฮิลแบร์ท ที่จะทำให้คณิตศาสตร์เป็นเรื่องของความแน่นอนตายตัวอย่างที่สุด ปราศจากความกำกวม หรือการตีความหมายใดๆ ทั้งสิ้น โดยสิ่งอื่นที่ไม่ได้อยู่ในระบบรูปนัย ฮิลแบร์ทจะไม่ถือว่าเป็นคณิตศาสตร์ แต่จะเรียกว่าเป็นอภิคณิตศาสตร์แทน ฮิลแบร์ทหวังว่าคณิตศาสตร์ในระบบรูปนัยจะให้ผลคือความจริงสัมบูรณ์ที่ปราศจากข้อโต้แย้ง ซึ่งเป็นอุดมคติสูงสุดของวิชาคณิตศาสตร์
แนวคิดของฮิลแบร์ทได้รับการต่อยอดจากบรรดานักคณิตศาสตร์หลายคน ในจำนวนนี้มีผลงานชิ้นเอกคือ พรินซิเพีย แมเทเมทิกา ซึ่งเป็นระบบรูปนัยที่พิสูจน์ความจริงทางเลขคณิต ที่สร้างขึ้นโดย เบอร์แทรนด์ รัสเซิลล์ และ อัลเฟรด ไวท์เฮด พรินซิเพีย แมเทเมทิกา ประกอบด้วยสัญลักษณ์ล้วนๆ เริ่มต้นขึ้นจากสัจพจน์ และดำเนินต่อไปด้วยกฎเกณฑ์ที่ตายตัว จนได้ทฤษฎีบทต่างๆ ขึ้นมา
คุณสมบัติสำคัญที่สุดของระบบรูปนัยคือความต้องกัน ซึ่งหมายความว่าในที่สุดแล้ว ระบบจะต้องไม่พิสูจน์จนได้ข้อขัดแย้งใดๆ เกิดขึ้น หรือพูดอย่างเป็นรูปนัยได้ว่า จะต้องไม่มีประพจน์ formula_1 ที่ทั้ง formula_1 และ formula_3formula_1 สามารถพิสูจน์ได้ในระบบ
ถ้าปราศจากความต้องกันแล้ว ระบบคณิตศาสตร์ก็จะพังครืน เพราะเราจะไม่สามารถเชื่อใจความจริงทางคณิตศาสตร์ที่ระบบพิสูจน์มาได้อีกต่อไป รัสเซิลล์ได้ค้นพบความไม่ต้องกันนี้ในทฤษฎีเซตของคันทอร์ ในรูปแบบที่เรียกว่าปฏิทรรศน์ของรัสเซิลล์ ทำให้ทฤษฎีเซตดั้งเดิมต้องถูกปรับปรุงใหม่เพื่อกำจัดปฏิทรรศน์นี้ทิ้งไป
นอกจากความต้องกัน นักคณิตศาสตร์ยังหวังว่าระบบรูปนัยที่พัฒนาขึ้นจะมีความสมบูรณ์ นั่นคือทุกประพจน์ที่มีรูปแบบถูกต้องตามระบบ จะสามารถพิสูจน์ได้โดยระบบว่าประพจน์นี้จริงหรือเท็จประการใด
จนกระทั่งเกอเดลได้ค้นพบทฤษฏีบทความไม่สมบูรณ์ ซึ่งมีใจความคร่าวๆ ว่า "ระบบรูปนัยใดๆ ก็ตามที่ซับซ้อนถึงขั้น พรินซิเพีย แมเทเมทิกา ถ้ามีความต้องกันแล้ว จะไม่มีความสมบูรณ์ รวมทั้งระบบรูปนัยนั้นจะไม่สามารถพิสูจน์ความต้องกันด้วยตัวของมันเองได้" ก็ทำให้วงการคณิตศาสตร์ตกตะลึงถึงขั้นช็อค เมื่อต้องรับรู้ว่าระบบคณิตศาสตร์ที่ได้พัฒนากันมาเนิ่นนานนั้นมีความไม่สมบูรณ์อยู่ในตัว ทฤษฎีบทความไม่สมบูรณ์ของเกอเดลจึงถือเป็นทฤษฎีบทที่ส่งผลกระทบที่รุนแรงลึกถึงรากฐานของคณิตศาสตร์เอง
ทฤษฎีบทความไม่สมบูรณ์ของเกอเดลข้อแรกกล่าวไว้ว่า
ในการพิสูจน์ทฤษฎีบทความไม่สมบูรณ์นี้ สามารถอธิบายคร่าวๆ ให้เข้าใจง่ายที่สุดได้ว่า เกอเดลได้สร้างประพจน์ formula_5 ขึ้นมาประพจน์หนึ่ง คล้ายๆ ประพจน์ที่เป็นปฏิทรรศน์คนโกหก โดยประพจน์ formula_5 มีความหมายว่า
เพราะฉะนั้น ถ้า formula_5 สามารถถูกพิสูจน์ได้ว่าเป็นจริง ก็หมายความว่าสิ่งที่ formula_5 บอกนั้นเป็นจริง แต่ formula_5 บอกว่าตัวเองไม่สามารถพิสูจน์ได้ว่าเป็นจริง ซึ่งขัดกับการถูกพิสูจน์ได้ว่าเป็นจริงข้างต้น เกิดเป็นข้อขัดแย้งขึ้นมา ??? formula_5 จึงเป็นตัวอย่างของประพจน์ที่เป็นจริงแต่ไม่สามารถพิสูจน์ได้ เป็นตัวอย่างที่แสดงให้เห็นถึงความไม่สมบูรณ์ของระบบ
นี่คือแนวคิดเบื้องต้น แต่ในการพิสูจน์ทฤษฎีบทความไม่สมบูรณ์นั้นต้องทำให้ formula_5 อยู่ในรูปแบบที่ถูกต้องตามระบบรูปนัย ซึ่งเกอเดลได้ค้นคิดประดิษฐ์วิธีการอันชาญฉลาดขึ้นมาเพื่อแก้ปัญหาตรงนี้ โดยใช้การให้เลขแบบเกอเดลเพื่อเปลี่ยนประพจน์ต่างๆ ในระบบรูปนัย ให้อยู่ในรูปเลขคณิตอีกทีหนึ่ง ซึ่งจะทำให้ข้อความที่เป็นอภิคณิตศาสตร์กลับไปอยู่ในรูปของคณิตศาสตร์ และสามารถพิสูจน์ได้ด้วยระบบรูปนัยอีกครั้ง
เกอเดลเริ่มต้นด้วยภาคแสดง formula_12 โดย formula_13 หมายถึง ประพจน์ที่มีเลขเกอเดลเท่ากับ formula_14 สามารถพิสูจน์ได้ในระบบจากลำดับของประพจน์ที่มีเลขเกอเดลเท่ากับ formula_15 ซึ่ง formula_13 ถือเป็นประพจน์อภิคณิตศาสตร์ แต่ก็สามารถเขียนให้อยู่ในรูปประพจน์ในระบบรูปนัยที่แสดงความสัมพันธ์ระหว่างตัวเลขสองตัวคือ formula_15 และ formula_14 ได้
ถ้าจะบอกว่า formula_14 ไม่สามารถพิสูจน์ได้ว่าเป็นจริง เราสามารถเขียนว่า
โดยเกอเดลแสดงให้เห็นว่ามีประพจน์หนึ่งซึ่งมีเลขเกอเดลเท่ากับ formula_21 และสามารถเขียนประพจน์นี้ได้ในรูป
ซึ่งประพจน์นี้เป็นประพจน์ที่บอกว่าตัวเองไม่สามารถพิสูจน์ได้ว่าเป็นจริง หรือกล่าวได้ว่านี่เป็นการเขียนประพจน์ formula_5 ข้างต้นขึ้นใหม่ ให้อยู่ในรูปแบบระบบรูปนัย
เมื่อลองพิจารณา formula_5 ในที่นี้ จะพบว่า ถ้า formula_5 สามารถถูกพิสูจน์ได้ว่าเป็นจริง formula_3formula_5 จะสามารถถูกพิสูจน์ได้ว่าเป็นจริงด้วย เพราะว่า ถ้า formula_5 สามารถถูกพิสูจน์ได้ว่าเป็นจริง จะมีลำดับของประพจน์ที่มีเลขเกอเดลเท่ากับ formula_29 ที่ formula_30 เพราะฉะนั้น (formula_31formula_15)formula_33 ก็จะสามารถถูกพิสูจน์ได้ นั่นคือ formula_3formula_5 จะสามารถถูกพิสูจน์ได้ว่าเป็นจริงด้วย หมายความว่าระบบรูปนัยนี้มีความไม่ต้องกันเกิดขึ้นแล้ว
ในทางกลับกัน ถ้า formula_3formula_5 สามารถถูกพิสูจน์ได้ว่าเป็นจริง เกอเดลแสดงให้เห็นว่าระบบรูปนัยนี้จะมีความไม่ต้องกันแบบโอเมกา หรือกล่าวให้แรงขึ้นไปได้ว่า ถ้า formula_3formula_5 สามารถถูกพิสูจน์ได้ว่าเป็นจริง formula_5 ก็สามารถถูกพิสูจน์ได้ว่าเป็นจริงด้วย หรือเกิดความไม่ต้องกันขึ้นนั่นเอง
เพราะฉะนั้น ระบบรูปนัยที่ต้องกันจะพิสูจน์ formula_5 ไม่ได้ว่าเป็นจริง แต่เมื่อพิสูจน์ formula_5 ไม่ได้ว่าเป็นจริง ก็หมายความว่าสิ่งที่ formula_5 บอกเป็นความจริง ในเมื่อระบบรูปนัยไม่สามารถพิสูจน์ความจริงข้อนี้ได้ก็หมายความว่าเกิดความไม่สมบูรณ์ขึ้นแล้ว และเกอเดลก็ตระหนักรู้ลึกซึ้งขึ้นไปอีกว่านี่ไม่ใช่ข้อบกพร่องของการสร้างหรือออกแบบระบบ ต่อให้เพิ่มสัจพจน์มากขึ้นเท่าใด หรือเพิ่มกฎการอนุมานให้มากขึ้นเพียงไหนก็ตาม ประพจน์แบบ formula_5 ก็สามารถถูกสร้างขึ้นได้เสมอ สิ่งที่เกอเดลค้นพบก็คือในระบบรูปนัยที่มีความต้องกันและมีประสิทธิภาพพอที่จะพิสูจน์ความจริงทางเลขคณิตนั้น ความไม่สมบูรณ์จำเป็นที่จะต้องเกิดขึ้น และเป็นสิ่งที่ไม่อาจจะหลีกเลี่ยงได้เลย นี่คือความรุนแรงของทฤษฎีบทความไม่สมบูรณ์ข้อที่หนึ่ง
ทฤษฎีบทความไม่สมบูรณ์ของเกอเดลข้อหลังกล่าวไว้ว่า
ในการพิสูจน์ขากลับ จะอาศัยข้อเท็จจริงประการหนึ่งว่า ในระบบรูปนัยที่มีประสิทธิภาพพอสมควร ถ้าระบบนี้ไม่มีความต้องกัน ทุกประพจน์จะสามารถถูกพิสูจน์ว่าเป็นจริงโดยระบบนี้ได้หมด เพราะฉะนั้นถ้าระบบนี้ไม่มีความต้องกัน ระบบนี้จะพิสูจน์ความต้องกันของตัวเองได้ว่าเป็นจริงด้วย
ส่วนการพิสูจน์ขาไปนั้น ก่อนอื่น ถ้าระบบมีความต้องกันเราสามารถเขียนในรูปประพจน์ได้ว่า (formula_31formula_46)(formula_3formula_31formula_15)formula_50 นั่นคือมีอย่างน้อยหนึ่งประพจน์ที่ระบบนี้พิสูจน์ไม่ได้ว่าเป็นจริง เราเรียกประพจน์นี้อย่างย่อๆ ว่า formula_51 และสามารถพิสูจน์ได้ในระบบว่า formula_52 เป็นจริง (รายละเอียดในการพิสูจน์ขอละเอาไว้) ซึ่งถ้า formula_51 ถูกพิสูจน์ได้ว่าเป็นจริงโดยระบบแล้ว จากกฎการอนุมานที่มี formula_5 ก็จะสามารถถูกพิสูจน์ได้ว่าเป็นจริงด้วย แต่จากทฤษฎีบทข้อแรก ถ้า formula_5 ถูกพิสูจน์ได้ว่าเป็นจริง ระบบจะมีความไม่ต้องกันเกิดขึ้น จบการพิสูจน์
ผลของทฤษฎีบทความไม่สมบูรณ์ข้อที่สองนี้บอกว่า ระบบรูปนัยที่มีประสิทธิภาพพอที่จะพิสูจน์ความจริงทางเลขคณิต จะไม่สามารถพิสูจน์ว่าตัวเองมีความต้องกันได้ แต่ก็ไม่ได้หมายความว่าความต้องกันของระบบนี้จะถูกพิสูจน์ไม่ได้เลย แต่ถ้าจะพิสูจน์ ก็ต้องใช้ระบบอื่นที่ไม่ใช่ตัวเอง โดย เกอร์ฮาร์ด เกนต์เซน สามารถพิสูจน์ความต้องกันของระบบรูปนัยทางเลขคณิตได้ ในปี ค.ศ. 1936