ทฤษฎีบทความไม่บริบูรณ์ของเกอเดิล

**ทฤษฎีบทความไม่บริบูรณ์ของเกอเดิล** (Gödel's incompleteness theorems) เป็นทฤษฎีบทในคณิตตรรกศาสตร์ ซึ่ง เคิร์ท เกอเดิล (Kurt Gödel) พิสูจน์ได้ในปี
ค.ศ. 1931

เคิร์ท เกอเดิล ซึ่งในขณะนั้นเป็นนักคณิตศาสตร์อยู่ที่มหาวิทยาลัยเวียนนา ได้ตีพิมพ์บทความชื่อ *Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme* (ต้นฉบับเป็นภาษาเยอรมัน หรือมีชื่อในภาษาอังกฤษว่า *On Formally Undecidable Propositions in Principia Mathematica and Related Systems* หรือ *ว่าด้วยประพจน์ที่ตัดสินไม่ได้อย่างเป็นรูปนัยใน [[พรินซิเพีย แมเทเมทิกา]] และระบบอื่นที่เกี่ยวข้อง*) ในบทความนี้ เกอเดิลได้แสดงผลลัพธ์เป็นสองทฤษฎีบทที่น่าตื่นตะลึง ซึ่งในภายหลังทฤษฎีบททั้งสองถูกเรียกรวมกันว่า**ทฤษฎีบทความไม่บริบูรณ์ของเกอเดิล** ทฤษฎีบทนี้นับว่าเป็นเป็นทฤษฎีบทสำคัญที่เข้าขั้นปฏิวัติวงการ ทั้งในด้านตรรกศาสตร์ ด้านคณิตศาสตร์ ด้านปรัชญา และด้านการแสวงหาความรู้ของมนุษยชาติ รวมทั้งทำให้เกิดบทวิเคราะห์ การตีความ และคำถามต่างๆ ตามมาขึ้นอีกมากมาย

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

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

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

แนวคิดของฮิลแบร์ทได้รับการต่อยอดจากบรรดานักคณิตศาสตร์หลายคน ในจำนวนนี้มีผลงานชิ้นเอกคือ พรินซิเพีย แมเทเมทิกา ซึ่งเป็นระบบรูปนัยที่พิสูจน์ความจริงทางเลขคณิต ที่สร้างขึ้นโดย เบอร์แทรนด์ รัสเซิลล์ และ อัลเฟรด ไวท์เฮด พรินซิเพีย แมเทเมทิกา ประกอบด้วยสัญลักษณ์ล้วนๆ เริ่มต้นขึ้นจากสัจพจน์ และดำเนินต่อไปด้วยกฎเกณฑ์ที่ตายตัว จนได้ทฤษฎีบทต่างๆ ขึ้นมา

คุณสมบัติสำคัญที่สุดของระบบรูปนัยคือความต้องกัน ซึ่งหมายความว่าในที่สุดแล้ว ระบบจะต้องไม่พิสูจน์จนได้ข้อขัดแย้งใดๆ เกิดขึ้น หรือพูดอย่างเป็นรูปนัยได้ว่า จะต้องไม่มีประพจน์ P ที่ทั้ง P และ \neg\,P สามารถพิสูจน์ได้ในระบบ 

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

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

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

## ทฤษฎีบทความไม่บริบูรณ์ข้อที่หนึ่ง

ทฤษฎีบทความไม่บริบูรณ์ของเกอเดิลข้อแรกกล่าวไว้ว่า

:*ระบบรูปนัยที่มีความต้องกันและมีประสิทธิภาพพอที่จะพิสูจน์ความจริงทางเลขคณิตได้ ระบบนี้จำเป็นที่จะต้องไม่บริบูรณ์*

ในการพิสูจน์ทฤษฎีบทความไม่บริบูรณ์นี้ สามารถอธิบายคร่าวๆ ให้เข้าใจง่ายที่สุดได้ว่า เกอเดิลได้สร้างประพจน์ G ขึ้นมาประพจน์หนึ่ง คล้ายๆ ประพจน์ที่เป็นปฏิทรรศน์คนโกหก โดยประพจน์ G มีความหมายว่า

:*ประพจน์นี้ไม่สามารถพิสูจน์ได้ว่าเป็นจริง*

เพราะฉะนั้น ถ้า G สามารถถูกพิสูจน์ได้ว่าเป็นจริง ก็หมายความว่าสิ่งที่ G บอกนั้นเป็นจริง แต่ G บอกว่าตัวเองไม่สามารถพิสูจน์ได้ว่าเป็นจริง ซึ่งขัดกับการถูกพิสูจน์ได้ว่าเป็นจริงข้างต้น เกิดเป็นข้อขัดแย้งขึ้นมา ??? G จึงเป็นตัวอย่างของประพจน์ที่เป็นจริงแต่ไม่สามารถพิสูจน์ได้ เป็นตัวอย่างที่แสดงให้เห็นถึงความไม่บริบูรณ์ของระบบ

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

เกอเดิลเริ่มต้นด้วยภาคแสดง Dem โดย Dem(x,z) หมายถึง ประพจน์ที่มีเลขเกอเดิลเท่ากับ z สามารถพิสูจน์ได้ในระบบจากลำดับของประพจน์ที่มีเลขเกอเดิลเท่ากับ x ซึ่ง Dem(x,z) ถือเป็นประพจน์อภิคณิตศาสตร์ แต่ก็สามารถเขียนให้อยู่ในรูปประพจน์ในระบบรูปนัยที่แสดงความสัมพันธ์ระหว่างตัวเลขสองตัวคือ x และ z ได้ 

ถ้าจะบอกว่า z ไม่สามารถพิสูจน์ได้ว่าเป็นจริง เราสามารถเขียนว่า
:\neg (\exists x)Dem(x,z) 
โดยเกอเดิลแสดงให้เห็นว่ามีประพจน์หนึ่งซึ่งมีเลขเกอเดิลเท่ากับ n และสามารถเขียนประพจน์นี้ได้ในรูป
:\neg (\exists x)Dem(x,n) 
ซึ่งประพจน์นี้เป็นประพจน์ที่บอกว่าตัวเองไม่สามารถพิสูจน์ได้ว่าเป็นจริง หรือกล่าวได้ว่านี่เป็นการเขียนประพจน์ G ข้างต้นขึ้นใหม่ ให้อยู่ในรูปแบบระบบรูปนัย

เมื่อลองพิจารณา G ในที่นี้ จะพบว่า ถ้า G สามารถถูกพิสูจน์ได้ว่าเป็นจริง \neg\,G จะสามารถถูกพิสูจน์ได้ว่าเป็นจริงด้วย เพราะว่า ถ้า G สามารถถูกพิสูจน์ได้ว่าเป็นจริง จะมีลำดับของประพจน์ที่มีเลขเกอเดิลเท่ากับ k ที่ Dem(k,n) เพราะฉะนั้น (\existsx)Dem(x,n) ก็จะสามารถถูกพิสูจน์ได้ นั่นคือ \neg\,G จะสามารถถูกพิสูจน์ได้ว่าเป็นจริงด้วย หมายความว่าระบบรูปนัยนี้มีความไม่ต้องกันเกิดขึ้นแล้ว

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

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

## ทฤษฎีบทความไม่บริบูรณ์ข้อที่สอง

ทฤษฎีบทความไม่บริบูรณ์ของเกอเดิลข้อหลังกล่าวไว้ว่า

:*ระบบรูปนัยที่มีประสิทธิภาพพอที่จะพิสูจน์ความจริงทางเลขคณิตได้ ระบบนี้จะพิสูจน์ได้ว่าตัวเองมีความต้องกันเมื่อและต่อเมื่อตัวเองมีความไม่ต้องกัน*

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

ส่วนการพิสูจน์ขาไปนั้น ก่อนอื่น ถ้าระบบมีความต้องกันเราสามารถเขียนในรูปประพจน์ได้ว่า (\existsy)(\neg\,\existsx)Dem(x,y) นั่นคือมีอย่างน้อยหนึ่งประพจน์ที่ระบบนี้พิสูจน์ไม่ได้ว่าเป็นจริง เราเรียกประพจน์นี้อย่างย่อๆ ว่า A และสามารถพิสูจน์ได้ในระบบว่า A -> G เป็นจริง (รายละเอียดในการพิสูจน์ขอละเอาไว้) ซึ่งถ้า A ถูกพิสูจน์ได้ว่าเป็นจริงโดยระบบแล้ว จากกฎการอนุมานที่มี G ก็จะสามารถถูกพิสูจน์ได้ว่าเป็นจริงด้วย แต่จากทฤษฎีบทข้อแรก ถ้า G ถูกพิสูจน์ได้ว่าเป็นจริง ระบบจะมีความไม่ต้องกันเกิดขึ้น จบการพิสูจน์

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

## เชิงอรรถ

## อ้างอิง
* Ernest Nagel, James Roy Newman, and Douglas R. Hofstadter, **Gödel's Proof**, revised edition, 2002. ISBN 0-8147-5816-9.

## ดูเพิ่ม
* ทฤษฎีบทความไม่บริบูรณ์ของเกอเดิล ใน สารานุกรมปรัชญาสแตนฟอร์ด
* 
* 

หมวดหมู่:คณิตตรรกศาสตร์
หมวดหมู่:ทฤษฎีบททางคณิตศาสตร์