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

ทฤษฎีบทความไม่บริบูรณ์ของเกอเดิล[a] (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 {\displaystyle P} ที่ทั้ง P {\displaystyle P} และ ¬ {\displaystyle \neg \,} P {\displaystyle P} สามารถพิสูจน์ได้ในระบบ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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