Infinitary methods in finite model theory

Add to your list(s) Download to your calendar using vCal

• Lindell, S (Haverford College)
• Friday 30 March 2012, 11:00-11:30
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact Mustapha Amrani.

Semantics and Syntax: A Legacy of Alan Turing

The accepted wisdom is that standard techniques from classical model theory fail to apply in the finite. We attempt to dispel this notion by presenting new proofs of the Gaifman and Hanf locality theorems, as they appear in Libkin’s textbook on finite model theory. In particular, using compactness over an expanded vocabulary, we obtain strikingly simple arguments that apply over both finite and infinite structures—all without the complexity of EhrenfeuchtFrass games normally used. Our techniques rely on internalizing most of the relevant mathematical features into the first-order theory itself. It remains to be seen whether these methods can be extended to proving order-invariant locality.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.