論希爾伯特-柏奈證明要件—皮亞諾算術及羅賓森算術之案例研究

On Hilbert-Bernays Provability Conditions - Case Studies of Peano Arithmetic and Robinson Arithmetic

杜蕙伶(Hui-Ling Tu)

指導教授 ： 蔡行健

國立中正大學/文學院/哲學系/碩士(2014年)

摘要

哥德爾的第一不完備定理（Gödel's first incompleteness theorem）內容為，若T是夠強的遞迴公理化（recursively axiomatizable）理論，則T是一致的若且唯若T是不完備的。而哥德爾的第二不完備定理內容為，若T是夠強的遞迴公理化理論，則T是一致的若且唯若T無法證明自己的一致性。從邏輯文獻中可知，若某個夠強的遞迴公理化理論T能滿足下列三個希爾伯特-柏奈證明要件（Hilbert-Bernays provability condition），T便有第二不完備性。
PC1. 對任何語句σ而言，若⊢_T σ則⊢_T Bew_T (˹ σ ˺)。
PC2. 對任兩個語句ρ, σ而言，⊢_T Bew_T (˹ ρ → σ ˺) → (Bew_T (˹ ρ ˺) → Bew_T (˹ σ ˺))。
PC3. 對任何語句σ而言，⊢_T Bew_T (˹ σ ˺) → Bew_T (˹ Bew_T (˹ σ ˺) ˺)。

邏輯學界普遍認為羅賓森算術理論（Robinson arithmetic），或稱之為Q，有第一不完備性，但沒有第二不完備性。然而Q沒有第二不完備性的確切證明，筆者至今仍未在文獻中找到。若能確實證明Q沒有第二不完備性，我們或許能對不完備定理有更進一步的認識，例如釐清下列這些問題：是否能找到比歸納公理架構（induction schema）弱的公理或公理架構，使得Q加入此公理或公理架構後所得的理論有第二不完備性，以及一個理論要具有第二不完備性的最低門檻為何等等。因為Q與PA的公理十分相似，而PA只比Q多一個歸納公理架構，但是PA有第二不完備性，所以本論文整理了Q的第一不完備性，及PA的第二不完備性之證明，希望藉由比較這兩個證明，試著推測Q或許不能滿足上述所有的三個證明要件之原因。

關鍵字

希爾伯特-柏奈證明要件 ； 皮亞諾算術 ； 羅賓森算術 ； 不完備性

並列摘要

The following are the Hilbert-Bernays provability conditions:
1. For every sentence σ, if ⊢_T σ then ⊢_T Bew_T σ.
2. For every sentence σ, ⊢_T (Bew_T σ → Bew_T Bew_T σ).
3. For every sentence ρ, σ, ⊢_T (Bew_T (ρ → σ) → (Bew_T ρ → Bew_T σ)).
If a recursively axiomatizable theory T is sufficiently strong and satisfies all of these three conditions, then Gödel's second incompleteness theorem applies to T.

The only difference between Peano arithmetic (PA) and Robinson arithmetic (Q) is that PA has the induction schema while Q does not. It has been proved that the second incompleteness theorem applies to PA. However, it is believed that the second incompleteness theorem does not apply to Q, but so far I have not found any proof of this in the literature.

In this thesis I have restated Rautenberg's proof of the first incompleteness of Q, and Rautenberg's and Boolos's proofs of the second incompleteness of PA. By analyzing these proofs, I have briefly explained why Q may not satisfy all of these three Hilbert-Bernays provability conditions.

並列關鍵字

Peano Arithmetic ； Robinson Arithmetic ； Incompleteness ； Hilbert-Bernays Provability Condition

參考文獻

4. Gaifman, H. (2000). What Gödel's incompleteness result does and does not show. The Journal of Philosophy, Vol.97, No. 8, pp. 462-470.

1. Boolos, G. S. (1995). The logic of provability. New York (NY): Cambridge.

2. Enderton, H. B. (2001). A mathematical introduction to logic. (2nd ed.). San Diego (California): Academic.

3. Fitting, M. (2007). Incompleteness in the land of sets. London: College Publications.

5. Lindström, P (1997). Aspects of incompleteness. New York (NY): Springer.