Penn Arts & Sciences Logo

Logic and Computation Seminar

Monday, September 23, 2024 - 3:30pm

Michael Benedikt

Oxford University

Location

University of Pennsylvania

DRL 4C4

This talk is about a hybrid of finite and infinite model theory, where formulas can reference two kinds of non-logical symbols: there are
``built-in'' or ``interpreted'' symbols, which are interpreted over an infinite structure for a complete background theory -- e.g. real or integer arithmetic. And there are ``uninterpreted relation symbols'' ranging over finite relations living within an infinite model of the theory. The expressiveness of first order logic in this setting was studied in the late 90's and early 2000's, motivated by the real field case, stemming from questions in databases and computational geometry.

Much of this talk will review what was accomplished decades ago.
I'll then present an overview of recent jointwork by myself and Ehud Hrushovski (https://arxiv.org/abs/2304.09231), that begin to progress on the many questions that were left open in decades past.