Beijing Institute of Mathematical Sciences and Applications Beijing Institute of Mathematical Sciences and Applications

  • About
    • President
    • Governance
    • Partner Institutions
    • Visit
  • People
    • Management
    • Faculty
    • Postdocs
    • Visiting Scholars
    • Staff
  • Research
    • Research Groups
    • Courses
    • Seminars
  • Join Us
    • Faculty
    • Postdocs
    • Students
  • Events
    • Conferences
    • Workshops
    • Forum
  • Life @ BIMSA
    • Accommodation
    • Transportation
    • Facilities
    • Tour
  • News
    • News
    • Announcement
    • Downloads
About
President
Governance
Partner Institutions
Visit
People
Management
Faculty
Postdocs
Visiting Scholars
Staff
Research
Research Groups
Courses
Seminars
Join Us
Faculty
Postdocs
Students
Events
Conferences
Workshops
Forum
Life @ BIMSA
Accommodation
Transportation
Facilities
Tour
News
News
Announcement
Downloads
Qiuzhen College, Tsinghua University
Yau Mathematical Sciences Center, Tsinghua University (YMSC)
Tsinghua Sanya International  Mathematics Forum (TSIMF)
Shanghai Institute for Mathematics and  Interdisciplinary Sciences (SIMIS)
BIMSA > Logic and Computation I \(ICBS\)
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.
Professor Lars Aake Andersson
Lecturer
Kazuyuki Tanaka
Date
10th September ~ 10th 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.
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.
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
Beijing Institute of Mathematical Sciences and Applications
CONTACT

No. 544, Hefangkou Village Huaibei Town, Huairou District Beijing 101408

北京市怀柔区 河防口村544号
北京雁栖湖应用数学研究院 101408

Tel. 010-60661855
Email. administration@bimsa.cn

Copyright © Beijing Institute of Mathematical Sciences and Applications

京ICP备2022029550号-1

京公网安备11011602001060 京公网安备11011602001060