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].
Lecturer
Date
2nd March ~ 29th June, 2026
Location
| Weekday | Time | Venue | Online | ID | Password |
|---|---|---|---|---|---|
| Monday | 15:20 - 17:50 | A3-2-301 | ZOOM 08 | 787 662 9899 | BIMSA |
Prerequisite
"Logic and Computation I (AU2024), II (SP2025)" or equivalent knowledge of mathematical logic and theory of computation.
Syllabus
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.
Reference
[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.
Audience
Advanced Undergraduate
, Graduate
, Postdoc
Video Public
No
Notes Public
Yes
Language
English
Lecturer Intro
Kazuyuki Tanaka received his Ph.D. from U.C. Berkeley. Before joining BIMSA in 2022, he taught at Tokyo Inst. Tech and Tohoku University, and supervised fifteen Ph.D. students. He is most known for his works on second-order arithmetic and reverse mathematics, e.g., Tanaka's embedding theorem for WKLo and the Tanaka formulas for conservation results. For more details: https://sendailogic.com/tanaka.html