You are not logged in | Log in

Compactness in sets with atoms

Speaker(s)
Mikołaj Bojańczyk
Affiliation
Uniwersytet Warszawski
Date
Jan. 9, 2013, 2:15 p.m.
Room
room 5870
Seminar
Seminar Automata Theory

This is another talk about sets with atoms (also known as Fraenkel-Mostowski sets, or nominal sets). Specifically, the topic is the notion of models for formulas of first-order logic. The problem is that a natural definition of a "model" for a formula of first-order logic makes the compactness theorem fail. On a related note, although sets with atoms are a good language to talk finite objects with data (such as data words), the language seems to be less suited to modelling infinite objects. As a solution to these problems, in the talk I will propose a different definition of "model" for first-order logic, together with a sound and complete proof system, which in particular means that the compactness theorem is recovered.