Logic and Computation I

This is an advanced undergraduate and graduate-level course in mathematical logic and theory of computation. Topics to be presented in the first semester include: computable functions, undecidability, propositional logic, NP-completeness, first-order logic, Goedel's completeness theorem, Goedel's incompleteness theorems, modal logic and its decidability.

In the second semester, we will move on to second-order logic, modal $\mu$-calculus, infinite automata, descriptive set theory, admissible recursion, etc.

In the second semester, we will move on to second-order logic, modal $\mu$-calculus, infinite automata, descriptive set theory, admissible recursion, etc.

Lecturer

Date

10th September ~ 19th December, 2024

Location

Weekday | Time | Venue | Online | ID | Password |
---|---|---|---|---|---|

Tuesday,Thursday | 15:20 - 16:55 | A3-2-301 | ZOOM 08 | 787 662 9899 | BIMSA |

Prerequisite

Completion of undergraduate course on logic, set theory or automata theory is recommended. But all interested students are welcome.

Syllabus

Part 1. Introduction to Computational Theory

Fundamentals on theory of computation and computability theory (recursion theory) of mathematical logic, as well as the connection between them.

This part is the basis for the following lectures.

Part 2. Propositional Logic and Computational Complexity

The basics of propostional logic (Boolean algebra) and complexity theory including some classical results, such as the Cook-Levin theorem.

Part 3. First Order Logic and formal arithmetic

The basics of first-order logic, Goedel's completeness theorem, Goedel's incompleteness theorems, the Ehrenfeucht-Fraisse theorem and Lindstrom's theorem.

Part 4. Modal logic

Kripke models, Kripke-complete and canonical logics, standard translation, bisimulation, decidability results, and epistemic logic. In "Logic and Computation II", we will move on to second-order logic and modal $\mu$-calculus.

Fundamentals on theory of computation and computability theory (recursion theory) of mathematical logic, as well as the connection between them.

This part is the basis for the following lectures.

Part 2. Propositional Logic and Computational Complexity

The basics of propostional logic (Boolean algebra) and complexity theory including some classical results, such as the Cook-Levin theorem.

Part 3. First Order Logic and formal arithmetic

The basics of first-order logic, Goedel's completeness theorem, Goedel's incompleteness theorems, the Ehrenfeucht-Fraisse theorem and Lindstrom's theorem.

Part 4. Modal logic

Kripke models, Kripke-complete and canonical logics, standard translation, bisimulation, decidability results, and epistemic logic. In "Logic and Computation II", we will move on to second-order logic and modal $\mu$-calculus.

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] P. Blackburn, M. de Rijke and Y. Venema, Modal Logic, Cambridge UP, 2002.

[4] K. Tanaka, 計算理論と数理論理学 (Mathematics of Logic and Computation, in Japanese), Kyoritsu 2022.

[2] D.C. Kozen, Theory of Computation, Springer 2006.

[3] P. Blackburn, M. de Rijke and Y. Venema, Modal Logic, Cambridge UP, 2002.

[4] K. Tanaka, 計算理論と数理論理学 (Mathematics of Logic and Computation, in Japanese), Kyoritsu 2022.

Audience

Advanced Undergraduate
, Graduate

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