Lecture: H5116, F 8:00-9:40
Section: HGW2403, F(e) 18:30-20:10
Textbook: https://doi.org/10.1017/CBO9781107050884
Lecture: H5116, F 8:00-9:40
Section: HGW2403, F(e) 18:30-20:10
Textbook: https://doi.org/10.1017/CBO9781107050884
Lecture: H5312, W 18:30-20:10
Section: H5312, W 20:20-21:05
This course is based on Shore‘s lecture note.
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\)
Today at 2 p.m., I will talk at Fudan Logic Seminar about natural reducts of set theory models.
Lecture: HGX205, M 18:30-21
Section: HGW2403, F 18:30-20
And all exercises for Chapter 2 (see page 23, open minds)
And exercises for Chapter 3 (see page 35, open minds): 1 (a) (b), 2.
And exercises for Chapter 4 (see page 47, open minds): 1 – 3.
And exercises for Chapter 5 (see page 60, open minds): 1 – 5.
Exercises for Chapter 6 (see page 69, open minds): 1 – 3.
Exercises for Chapter 7 (see page 88, open minds): 1 – 6. For exercise 2 (a) – (d), replace the existential modality E with the difference modality D. In the clause (b) of exercise 4, “completeness” should be “correctness”.
Exercises for Chapter 8 (see page 99, open minds): 1, 2, 4 – 6.
Exercises for Chapter 9 (see page 99, open minds).
Exercises for Chapter 10 and 11 (see page 117 and 125, open minds).
这是对知乎问题为什么能行可计算的就是图灵可计算的 的回答。
如果我没理解错的话，题主想要问的实际上就是丘奇-图灵论题（Church-Turing Thesis）为什么成立。丘奇-图灵论题简单地说就是：
一个自然数上的函数\(f:\mathbb{N}^n\to\mathbb{N}\)是能行可计算的（effectively computable），当且仅当它是图灵可计算的（Turing computable）。
Continue reading “为什么能行可计算的就是图灵可计算的（递归的）”
欢迎在评论区提交有关本书的勘误与修改意见。
有朋友在知乎上问：
http://logic.fudan.edu.cn/doc/Course/2014/MathLogic/Lecture01.pdf 最后一段：
- 集合论可以被看作是一种一阶逻辑理论
- 一阶逻辑的语法、语义概念都可以在集合论中定义， 关于一阶逻辑的定理可以被看作是集合论的定理
建立一阶逻辑时貌似很多定义都用了集合论描述。而集合论本身又可以被看作是一种一阶逻辑理论。不是有循环定义的嫌疑吗？
我在知乎的回答如下： Continue reading “集合论和一阶逻辑的关系？”