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

จากวิกิพีเดีย สารานุกรมเสรี

ทฤษฎีบทความไม่สมบูรณ์ของเกอเดล (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 หรือ ว่าด้วยประพจน์ที่ตัดสินไม่ได้อย่างเป็นรูปนัยใน พรินซิเพีย แมเทเมทิกา และระบบอื่นที่เกี่ยวข้อง) ในเปเปอร์นี้ เกอเดลทำการพิสูจน์จนที่สุดแล้วได้ผลลัพธ์เป็นสองทฤษฎีบทที่น่าตื่นตะลึง ซึ่งในภายหลังทฤษฎีบททั้งสองถูกเรียกรวมกันว่าทฤษฎีบทความไม่สมบูรณ์ของเกอเดล ทฤษฎีบทนี้นับว่าเป็นเป็นทฤษฎีบทสำคัญที่เข้าขั้นปฏิวัติวงการ ทั้งในด้านตรรกศาสตร์ ด้านคณิตศาสตร์ ด้านปรัชญา และด้านการแสวงหาความรู้ของมนุษยชาติ รวมทั้งทำให้เกิดบทวิเคราะห์ การตีความ และคำถามต่างๆ ตามมาขึ้นอีกมากมาย

เนื้อหา 1 จุดเริ่มต้น 2 ทฤษฎีบทความไม่สมบูรณ์ข้อที่หนึ่ง 3 ทฤษฎีบทความไม่สมบูรณ์ข้อที่สอง 4 อ้างอิง

[แก้] จุดเริ่มต้น

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

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

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

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

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

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

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

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

[แก้] ทฤษฎีบทความไม่สมบูรณ์ข้อที่หนึ่ง

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

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

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

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

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

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

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

ถ้าจะบอกว่า z ไม่สามารถพิสูจน์ได้ว่าเป็นจริง เราสามารถเขียนว่า

โดยเกอเดลแสดงให้เห็นว่ามีประพจน์หนึ่งซึ่งมีเลขเกอเดลเท่ากับ n และสามารถเขียนประพจน์นี้ได้ในรูป

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

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

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

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

[แก้] ทฤษฎีบทความไม่สมบูรณ์ข้อที่สอง

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

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

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

ส่วนการพิสูจน์ขาไปนั้น ก่อนอื่น ถ้าระบบมีความต้องกันเราสามารถเขียนในรูปประพจน์ได้ว่า (y)(x)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 0814758169.

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