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.

---