Logic and Philosophy
《递归论：算法与随机性基础》勘误
(针对2018年10月第1版第1次印刷)
第13页第34行：“并且读写头停在……读写头停在0上）”改为“并且读写头停在\(y\) 串的 最后一个 1 （如果有的话，不然 \(y = 0\) ，停在隔开原 \(x + 1\) 串与 \(y + 1\) 串的 0 ） 的右侧。”
Set Theory II 2020
Online Lecture: Lecture 01 Slides
Mathematical Logic 2019
Modal Logic 2019
Lecture: H5116, F 8:009:40
Section: HGW2403, F(e) 18:3020:10
Textbook: https://doi.org/10.1017/CBO9781107050884
Computability Theory 2019
Lecture: H5312, W 18:3020:10
Section: H5312, W 20:2021:05
This course is based on Shore‘s lecture note. Here is some solutions for the exercises.
Mathematical Logic 2018
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 epsiloncomplete, 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 epsiloncomplete. 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)\bigmA\subset P(d)\big\}= P\big(\bigcap\big\{d\bigmA\subset P(d)\big\}\big).
\]
Therefore, \(B\) is welldefined. Next, we show that
\[
\bigcap\big\{d\bigmA\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.
Modal Logic 2018
Lecture: HGX205, M 18:3021
Section: HGW2403, F 18:3020
Exercise 01
 Prove that \(\neg\Box(\Diamond\varphi\wedge\Diamond\neg\varphi)\) is equivalent to \(\Box\Diamond\varphi\rightarrow\Diamond\Box\varphi\). What you have assumed?
 Define strategy and winning strategy for modal evaluation games. Prove Key Lemma: \(M,s\vDash\varphi\) iff V has a winning strategy in \(G(M,s,\varphi)\). Prove that modal evaluation games are determined, i.e. either V or F has a winning strategy.
And all exercises for Chapter 2 (see page 23, open minds)
Exercise 02
 Let \(T\) with root \(r\) be the tree unraveling of some possible world model, and \(T’\) be the tree unraveling of \(T,r\). Show that \(T\) and \(T’\) are isomorphic.
 Prove that the union of a set of bisimulations between \(M\) and \(N\) is a bisimulation between the two models.
 We define the bisimulation contraction of a possible world model \(M\) to be the “quotient model”. Prove that the relation links every world \(x\) in \(M\) to the equivalent class \([x]\) is a bisimulation between the original model and its bisimulation contraction.
And exercises for Chapter 3 (see page 35, open minds): 1 (a) (b), 2.
Exercise 03
 Prove that modal formulas (under possible world semantics) have ‘Finite Depth Property’.
And exercises for Chapter 4 (see page 47, open minds): 1 – 3.
Exercise 04

 Prove the principle of Replacement by Provable Equivalents: if \(\vdash\alpha\leftrightarrow\beta\), then \(\vdash\varphi[\alpha]\leftrightarrow\varphi[\beta]\).
 Prove the following statements.
 “For each formula \(\varphi\), \(\vdash\varphi\) is equivalent to \(\vDash\varphi\)” is equivalent to “for each formula \(\varphi\), \(\varphi\) being consistent is equivalent to \(\varphi\) being satisfiable”.
 “For every set of formulas \(\Sigma\) and formula \(\varphi\), \(\Sigma\vdash\varphi\) is equivalent to \(\Sigma\vDash\varphi\)” is equivalent to “for every set of formulas \(\Sigma\), \(\Sigma\) being consistent is equivalent to \(\Sigma\) being satisfiable”.
 Prove that “for each formula \(\varphi\), \(\varphi\) being consistent is equivalent to \(\varphi\) being satisfiable” using the finite version of Henkin model.
And exercises for Chapter 5 (see page 60, open minds): 1 – 5.
Exercise 05
Exercises for Chapter 6 (see page 69, open minds): 1 – 3.
Exercise 06
 Show that “being equivalent to a modal formula” is not decidable for arbitrary firstorder formulas.
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”.
Exercise 07
 Show that there are infinitely many nonequivalent modalities under T.
 Show that GL + Id is inconsistent and Un proves GL.
 Give a complete proof of the fact: In S5, Every formula is equivalent to one of modal depth \(\leq 1\).
Exercises for Chapter 8 (see page 99, open minds): 1, 2, 4 – 6.
Exercise 08
 Let \(\Sigma\) be a set of modal formulas closed under substitution. Show that \[(W,R,V),w\vDash\Sigma~\Leftrightarrow~ (W,R,V’),w\vDash\Sigma\] hold for any valuation \(V\) and \(V’\). Define a \(p\)morphism between \((W,R),w\) and \((W’,R’),w’\) as a “functional bisimulation”, namely bisimulation regardless of valuation. Show that if there is a \(p\)morphism between \((W,R),w\) and \((W’,R’),w’\), then for any valuation \(V\) and \(V’\), we have \[(W,R,V),w\vDash\Sigma~\Leftrightarrow~ (W’,R’,V’),w\vDash\Sigma.\]
Exercises for Chapter 9 (see page 99, open minds).
Exercise the last
Exercises for Chapter 10 and 11 (see page 117 and 125, open minds).