| Meetings | TTh 1:00-2:30, 2-146 |
|---|---|
| Instructor | Eric Rosen |
| Office | 2-279 |
| rosen (at) math (dot) mit (dot) edu | |
| Office Hours | Tuesday 2:30 - 3:30, Wednesday 3:00 - 4:00, and by appointment. |
| Prerequisites | 18.100, 18.700, or 18.701. The course will be essentially self-contained, though some prior exposure to formal logic and/or complexity theory would be helpful. |
| Description |
Classical model theory investigates properties of mathematical
structures, e.g., the natural numbers, groups, rings, graphs, that are
expressible in first-order logic. Traditionally, the focus has been on
infinite structures, such as the field of real numbers. An interesting
new direction has been the development of finite model theory, concerned
with classes of finite structures that can be defined in various logical
languages, including, for example, second-order logic or logics with
recursion operators.
One of the first significant discoveries was that there are close connections between logical languages and complexity classes, such as P and NP. There are also interesting relations between logical languages and languages recognized by finite automata. In fact, theoretical computer science has been a major source of inspiration in the field. But there are also important connections with areas of combinatorics, such as the theory of random graphs, and other areas of pure math, such as algebra. More information about finite model theory can be found here. |
| Calendar | Here is the course schedule. |
| Text | Elements of Finite Model Theory, by
Leonid Libkin.
Information about the book can be found on amazon.
You can also find information here about books on reserve and some online references for basic logical background. |
| Format | The course will be seminar format, which means that classes will consist of student presentations. Participants will also be required to write a ten page paper, in LaTeX, on a related topic. |
| Grading | Grades will be based on class presentations (40%), homework (20%), and the final paper (40%). |
| Paper | Information about the final project
can be found here.
Here are some student papers from the seminar. |
| Homework | Students are permitted to discuss homework with each other, but must write up their own solutions in their own words. Problem sets should be handed in at the beginning of class on the day that they are due. |
Last updated June 2008