Mathematical Logic 2020

Lecture: HGX308, M 9:55-11:35
Section: HGX307, R 18:30-20:10

Slides 01 (handout) Slides 02 (handout) Slides 03 (handout) Slides 04 (handout) Slides 05 (handout) Slides 06 (handout) Slides 07 (handout) Slides 08 (handout) Slides 09 (handout) Slides 10 (handout) Slides 11 (handout) Slides 12 (handout) Slides 13 (handout) Slides 14 (handout) Slides 15 (handout) Slides 16 (handout) Slides 17 (handout)

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

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\)。