CSIE 5111: Introduction to Mathematical Logic

       

Instructor

Venue and time

  • Monday, 14:30-17:00, room CSIE 102.

Administration

  • For correspondence, use my CSIE email: tonytan@csie.ntu.edu.tw
  • Please check this website regularly. Course notes and homework will be posted here.
  • All the announcements will also be posted here, as well as in the bulletin of this course in CEIBA.
  • Each homework weighs 25%.

Teaching assistants

  • Ma Yanger (b04902032@ntu.edu.tw), office hour: 15:00-16:00, room 401.
  • If needed, you may try to arrange another time slot with the TA directly.

Recommended textbooks

  • A Mathematical Introduction to Logic by H. Enderton.
  • A Concise Introduction to Mathematical Logic by W. Rautenberg.
  • Mathematical logic by H.-D. Ebbinghaus, J. Flum and W. Thomas.

Syllabus (tentative)

Part Week Dates Lesson Remark
A I 18 Feb. Lesson 1. Preliminaries --
B II 25 Feb. Lesson 2. Compactness theorem for propositional calculus --
III 4 Mar. Lesson 3. Proof system in propositional calculus HW 1 out.
IV 11 Mar. Lesson 4. Completeness of propositional calculus --
C V 18 Mar. Lesson 5. First-order logic (FO) part I --
VI 25 Mar. Lesson 6. First-order logic (FO) part II HW 1 due. HW 2 out.
VII 1 Apr. -- --
D VIII 8 Apr. Lesson 7. Logical consequences and theories --
IX 15 Apr. Lesson 8. Proof system in FO HW 2 due.
X 22 Apr. Lesson 9. Gödel's completeness theorem --
XI 29 Apr. Lesson 10. Löwenheim-Skolem theorem and categorical sets HW 3 out.
XII 6 May -- --
E XIII 13 May Lesson 11. Gödel's incompleteness theorem part. I --
XIV 20 May Lesson 12. Gödel's incompleteness theorem part. II HW 3 due.
XV 27 May Lesson 13. Decision problems in FO HW 4 out.
XVI 3 Jun. Lesson 14. Some topics in logic in computer science --
XVII 10 Jun. -- --
XVIII 17 Jun. -- HW 4 due (on Friday).

Notes on homework submission

  • You should write down your class number, your student number and your name in your homework solution.
  • Homeworks will be posted here on Mondays in the indicated week.
  • Their due dates are also always on Mondays before the class starts in the indicated week.
  • You can submit your homework earlier than the due date by slipping it under the door of my office.
  • Homework solution has to be handwritten or typewritten in a format that will be determined later.
  • The tidiness of your homework contributes to your grade.
  • Discussions/collaborations are allowed, but make sure that you acknowledge that you do your homeworks in collaboration and that you understand and write down your own solutions.
  • Points will be deducted if you don't understand your own solutions.