Compactness in sets with atoms

Prelegent(ci)

Mikołaj Bojańczyk

Afiliacja

Uniwersytet Warszawski

Termin

9 stycznia 2013 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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.

---