Stone duality in logic and computer science

MSc Logic Project, January 2018

Final presentations

January 31, 13:30-16:30, F2.19, Science Park 107. The five student presentations will constitute a special session of the A|C Seminar. See the webpage of the A|C Seminar for more details. All are welcome.


Date and Time Location Contents Homework
Mon 8 Jan, 10:30-12:30 F3.20 Project Introduction; Sections 1.1, 1.2, 1.3 up to Lemma 1.12. Sec. 1.1: 2, 3, 4, 5*, 6*, 8;
Sec. 1.2: 10, 12(a), 12(b)+, 13(a)-(e)*, (f)+, 15, 18+, 19*;
Sec. 1.3: 20, 21(a)-(c), (d)+
Typos / Feedback for 1.1 and 1.2.
Tue 9 Jan, 10:30-12:30 F1.15 Section 1.3, Some general remarks on Duality, Section 2.1. Last time's homework, and
Sec. 1.3: 22, 23*, 24*, 26 (separate file in Dropbox);
Sec. 2.1: 1+, 3+, 5*, 6+, 9* (give a reference);
Typos / Feedback for 1.3 and 2.1.
Thu 11 Jan, 15:30-17:30 F3.20 Section 2.3, with outline of 2.2 and 2.4; Section 3.1. Sec 2.2: 11, 15;
Sec 2.3: 16, 18, 19;
Sec 3.1: 4, 5, 7;
Typos / Feedback for Chapter 2 and 3.1.
Fri 12 Jan, 13:30-15:30 F3.20 Section 3.1 and 3.2. Sec 3.1: 8;
Sec 3.2: 10, 11, 12* (f is optional).
Mon 15 Jan, 10:30-12:30 F2.19 Recap of last week in Category-Theoretic Language; Completeness of classical propositional logic; Duality for Operators on finite distributive lattices. Catch up with old homework.
Tue 16 Jan, 10:30-12:30 F2.19 Operators on distributive lattices; Completeness of modal logic; Completeness of classical predicate logic. Problem set (in Dropbox)
Tue 16 Jan, 15:00-17:00 F2.01 Exercise Session
Thu 18 Jan, 10:30-12:30 F2.19 Applications of duality to CS part 1: Languages, automata, monoids, Schutzenberger's Theorem (slides in Dropbox) Submit list of three choices for individual paper (see Dropbox) before Friday 5pm
Fri 19 Jan, 10:30-12:30 F2.19 Applications of duality to CS part 2: Varieties, Profinite monoids, Recent applications (slides in Dropbox) Problem set (in Dropbox)
Week of 22 Jan - 26 Jan See Dropbox Individual Meetings Prepare Presentations
Mon 29 Jan, 12:30-14:00 SP 904 D1.111 Practice Presentations
Tue 30 Jan, 10:30-12:30 F2.19 Practice Presentations
Wed 31 Jan, 13:30-16:30 F2.19 Final Presentations (A|C Seminar)
Fri 2 Feb, 17:00 Deadline for submitting final report


Project description

Instructor. Sam van Gool

Content. Stone duality is a mathematical theory which provides the underpinning for the fundamental connection between syntax and semantics in logic and computer science. The theory has been applied in a variety of settings: modal, intuitionistic, multi-valued and predicate logic; topology of non-Hausdorff spaces; and, recently, automata and (pro)finite monoids.
This project invites students to dive into (some of) these recent applications of Stone duality and its generalizations. Students will also gain experience reading and presenting research papers in the area, and active participation in this project could lead students to research directions suitable for a Master's thesis.
The first half of this project will be an intensive tutorial course on Stone duality and its connections to logic and computer science. The second half will take the form of a reading seminar: students will choose an application of Stone duality from the literature to study on their own. For this part, students' own interests and input will be welcomed and will influence the direction we take. The third week will be reserved for progress meetings, individually or in small groups. In the final week, students will each present their assigned papers to the group.

Organisation. 16 hours of interactive lectures during the first two weeks; schedule for last two weeks TBD. First meeting January 8 at 10:30am.

Assessment. (1) Active participation; (2) Individual presentations; (3) Final project report on tutorial exercises and literature study, to be completed by February 2 at 5pm.

Prerequisites. Required. Familiarity with mathematical logic, at the level of the MSc Logic course "Introduction to Modal Logic" or similar; some degree of mathematical maturity and/or fearlessness.
Preferred but not required. Basic knowledge of (universal) algebra and (point-set) topology at the undergraduate level is helpful (but the necessary mathematical prerequisites will be reviewed in the first part of the course).

Note. Related courses in the MSc Logic are "Mathematical Structures in Logic" (Spring 2017) and "Topics in Modal Logic" (Fall 2017), but these are not prerequisites. Students who took one or both of these courses will have a good basis to build on, but this project will still be of interest to them; there will not be much overlap.

Registration. To register, please send a brief email to the instructor (name without spaces at me dot com), indicating: (1) which of the courses Introduction to Modal Logic, Mathematical Structures in Logic and/or Topics in Modal Logic you took, (2) for planning purposes, any times during which you are not available in January, and (3) in one sentence, your motivation for participating in this project.