論理と計算のしくみ: 訂正と補足

ここは、萩谷昌己・西崎真也著「論理と計算のしくみ」(岩波書店)の訂正と補足のページです。

本書に対するご意見や間違いの指摘などは、

hagiya@is.s.u-tokyo.ac.jp
までよろしくお願いいたします。

p.221 補題5.15 および p.223

こちらを参照ください。

以下は第1刷に対する訂正と補足です。第2刷では改訂されています。

p.17 アメリカの首都はニューヨークである

アメリカの首都はワシントンです。 この命題は偽の命題の例としてあげました。

p.68 Γ→Δ,A'

カットの規則の左の前提は、Γ→Δ,Aの間違いです。

p.81 問題2.2

この問題はかなり難しいです。章末問題としては不適切でした。 特に、ヒルベルト流の基本的な性質について本文ではほとんど述べていませんので、 そのような性質を示しつつ証明する必要があります。 証明はここにあります。 安部達也君のより簡潔な証明はここにあります。(萩谷)

p.118 V(π0,P) = T

4行目の V0,P)=T は、 V(w0,P)=T の間違いです。

p.118 w |= A(AUB)

8行目の w |= A(AUB) は、 π |= A(AUB) の間違いです。

p.148 g(x,z)=h(x,z,w)

下から3行目の g(x,z)=h(x,z,w)は、 g(x,z)=h(x,z,z)の間違いです。

p.150 y < z および x < z

一般には、p(x,y)<=xおよび p(x,y)<=yですので、 4行目および6行目の有界最小化のy<zおよびx<zは、 y<z+1およびx<z+1とすべきです。

p.152 h(x)=a(h'(x),x)

6行目のh(x)=a(h'(x),x)は、 h(x)=a(h'(x),0)の間違いです。

p.160 算術の公理

等号に関する公理が不足しています。∀x(x=x)を 追加してください。

p.172 ∃w(Formula[x]∧¬Provable[x])

4行目の∃w(Formula[x]∧¬Provable[x])は、 ∃x(Formula[x]∧¬Provable[x])の間違いです。

p.176 A[z+1]∨A[z+2]∨A[z+3]

A[z+1]∨A[z+2]∨A[z+3]を 展開した結果が間違っています。 8行目から10行目は、正しくは、以下のようになります。(萩谷)

(z+1 < y+yz < z+1 ∧ 3|z+1) ∨
(z+2 < y+yz < z+2 ∧ 3|z+2) ∨
(z+3 < y+yz < z+3 ∧ 3|z+3)

p.245 問題1.1(iii)の解答

AからBへの関数をA×Bの部分集合と考えると、 φφは一点集合{φ}と定義することができます。 (任意の集合Aに対して、 Aφは一点集合{φ}と定義することが一般的です。) また、φφをφの要素の0個の列の集合と考えても、 φφは空列から成る一点集合に等しいと考えた方が自然です。

集合Aの要素の数を|A|で表すとき、 |AB|=|A||B|が 常に成り立つべきですが、 数学では0の0乗00が未定義であるため、 本章で説明しているような素朴な集合論では、 φφも未定義にした方がよいと考えていました。 しかし、離散的な場合は、数学においても00=1と考えるのが一般的です。 括弧の中の説明は、00が未定義であるという強引で間違った議論に他ありません。 すなわち、Aφが{φ}に等しく、 φAがφに等しいならば、 φφは{φ}にもφにもすることができてしまう、と主張しています。 しかし、φAがφに等しくなるためには、 A≠φという条件が必要とされます。 「矛盾していると考えることもできる」という言い方は不適切でした。(萩谷)