เซ็ตของประโยคที่เป็นจริงของระบบไม่สามารถนิยามได้ในระบบ

ในหนังสือ Reflections ปู่เรย์อธิบายทฤษฎีบทของ Tarski ไม่ยาวนัก และสามารถทำความเข้าใจตามได้ไม่ยากนัก กำหนดให้ระบบเชิงคณิตศาสตร์ที่เรากำลังสนใจมีลักษณะดังนี้ (ในการบรรยายลักษณะของมัน เราจะใช้คำว่าจำนวนแทนจำนวนเต็มที่ไม่ติดลบ เช่น 0, 1, 2, 3, ..., n, ...) ในเซ็ตของข้อความ (expressions) ในระบบดังกล่าวจะมีเซ็ตที่ well-defined (ราชบัณฑิตฯ เรียก เซ็ตแจ่มชัด) เซ็ตหนึ่งของข้อความ ซึ่งเราเรียกข้อความของเซ็ต well-defined นั้นว่าประโยค (sentences) และเรียกข้อความของเซ็ตที่ well-defined เซ็ตอื่นว่า predicate (ราชบัณฑิตฯ เรียก ภาคแสดง)

predicate แต่ละตัวคือชื่อ (name) ของเซ็ตใดเซ็ตหนึ่งของจำนวน สำหรับแต่ละเพรดิเคต H และแต่ละจำนวนน n จะมีประโยคที่เขียนด้วย H(n) ซึ่งจะถูกตีความว่าหมายถึง n เป็นสมาชิกของเซ็ตที่มีชื่อว่า H

ประโยคทุกประโยคของระบบนี้อยู่ในรูป H(n) สำหรับบางเพรดิเคต H และจำนวน n

ทุกข้อความของระบบนี้จะมีการกำหนดหมายเลขกำกับ เราเรียกหมายเลขกำกับนั้นว่าจำนวนเกอเดลของข้อความ ถ้าจำนวน n เป็นจำนวนเกอเดลของประโยค เราจะเรียก n ว่าจำนวนประโยค (sentence number) และกำหนดให้ S_n แทนประโยคที่จำนวนเกอเดลเท่ากับ n, ถ้า n เป็นจำนวนเกอเดลของเพรดิเคต เราจะเรียก n ว่าจำนวนเพรดิเคต (predicate number) แล้วกำหนดให้ H_n แทนเพรดิเคตที่จำนวนเกอเดลเท่ากับ n

คำว่า diagonalization ของ H หมายถึงประโยค H(h) สำหรับเพรดิเคต H ใด ๆ ก็ตามที่จำนวนเกอเดลเท่ากับ h ฉะนั้นสำหรับจำนวนเพรดิเคต n ใด ๆ diagonalization ของ H_n คือประโยค H_n(n)

สำหรับแต่ละจำนวน n เราจะจับคู่มันกับจำนวนที่เขียนแทนด้วย n* ในแบบที่ ถ้า n เป็นจำนวนเพรดิเคต แล้ว n* เป็นจำนวนเกอเดลของประโยค H_n(n) (ประโยคนี้ก็คือ diagonalization ของ H_n นะฮะ) และเพื่อความสะดวก เราจะกำหนด notation ดังนี้ สำหรับเพรดิเคต H และข้อความ X ใด ๆ ว่า H[X] หมายถึง H(x) เมื่อ x คือจำนวนเกอเดลของ X ฉะนั้นสำหรับเพรดิเคต H ใด ๆ ข้อความ H[H] แทน diagonalization ของ H

กำหนดเซ็ต Σ เป็นเซ็ตของข้อความของระบบ เราจะพูดว่าเพรดิเคต H นิยาม Σ ในความหมายว่า H เป็นชื่อของเซ็ตของจำนวนเกอเดลของสมาชิกของ Σ ฉะนั้น H นิยาม Σ คือการพูดว่า สำหรับทุกข้อความ X แล้วประโยค H[X] เป็นจริงก็ต่อเมื่อ X เป็นสมาชิกของ Σ

