菊池誠著『不完全性定理』初版 1・2 刷 正誤表 2017/9/8 （1/2） 頁 行 誤 正 36 ↑ 2 意義 異議 38 3 導くの長さ 導く長さ 72 13 補題 3.4.5 補題 3.4.4 98 4 し，集合論を紹介する集合を し，集合を 106 ↑ 8 ∀x∀y∀z(x ≤ y → x + z ≤ y + z) ∀x∀y∀z(x < y → x + z < y + z) 107 ↑ 3–2 y1, . . . , yn を · · · 自由変数 y を φ(x) に現れない変数
107 ↑ 2 ∀y(y < x → φ(x)) ∀y(y < x → φ(y))
108 5 ∀y < x¬φ(x) ∀y < x¬φ(y)
119 8 積集合 直積集合 122 脚注 11 Barwse Barwise 125 10 ∈ や ⊆ 集合間 ∈ や ⊆ は集合間 130 16 原始再帰法を使って 5.1 節で紹介する原始再帰法を使って 151 ↑ 9 ∃x < y，∀x < y を ∃x，∀x に書き換える （＊１） 157 ↑ 1 h(¯x) f (¯x) 162 脚注 1 自然数 a の数項は ˙a と書くことが多い． （削除） 163 1 PrvT が T が再帰的であれば PrvT は 163 3 とする．集合 とする．T が再帰的であれば集合 165 ↑ 14 f (m) 終了し f (m) の計算が終了し 166 15 Nn からN への （＊２） 169 1–2 また，次の定理で紹介するように， なお， 169 2–3 存在も· · · 用いて 存在は以下のように 169 11–16 C = · · · ではない． （＊３） 180 8 xm= g(x) xm= gm(x) 187 ↑ 11 T で T 上で 187 ↑ 10 T で T 上で 188 6 ただし証明は ただし (1)⇒ (2) の証明は 189 ↑ 5 A⊆ Nn A⊆ N 190 1 定理 6.4.4 定理 6.4.4 と注意 6.4.6 190 11 T 上で N 上で 190 12–13 の同値性が証明できる は同値である 190 ↑ 10 T 上で弱表現する 定義する 200 ↑ 14 T 上で （削除） 200 ↑ 14 弱表現 定義 200 ↑ 4 ω 無矛盾 Σ1健全 200 ↑ 2 ω 無矛盾 Σ1健全 201 ↑ 12 ω 無矛盾 Σ1健全 203 14 原始再帰的な n > 0 の場合は，原始再帰的な 203 16 Σn 論理式 n > 0 の場合は，Σn 論理式 210 10 PA−⊢ σ ↔ ¬PrT(⌈σ⌉) および （削除） 212 ↑ 10 対角化定理 定理 7.2.14 214 ↑ 7 N|= PrT(⌈¬φ(a)⌉) N |= PrT(⌈¬φ(a)⌉) 1
菊池誠著『不完全性定理』初版 1・2 刷 正誤表 2017/9/8 （2/2） 頁 行 誤 正 214 ↑ 6 N |= PrT(⌈φ(a)⌉) N |= PrT(⌈¬φ(a)⌉) 217 7 補題 7.4.1 (2) の証明 補題 7.4.1 D2 の証明 222 ↑ 2 補題 7.5.5 定理 7.5.5 224 ↑ 10 可証性述語は· · · 満たし， （＊４） 224 ↑ 9 成り立つと仮定する． 成り立つ． 231 12–15 ∀z ≤ y¬PfT(⌈0 = 1⌉, z) · · · 証明できる． （＊５） 233 ↑ 1 の場合 （削除） 258 ↑ 3 M 上で M 上での 264 13 b = 0 ならば （削除） 265 ↑ 1 しかし， しかし，以下で紹介するように， 267 脚注 3 Kriesel Kreisel 272 ↑ 6 注意 8.4.4 で 注意 6.2.5 で 272 ↑ 4 書くことにする．I∆0+ Exp （＊６） 274 2–4 次の問題が· · · 肯定的に解ける．〈問題 8.4.9〉 （削除） 274 5 するか． （＊７） 274 6 【注意 8.4.10】 【注意 8.4.9】 278 15 LF LR 278 16 LF LR 289 12 つてい義論する ついて議論する 304 15 何であるのは 何であるのかは
338 3 G¨odels’ result G¨odel’s result
（＊１）
∃z < y，∀z < y を ∃z，∀z に書き換え，B = {(¯x) ∈ Nn:∃z((¯x, z) ∈ A)}，C = {(¯x) ∈ Nn :∀z((¯x, z) ∈ A)}
とする． （＊２） 再帰的関数 f とは f のグラフではなく f の定義を意味することとし， （＊３） K は再帰的であると仮定する．このときN\K は再帰的可算なので，N\K = {x ∈ N : f(x) = 0} となる 再帰的関数 f が存在する．f (x)̸= 0 ならば f(x) の計算が停止しないように f を作り変えて，f(x) = 0 と f (x)↓ は同値であると仮定する．e = ⌈f⌉ とする．e ∈ N \ K と f(e) ↓ は同値であり，f(e) ↓ は V1(e, e)↓ のことなので e∈ K と同値であり，矛盾する．ゆえに K は再帰的ではない． （＊４） 可証性述語は形式化された演繹定理を満たすことを，すなわち，どのような φ と ψ についても T ⊢ PrT +φ(⌈ψ⌉) ↔ PrT(⌈φ → ψ⌉) が成り立つことを仮定する．このとき， （＊５） G¨odel の可証性述語 PrT(x)，Rosser の可証性述語 PrRT(x) 以外にも様々な可証性述語が知られている．例 えば，∃y(PfT(x, y)∧ ¬PfT(⌈0 = 1⌉, y)) を Pr∗T(x) とすれば，この Pr∗T(x) は可証性述語になる．なお， T ⊢ τ ↔ ¬Pr∗T(⌈τ⌉) を満たす τ は G¨odel 文になるが，注意 7.6.15 で紹介するように，この Pr∗T(x) は Rosser の可証性述語と似た性質を持つ． 2
（＊６） 書くことにする．自然数 x が素数であることを意味する ∆0 論理式を φ(x) とするとき，I∆0+ Exp （＊７） すれば，問題 8.4.5 は肯定的に解ける．しかし，M⊆eN となる N|= PA が存在しない可算な M |= BΣ1 が 存在する． 3
