Today at 2 p.m., I will talk at Fudan Logic Seminar about natural reducts of set theory models.
Blog
Set Theory II (Forcing) 2018
Lecture: HGW2403, T 18:3021
Section: HGW2403, R 18:3020
Instruction for the final paper
You can choose one of the following topics.
 An introduction to one specific forcing notion from this list (for Cohen forcing you can introduce an application not discussed in our course) and explain how it works.
 On one or more issues concerning the metatheory of forcing. For example, why and how we can talk about an “outer model” or a “object” not in our universe, why we can and why we need to assume the existence of a transitive model, how to account forcing arguments as purely constructive methods, etc.
Problem set 01
 Let \(\pi\) be the canonical interpretation of PA into ZF. Can we prove “for each arithmetic formula \(\varphi\), if ZFC \(\vdash\pi(\varphi)\), then PA \(\vdash\varphi\)”? Prove it if we can, explain it if we cannot.
 Assume ZF \(\vdash\varphi^L\) for each formula \(\varphi\in\Sigma\), and \(\Sigma\vdash\psi\). Show that ZF \(\vdash\psi^L\).
 Why Con(ZF) does not imply there is a countable transitive model of ZF?
Problem set 02
Kunen’s set theory (2013) Exercise I.16.6 – I.16.10, I.16.17.
Problem set 03
Kunen’s set theory (2013) Exercise II.4.6, 4.8.
Jech’s set theory (2002) Exercise 7.1, 7.3 – 7.5, 7.13, 7.16, 7.18 – 7.20, 7.22 – 7.33.
Problem set 04
 Let \(M^\mathbb{B}\) be a Boolean valued model. Prove the following statements are valid in \(M^\mathbb{B}\).
 \(\forall y\big(\forall x\varphi(x)\rightarrow\varphi(y)\big)\).
 \(\forall x(\varphi\rightarrow\psi)\rightarrow\forall x\varphi\rightarrow\forall x\psi\).
 \(\alpha\rightarrow\forall x\alpha\), \(x\) does not occur in \(\alpha\) freely.
Jech’s set theory (2002) Exercise 14.12.
Problem set 05
 Let \(\sigma\) be a \(\mathbb{B}\)name. Show that \[ \!\exists x\in\sigma~\varphi(x)\! = \sum_{\xi\in\textrm{dom}\sigma}\sigma(\xi)\cdot\!\varphi(\xi)\!.\]
 For any partial order \(\mathbb{P}\), there is a separative partial order \(\mathbb{Q}\) and a surjection \(h:\mathbb{P}\to\mathbb{Q}\) such that
 \(x\leq y\) implies \(h(x)\leq h(y)\);
 \(x\) and \(y\) are compatible in \(\mathbb{P}\) if and only if \(h(x)\) and \(h(y)\) are compatible in \(\mathbb{Q}\).
Such \(\mathbb{Q}\) is unique up to isomorphism. We call it the separative quotient of \(\mathbb{P}\).
Jech’s set theory (2002) Exercise 14.1, 14.9, 14.14, 14.16. Lemma 14.13.
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).
The idea of a decentralized danmaku (弾幕) and subtitles service
Niconico and bilibili are the two leading streaming video sharing service provider who also feature overlaid comments called danmaku (弾幕).
Continue reading “The idea of a decentralized danmaku (弾幕) and subtitles service”
Koh Tao 2015
为什么能行可计算的就是图灵可计算的（递归的）
这是对知乎问题为什么能行可计算的就是图灵可计算的 的回答。
如果我没理解错的话，题主想要问的实际上就是丘奇图灵论题（ChurchTuring Thesis）为什么成立。丘奇图灵论题简单地说就是：
一个自然数上的函数\(f:\mathbb{N}^n\to\mathbb{N}\)是能行可计算的（effectively computable），当且仅当它是图灵可计算的（Turing computable）。
Continue reading “为什么能行可计算的就是图灵可计算的（递归的）”
《数理逻辑：证明及其限度》勘误
欢迎在评论区提交有关本书的勘误与修改意见。 Continue reading “《数理逻辑：证明及其限度》勘误”
《作为哲学的数理逻辑》勘误
欢迎在评论区提交有关本书的勘误与修改意见。
如何解决血荒、血贵以及不公平的卖血问题
最近北京卫计委叫停互助献血的举措引起较多争议。我想借机谈谈个人关于构建“以血换血”为主“以钱换血”为辅的血液管理体系的设想。
Continue reading “如何解决血荒、血贵以及不公平的卖血问题”
加密数字货币、信任与虚拟身份
1620年11月11日，载着英格兰分离教派清教徒的五月花号终于决定停靠在现马赛诸塞州的鳕鱼角。这不是这片新大陆第一批英语殖民者，当然也不是最后一批。这些殖民者或因为坚持独特的宗教理想或为逃避政治迫害或存粹为了投机而选择离开了欧洲的成熟社会，以寻求各自心中的理想之国。得益于大西洋的阻隔，这群人可以摆脱部分历史束缚，相对自由地开始新的社会实验。十八世纪以来发源于欧洲的启蒙思想和理论在这里找到了理想的实验环境。 Continue reading “加密数字货币、信任与虚拟身份”