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.

Schedule

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

Notes.

There may be changes in the schedule, please check this page regularly.
All rooms are in building SP107, unless noted otherwise.
* Starred exercises are particularly important, and their results may be used in the course.
+ Plussed exercises are optional.
Lecture Notes are available in the Dropbox shared with participants. As part of the homework, every participant will annotate the lecture notes with typos and/or other feedback. Annotations can be made either in the paper copy in Sam's mailbox, or digitally in Dropbox.

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: mo dal, intuit ionistic, multi-valued and pre dic ate 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.

References.

Mai Gehrke, Duality, inaugural speech, Radboud University Nijmegen, 2009.
A general introduction to Stone duality, written with a broad, non-mathematical audience in mind.
Sam van Gool, Machines, Models, Monoids, and Modal logic (version with animations), TbILLC tutorial, 2017.
Slides introducing some of the more advanced research topics that we will look at in this project. Also see the further references in these slides.
Lecture notes for the first part will be made available during the course.
Click the links in the first paragraph above for a sample of relevant books and research articles. A definitive list will be compiled during the project, based on students' input.