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

(针对2018年10月第1版第1次印刷)

第13页第3-4行:“并且读写头停在……读写头停在0上)”改为“并且读写头停在\(y\)­ 串的 最后一个 1 (如果有的话,不然 \(y = 0\) ,停在隔开原 \(x + 1\)­ 串与 \(y + 1\)­ 串的 0 ) 的右侧。”

Set Theory II (Forcing) 2018


Lecture: HGW2403, T 18:30-21
Section: HGW2403, R 18:30-20

Syllabus

Instruction for the final paper

You can choose one of the following topics.

  1. 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.
  2. On one or more issues concerning the meta-theory 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

  1. 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.
  2. Assume ZF \(\vdash\varphi^L\) for each formula \(\varphi\in\Sigma\), and \(\Sigma\vdash\psi\). Show that ZF \(\vdash\psi^L\).
  3. 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

  1. 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

  1. 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)|\!|.\]
  2. 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:30-21
Section: HGW2403, F 18:30-20

Syllabus

Exercise 01

  1. Prove that \(\neg\Box(\Diamond\varphi\wedge\Diamond\neg\varphi)\) is equivalent to \(\Box\Diamond\varphi\rightarrow\Diamond\Box\varphi\). What you have assumed?
  2. 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

  1. 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.
  2. Prove that the union of a set of bisimulations between \(M\) and \(N\) is a bisimulation between the two models.
  3. 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

  1. 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

    1. Prove the principle of Replacement by Provable Equivalents: if \(\vdash\alpha\leftrightarrow\beta\), then \(\vdash\varphi[\alpha]\leftrightarrow\varphi[\beta]\).
    2. 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”.
    3. 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

  1. Show that “being equivalent to a modal formula” is not decidable for arbitrary first-order 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

  1. Show that there are infinitely many non-equivalent modalities under T.
  2. Show that GL + Id is inconsistent and Un proves GL.
  3. 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

  1. 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).