ประโยคสองประโยคจะสมมูลกัน (equivalent) ถ้าพวกมันเป็นจริงทั้งคู่ หรือไม่ก็เป็นเท็จทั้งคู่ ทีนี้ ระบบที่เรากำลังสนใจจะต้องผ่านเงื่อนไขสองข้อคือ

C1: สำหรับเพรดิเคต H ใด ๆ จะมีเพรดิเคต H# ซึ่งจะถูกเรียกว่า diagonalizer ของเพรดิเคต H ในแบบที่ ประโยค H#(n) สมมูลกับ H(n*) สำหรับทุก ๆ จำนวนพริดิเคต n C2: สำหรับเพรดิเคต H ใด ๆ จะมีเพรดิเคต H-bar ซึ่งจะถูกเรียกว่านิเสธ (negation) ของเพรดิเคต H ในแบบที่ ประโยค H-bar(n) เป็นจริงก็ต่อเมื่อ H(n) เป็นเท็จ สำหรับทุกจำนวน n

เงื่อนไข C1 บอกว่า สำหรับเพรดิเคต H และ K ใด ๆ ประโยค H#[K] สมมูลกับ H[K[K]] เพราะ K ถูกจับคู่อยู่กับจำนวนเกอเดล k และ H#(k) สมมูลกับ H(k*) ซึ่ง H#(k) ก็คือประโยค H#[K] และเนื่องจาก k* เป็นจำนวนเกอเดลของ K[K] (ซึ่งก็คือ K(k)) ฉะนั้น H(k*) คือประโยค H[K[K]]

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

