《数理逻辑:证明及其限度》(第二版)勘误

P. 11,例 1.4.1 (3),\(S_3(n)\) 的通项应为 “\(\frac{n^2(n+1)^2}{4}\)”。(感谢李令喜)(第二次印刷已修正)

P.17,1.5.5定义,要求S是由X的非空子集组成的集合。(否则无法排除划分中含有空集作为元素的情况,由此,第18页定理1.5.9(1)未必成立)。(第二次印刷已修正)

P.30,第12行,“\(f_\ast E\to E\)”改为“\(f_\ast E\times E\to E\)”。(感谢王琦)(第二次印刷已修正)

P.66,倒数第2、4、9行,将”\(P^1_i(x)\)“改为”\(P^1_i x\)“。(第二次印刷已修正)

P. 67,第2行。”\(\forall x (Sx\not\approx 0)\)“添加注释:”为了增加可读性,我们在这里添加了括号,用来表示那些正式的公式 ‘\(\forall v_i (\neg\approx Sv_i 0)\)’。后文中的‘\(\forall x~(x\notin z)\)’、‘\(\forall a(e+a\approx a)\)’等,也是类似情况”。(霍sh建议)(第二次印刷已修正)

P. 68,倒数第7行。”\(\forall a(\exists b(a+b\approx e))\)“改为”\(\forall a\exists b(a+b\approx e)\)“。根据简写规则前者会添加多余的括号。(霍sh建议)(第二次印刷已修正)

P.70,习题3.1.4。“没有形如\(4k+3\)的整数是平方和”拟改为“没有形如\(4k+3\)的整数是两个整数平方的和”。(张镇涛建议)

P.80,第5行。“\(y\)不在\(\varphi\)中出现”改为“\(y\)不在\(\Gamma\)和\(\varphi\)中出现”。(第二次印刷已修正)

P.116,第3行,“则\(\Gamma’=\)同样的原子公式,\(\psi(v_k),\Delta\),”改为“则\(\Gamma’=\)同样的原子公式,\(\psi(v_k),\Delta,\exists x\psi(x)\),”。(感谢曾千里)(第二次印刷已修正)

P.126,定理7.1.13,“\(0\leq\leq n\)”改为“\(0\leq i\leq n\)”。(感谢曾千里)(第二次印刷已修正)

P. 136,例 7.3.2, 7.3.3 中定义的\(R\), \(P_a\), \(R_a\)在格式上更显著的标出,并给出更多例子,方便读者阅读到后面的时候往回查找。(何jl建议)(涉及较多页码改动,第二次印刷未改动

P.165,8.4节第一段两处“8.4节和8.4.6节”均应改为“8.4节和8.5节”。

P.169,倒数第8行,“根据以上对非标准模型的分析,我们不能用乌什-沃特判别法。”细节待补充(感谢曾千里)(涉及较多页码改动,第二次印刷未改动

P.172,定理8.5.3,“存在自然数\(M\)和\(p\)”改为“存在自然数\(M\)和\(p>0\)”。(感谢曾千里)(第二次印刷已修正)

P. 174,习题8.5.5,添加提示:对\(n>1\),令\(\sigma_n\)为命题\(\forall x(\bigvee_{0\leq y\leq n-1}x\equiv_n y)\)。对每个\(n>1\),尝试找到满足\(\sigma_i\)(\(i\leq n\))但并不满足所有\(\sigma_m\)的非标准模型。
例如,考虑非标准模型里面的元素都是形如\((q,i)\)的,其中\(q\)是一个\(\geq 0\)的有理数,\(i\)是一个整数;\(q=0\)时,\(i\)只能取自然数;直观上\(q>0\)时\((q,i)\)就是编码为\(q\)的\(Z\)链上的第\(i\)号;加法自然地取两个分量分别相加。要找到满足\(\sigma_i\)(\(i\leq n\))却不满足整个普莱斯伯格算术的模型。考虑上述模型的一个子模型。其中只允许形如\((m/N^k,i)\)的元素,其中\(N=n!\),\(m\)和\(k\)是自然数。(感谢曾千里)(涉及较多页码改动,第二次印刷未改动

P. 234,习题10.4.4,“\(\vdash_T\Box_{T’}\varphi\leftrightarrow\Box_T(\varphi\rightarrow\varphi)\)”改为“\(\vdash_T\Box_{T’}\psi\leftrightarrow\Box_T(\varphi\rightarrow\psi)\)”。(感谢曾千里)(第二次印刷已修正)

P. 240,第4行,“(Chang and Keisler, 1900)”改为“(Chang and Keisler, 1990)”(感谢曾千里)(第二次印刷已修正)

P. 156, 180, 181, 182, 206, 207, 208, 220, 221, 222, 223, 224, 227, 231, 232, 233, 234,“\(\vdash_T\)”用法统一为“\(T\vdash\)”。(第二次印刷已修正)

P. 187,定理9.1.26,“一个\(\Delta_1\)的公式”的表述有问题。P. 179页把对\(\Delta_1\)的定义基于“逻辑等价”,需要修正。(感谢姚宁远)

see also http://logic.fudan.edu.cn/book/ml2

《递归论:算法与随机性基础》勘误

(针对2018年10月第1版第1次印刷)

第13页第3-4行:“并且读写头停在……读写头停在0上)”改为“并且读写头停在\(y\)­ 串的 最后一个 1 (如果有的话,不然 \(y = 0\) ,停在隔开原 \(x + 1\)­ 串与 \(y + 1\)­ 串的 0 ) 的右侧。”

第158页第一段:\(x,y\) 统一分别改为 \(\sigma,\tau\)。

第162页第三段开头:“对0-1串\(\sigma\)”,改为“对0-1串\(\tau\)”。

第164页第9行:“\(C(\sigma)\leq |\sigma|-|\mu|…\)”改为“\(C(\sigma)\leq |\sigma|-|\nu|…\)”。

第169页倒数第5行:“对每个 \(\mu\)”改为“对每个 \(\tau\)”。

第177页,定理5.2.35证明中,把出现的“\(c_0\)”统一改为“\(c_e\)”更合适。

第178页倒数第9行:改为\(\lambda(U_n)\leq\frac{(\mathrm{e}^{-2\varepsilon^2})^n}{1-\mathrm{e}^{-2\varepsilon^2}}\),即指数由\(m\)改为\(n\)。