R.Smullyan『不完全性定理』改訂版
ここでいう数とは自然数のことに限る
次の性質を満たす体系$ \mathscr{L}について考える
1. 加算無限集合$ \mathcal{E}：$ \mathscr{L}の式
2.$ \mathcal{E}の部分集合$ \mathcal{S}：$ \mathscr{L}の文
3.$ \mathcal{E}の部分集合$ \mathcal{P}：$ \mathscr{L}の証明可能な文
4.$ \mathcal{E}の部分集合$ \mathcal{R}：$ \mathscr{L}の反証可能な文
5.式の集合$ \mathcal{H}：$ \mathscr{L}の述語
6. 任意の式$ Eと任意の自然数$ nに対して式$ E(n)を割り当てる関数$ \Phi
ただし$ \Phiは述語$ Hと自然数$ nに対して文$ H(n)を割り当てることを条件とする
7.$ \mathcal{E}の部分集合$ \mathcal{T}：$ \mathscr{L}の真な文，真理集合
$ \mathscr{L}の言及可能性
真理集合$ \mathcal{T}に関係する概念（$ \mathcal{P},\mathcal{R}に無関係）
数$ n，述語$ Hとし，
文$ H(n)が真，つまり$ H(n) \in \mathcal{T}のとき
「$ nは$ Hを充足させる」
述語$ Hを充足させる数$ n全ての集合を$ Aとしたとき
「$ Aは$ Hで言及される」
$ H(n) \in \mathcal{T} \iff n \in A
数の集合$ Aが$ \mathscr{L}の述語で言及されるなら
「$ Aは$ \mathscr{L}で言及可能」
$ \mathscr{L}の正確性
$ \mathscr{L}で証明可能な全ての文を真とし，反証可能な全ての文を偽とする
「$ \mathscr{L}は正確である」
$ \mathcal{P}が$ \mathcal{T}の部分集合かつ，$ \mathcal{R}と$ \mathcal{T}には共通部分が存在しない
$ \mathscr{L}の全ての式$ Eに対して$ g(E) = nとなる数$ nを唯一つ対応させる関数を定める（Gödel数） 全ての数は何らかの式のGödel数であるとする
数$ nに対して式$ E_nを$ g(E_n) = nとする
式$ E_n(n)は$ E_nの対角式と呼ぶ
特に$ E_nが述語なら$ E_n(n)は文
$ E_n(n)が真 $ \iff $ nは$ E_n自体を充足する
対角式のGödel数，すなわち$ g(E_n(n))を$ d(n)とする，$ d(n) := g(E_n(n))
任意の数集合$ Aに対して$ d(n) \in Aを満たす全ての$ nの集合を$ A^*とする
任意の数$ nについて$ n \in A^* \iff d(n) \in A \iff g(E_n(n)) \in A
適当な体系$ \mathscr{L}において証明可能な文全てのGödel数の集合を$ Pとする
数全体の集合，すなわち$ \Nに対する$ Aの補集合を$ \tilde{A}
定理GT
正確な体系$ \mathscr{L}でかつ集合$ (\tilde{P})^*が$ \mathscr{L}言及可能なとき，$ \mathscr{L}真かつ$ \mathscr{L}証明不能な文が存在する
$ (\tilde{P})^*は$ d(n) \in \tilde{P}を満たす全ての$ nの集合
証明
仮定が成り立つとする
$ \mathscr{L}で$ (\tilde{P})^*を言及する述語$ Hとし，$ HのGödel数は$ hとする
$ Hの対角式$ G = H(h)は真かつ$ \mathscr{L}証明不能を示す
任意の数$ nで$ H(n)が真$ \iff$ nで $ n \in (\tilde{P})^*
言及性の定義
$ n = hとして$ h \in (\tilde{P})^*
任意の$ nで成り立つなら$ hでも成り立つ
$ h \in (\tilde{P})^* \iff d(h) \in \tilde{P} \iff d(h) \notin P \iff g(H(h)) \notin P
整理すると，$ H(h)が真$ \iff$ g(H(h)) \notin P
よってどちらかである
$ H(h)が真でかつ，$ H(h)は証明不能（$ Pの定義より）
$ H(h)が真でないかつ，$ H(h)は証明可能
これは仮定$ \mathscr{L}の正確性より矛盾する
以上より，$ H(h)は真かつ，$ H(h)は証明不能
したがって，$ \mathscr{L}真かつ$ \mathscr{L}証明不能な文$ H(h)が存在する
証明2：補助定理Dを使って
$ (\tilde{P})^*が$ \mathscr{L}言及可能なら，$ \tilde{P}のGödel文，つまり「$ \mathscr{L}証明不能のとき真」な文が存在する
補助定理D
$ \mathscr{L}について次の条件G1 ~ G3を考えて$ (\tilde{P})^*の言及可能性について検証する
G1. $ \mathscr{L}で言及可能な全ての集合$ Aについて$ A^*が$ \mathscr{L}言及可能
G2. $ \mathscr{L}で言及可能な全ての集合$ Aについて$ \tilde{A}が$ \mathscr{L}言及可能
G3. $ Pが$ \mathscr{L}言及可能
数集合$ A，文$ E_nに対して
$ E_nが真$ \iff$ g(E_n) \in Aなら
「$ E_nを$ Aに対してのGödel文」
集合$ AのGödel文とは「文自体のGödel数が$ Aの要素である」を主張する文である
補助定理D
a. 任意の数集合$ Aで$ A^*が$ \mathscr{L}で言及可能なら$ AのGödel文が存在する
b. G1を満たす体系$ \mathscr{L}で言及可能な全ての集合$ Aに対して$ AのGödel文が存在する
証明
a.
$ \mathscr{L}で$ A^*を言及する述語$ HとそのGödel数$ hとして
任意の数$ nで$ H(n)が真$ \iff$ n \in A^*
$ n = hとして$ H(h)が真$ \iff$ h \in A^*
$ h \in A^* \iff g(H(h)) \in A
$ d(h) = g(E_h(h)) = g(H(h))
よって$ H(h)が真$ \iff$ g(H(h)) \in Aであり，これはGödel文の定義である
b. 自明
定理T
体系$ \mathscr{L}で真な文のGödel数の集合を$ Tとする
1. $ (\tilde{T})^*は$ \mathscr{L}言及不能
2. G1を満たす$ \mathscr{L}は$ \tilde{T}を$ \mathscr{L}言及不能
3. G1,G2を満たす$ \mathscr{L}は$ Tを$ \mathscr{L}言及不能
証明
補題
$ \tilde{T}のGödel文$ Gは存在しない
「$ GのGödel数が，真である文のGödel数のどれでもないなら，真」は矛盾する
$ GのGödel数は，真である文のGödel数ではない
$ Gが真のとき，$ GのGödel数は真である文のGödel数
1.$ (\tilde{T})^*が$ \mathscr{L}言及可能と仮定すると，補助定理Dより，$ \tilde{T}のGödel文が存在する，これは補題に矛盾する．
2. G1より$ \tilde{T}から$ (\tilde{T})^*が言及可能であることになる．1より矛盾．
3. G2より$ Tから$ \tilde{T}が言及可能であることになる．2より矛盾．
定理T.3は，G1，G2を十分に強い条件と濁すと次のように言い換えられる
「十分に強い条件下の体系では，その体系の真理概念を体系自体で定義することが出来ない」
文$ Xが$ \mathscr{L}で証明可能あるいは反証可能なら$ Xが決定可能，そうでないなら$ Xは決定不能である
$ \mathscr{L}の任意の文が決定可能なら完全，そうでない（決定不能な文が存在する）なら不完全
定理1
正確な$ \mathscr{L}について$ (\tilde{P})^*が言及可能なら$ \mathscr{L}は不完全である．
$ Pとは$ \mathscr{L}証明可能な文のGödel数の集合とする．
証明
$ \mathscr{L}が定理GTの仮定を満たすなら$ \mathscr{L}真かつ$ \mathscr{L}証明不能な文$ Gが存在する
$ Gは偽ではないので反証不能である
よって$ Gは証明不能かつ反証不能である
定理1': 双対性からの定理1の変形
正確な$ \mathscr{L}について$ R^*が言及可能なら$ \mathscr{L}は不完全である．
より言うと，$ R^*を言及する述語$ Kについて$ K(k)が決定不能
$ Rとは$ \mathscr{L}反証可能な文のGödel数の集合とする．
証明
仮定が成立するとする
$ RのGödel文が存在する，
補助定理D
$ R^*を言及する述語$ Kとし，文$ K(k)は$ RのGödel文
文$ K(k)が真$ \iff$ g(K(k)) \in R$ \iff$ K(k)は$ \mathscr{L}反証可能
よってどちらかである
$ K(k)が真なら同時に$ K(k)は$ \mathscr{L}反証可能
$ \mathscr{L}の正確性よりこれは矛盾する
真なら証明可能でなければならない
$ K(k)が偽なら同時に$ K(k)が$ \mathscr{L}反証不能
$ \mathscr{L}の正確性よりこれも矛盾する
偽なら反証可能でなければならない
以上より，文$ K(k)は証明可能でも反証可能でもない（証明不能かつ反証不能）
2
言及する
自由出現する変数が$ v_iのみの論理式$ F(v_i)が数集合$ Aを言及する
$ n \in A$ \iff$ F(a)が真
例えば
偶数は自由出現が$ v_1のみの論理式$ \exists v_2(v_1 = \bar{2} \cdot v_2)によって言及される
集合または関係が，言語$ \mathscr{L}_Eの論理式として表すことが可能なら（言及可能なら），このとき集合/関係は算術的Eという
3
4
11.
自己言及体系
絶対これ3章あたりに持ってきたほうが理解進むだろ
「推論者は$ pであることを信じる」命題を$ Bpと表記しているがこれを$ \Box pと書くと「ある体系$ pで証明できる」に近いものができると思う