Logic and Computation III
This is an advanced undergraduate and graduate-level course in mathematical logic and theory of computation, following on from Parts I and II. In the previous courses, we have covered the basics of computability and computational complexity, as well as fundamental results in first-order logic, formal arithmetic, and modal logic. In this semester, we will move on to analytical hierarchy, descriptive set theory, admissible recursion, inductive definition and modal $\mu$-calculus. Those who have not taken the previous courses should have a standard knowledge of mathematical logic such as contained in textbooks [1] or [2].
讲师
日期
2026年03月02日 至 06月29日
位置
| Weekday | Time | Venue | Online | ID | Password |
|---|---|---|---|---|---|
| 周一 | 15:20 - 17:50 | A3-2-301 | ZOOM 08 | 787 662 9899 | BIMSA |
修课要求
"Logic and Computation I (AU2024), II (SP2025)" or equivalent knowledge of mathematical logic and theory of computation.
课程大纲
0. Recaps: Fundamentals on theory of computation and mathematical logic, as well as the connection between them.
1. Descriptive set theory: Lightface and boldface hierarchies, ordinal notation, hyperarithmetical sets, and the Kondo-Addison theorem.
2. Determinacy and second-order arithmetic: Gale-Stewart games, determinacy and reverse mathematics, memoryless determinacy of parity games.
3. Admissible ordinals and KP set theory: Basics of KP set theory, $\alpha$-recursion theory, recursively large ordinals and models of second-order arithmetic.
4. Modal Mu-calculus and alternation hierarchy: Monotone operators, Modal mu-calculus and game semantics, strictness of alternation hierarchy.
1. Descriptive set theory: Lightface and boldface hierarchies, ordinal notation, hyperarithmetical sets, and the Kondo-Addison theorem.
2. Determinacy and second-order arithmetic: Gale-Stewart games, determinacy and reverse mathematics, memoryless determinacy of parity games.
3. Admissible ordinals and KP set theory: Basics of KP set theory, $\alpha$-recursion theory, recursively large ordinals and models of second-order arithmetic.
4. Modal Mu-calculus and alternation hierarchy: Monotone operators, Modal mu-calculus and game semantics, strictness of alternation hierarchy.
参考资料
[1] H.D. Ebbinghaus, H. Flum and W. Thomas, Mathematical Logic, 3rd ed., Springer 2021.
[2] D.C. Kozen, Theory of Computation, Springer 2006.
[3] J. Bradfield and I. Walukiewicz, the mu-calculuc and model-checking, E.M. Clarke et al. (eds.), Handbook of model-checking, Springer 2018.
[4] K. Tanaka, 計算理論と数理論理学 (Mathematics of Logic and Computation, in Japanese), Kyoritsu 2022.
[2] D.C. Kozen, Theory of Computation, Springer 2006.
[3] J. Bradfield and I. Walukiewicz, the mu-calculuc and model-checking, E.M. Clarke et al. (eds.), Handbook of model-checking, Springer 2018.
[4] K. Tanaka, 計算理論と数理論理学 (Mathematics of Logic and Computation, in Japanese), Kyoritsu 2022.
听众
Advanced Undergraduate
, Graduate
, 博士后
视频公开
不公开
笔记公开
公开
语言
英文
讲师介绍
田中一之教授博士毕业于美国加州大学伯克利分校，曾就职于东京工业大学和东北大学，并指导15位博士生和50名硕士生，2022年正式入职BIMSA。他是数理逻辑和计算理论领域的国际知名学者，在反推数学和二阶算术领域开创了新的研究方法，如WKLo的田中嵌入定理和守恒结果的田中公式。田中一之教授还致力于模态mu演算，认知逻辑，随机博弈树等交叉领域的研究。详见个人主页 https://sendailogic.com/tanaka.html