เราเรียกประโยค S ว่าเป็น fixed point ของเพรดิเคต H ถ้าประโยค S สมมูลกับ H[S] (โน้ต fixed point นี่สัมพันธ์กับ self-reference สมมติว่า S เป็น fixed point ของ H และให้ n เป็นจำนวนเกอเดลของ S ฉะนั้น S_n ซึ่งสมมูลกับ H(n) สามารถมองว่าเป็นการอ้างว่าจำนวนเกอเดลของมันเองอยู่ในเซ็ตที่ถูกระบุชื่อโดย H) อาศัยแค่ C1 เราจะได้ทฤษฎีบทที่ว่า "เพรดิเคต H ทุกตัว มี fixed point" (อันนี้พิสูจน์ได้ไม่ยาก จากเงื่อนไขว่า H#[K] สมมูลกับ H[K[K]] เราก็ให้ K แทนเพรดิเคต H# ก็จะได้ H#[H#] สมมูลกับ H[H#[H#]] ซึ่งหมายความว่า H#[H#] เป็น fixed point ของ H)

เราจะเรียกเพรดิเคต H ว่าเป็น truth predicate ถ้า H นิยามเซ็ตของประโยคที่เป็นจริง (นั่นคือ ถ้า H เป็นชื่อของเซ็ตของจำนวนเกอเดลของประโยคที่เป็นจริง) ในการพิสูจน์ทฤษฎีบทนี้ เราจะต้องแสดงให้เห็นว่า truth predicate ไม่สามารถมีอยู่ได้ในระบบเชิงคณิตศาสตร์ใดก็ตามที่เป็นไปตามสมมติฐานของเรา เอาล่ะ ถ้า H เป็น truth predicate แล้วละก็ สำหรับข้อความ X ใด ๆ ประโยค H[X] จะเป็นจริงก็ต่อเมื่อ X เป็นประโยคที่เป็นจริง นั่นคือ สำหรับประโยค S ทุกประโยค ประโยค H[S] เป็นจริงก็ต่อเมื่อ S เป็นจริง เท่ากับพูดว่า S เป็น fixed point ของ H ดังนั้น ถ้า H เป็น truth predicate แล้วประโยคทุกประโยคเป็น fixed point ของ H ฉะนั้น ถ้าเราสามารถแสดงได้ว่ามีอย่างน้อย 1 ประโยคที่ไม่เป็น fixed point ของ H ก็เป็นอันจบพิธี

จากทฤษฎีบท fixed point เรารู้ว่า H-bar มี fixed point สมมติว่ามันคือ S ฉะนั้น S สมมูลกับ H-bar(S) ทำให้ S ไม่สามารถสมมูลกับ H[S] (เพราะเป็นไปไม่ได้ที่ H-bar[S] จะสมมูลกับ H[S]) พูดอีกอย่างว่า การมีอยู่ของ fixed point ของ H-bar ก็คือเครื่องยืนยันว่า H ไม่เป็น truth predicate และ fixed point ตัวหนึ่งของ H-bar ก็คือ H-bar#[H-bar#] (จากตัวอย่างที่ใช้พิสูจน์ fixed point theorem) QED

จากจุดนี้ เราต่อไปที่ผลลัพธ์ของเกอเดลได้ฮะ ถ้ามีเซ็ตของประโยคที่เรียกว่า provable sentences (ประโยคที่สามารถพิสูจน์ได้) ในแบบที่เงื่อนไขต่อไปนี้เป็นจริง

C3: เซ็ตของประโยคที่สามารถพิสูจน์ได้ นิยามได้

เราจะเรียกระบบว่าเป็นระบบที่ถูกต้องถ้ามีเฉพาะประโยคที่เป็นจริงเท่านั้นที่สามารถพิสูจน์ได้ และเราจะถือว่าระบบที่เรากำลังสนใจอยู่นี้เป็นระบบที่ถูกต้อง (แปลว่า provable sentences ทุก ๆ ประโยค เป็นจริง) เนื่องจากเซ็ตของประโยคที่สามารถพิสูจน์ได้นิยามได้ และจากทฤษฎีบทของ Tarski เซ็ตของประโยคที่เป็นจริง ไม่สามารถนิยามได้ ฉะนั้นทั้งสองเซ็ตไม่ทับกันสนิท หมายความว่ามีความเป็นไปได้ 2 แบบ แบบแรก มีบางประโยคที่เป็นจริงที่ไม่สามารถพิสูจน์ได้ หรือแบบที่สอง มีบางประโยคที่สามารถพิสูจน์ได้ที่ไม่เป็นจริง แต่เราตั้งสมมติฐานว่าเป็นระบบที่ถูกต้อง ทำให้แบบที่สองตกไป ฉะนั้น เราได้ผลลัพธ์ของเกอเดลที่ว่ามีบางประโยคที่เป็นจริงที่ไม่สามารถพิสูจน์ได้ เราจะเรียกประโยคดังกล่าวว่าประโยคเกอเดล

เราสามารถแสดงตัวอย่างประโยคเกอเดลได้ดังนี้ เซ็ตของประโยคที่สามารถพิสูจน์ได้ถูกนิยามด้วยเพรดิเคต P บางตัว ฉะนั้น fixed point S ใด ๆ ของ P-bar ก็คือประโยคเกอเดล (เพราะ P[S] เป็นจริงก็ต่อเมื่อ S สามารถพิสูจน์ได้ ทำให้ P-bar[S] เป็นจริงก็ต่อเมื่อ S ไม่สามารถพิสูจน์ได้ และถ้า S สมมูลกับ P-bar[S] แล้ว S เป็นจริงก็ต่อเมื่อ S ไม่สามารถพิสูจน์ได้) และ fixed point ตัวหนึ่งของ P-bar ก็คือ P-bar#[P-bar#]

ฉะนั้น P-bar#[P-bar#] เป็นประโยคเกอเดล มันเป็นประโยคที่เป็นจริงแต่ไม่สามารถพิสูจน์ได้ในระบบ ภายใต้เงื่อนไขว่าระบบนั้นเป็นระบบที่ถูกต้อง