# Research

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

(针对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\)”。

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

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

## How to define membership relation from subset relation and power set operation

In my talk at 2018 Chinese Mathematical Logic Conference, I asked if \((V,\subset,P)\) is epsilon-complete, namely if the membership relation can be recovered in the reduct. Professor Joseph S. Miller approached to me during the dinner and pointed out that it is epsilon-complete. Let me explain how.

**Theorem**

Let \((V,\in)\) be a structure of set theory, \((V,\subset,P)\) is the structure of the inclusion relation and the power set operation, which are defined in \((V,\in)\) as usual. Then \(\in\) is definable in \((V,\subset,P)\).

**Proof.**

Fix a set \(x\). Define \(y\) to be the \(\subset\)-least such that

\[\forall z \big((z\subset x\wedge z\neq x)\rightarrow P(z)\subset y\big).\]

Actually, \(y=P(x)-\{x\}\), so \(\{x\}= P(x) – y\). Since set difference can be defined from subset relation and \((V,\subset,\{x\})\) can define \(\in\), we are done.

\(\Box\)

Here is another argument figured out by Jialiang He and me after we heard Professor Miller’s Claim.

**Proof.**

Since \(\in\) can be defined in \((V,\subset,\bigcup)\) (see the slides). Fix a set \(A\), it suffices to show that we can define \(\bigcup A\) from \(\subset\) and \(P\).

Let \(B\) be the \(\subset\)-least set such that there is \(c\), \(B=P(c)\) and \(A\subset B\). Note that

\[

\bigcap\big\{P(d)\bigm|A\subset P(d)\big\}= P\big(\bigcap\big\{d\bigm|A\subset P(d)\big\}\big).

\]

Therefore, \(B\) is well-defined. Next, we show that

\[

\bigcap\big\{d\bigm|A\subset P(d)\big\}=\bigcup A.

\]

Clearly, \(A\subset P(\bigcup A)\). This proves the direction from left to right. For the other direction, if \(x\) is in an element of \(A\), then it is in an element of \(P(d)\) given \(A\subset P(d)\), i.e. it is an element of such \(d\).

Therefore \(\bigcup A\) is the unique set whose power set is \(B\).

\(\Box\)

## Talk at Fudan Logic Seminar

Today at 2 p.m., I will talk at Fudan Logic Seminar about natural reducts of set theory models.

## 《作为哲学的数理逻辑》勘误

http://logic.fudan.edu.cn/doc/LaPamend.pdf

欢迎在评论区提交有关本书的勘误与修改意见。

第133-134页。“ZFC 的可数传递的模型”文本框中关于 \(T_\alpha\)（\(\omega\leq\alpha<\omega_1^\mathrm{CK}\)）的定义不是良定义的。