Transitivity and Equivalence in Two-Variable First-Order Logic

Prelegent(ci)

Ian Pratt-Hartmann

Afiliacja

School of Computer Science University of Manchester

Termin

16 stycznia 2019 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

The notions of transitive relation and equivalence relation number among the most
salient concepts in  logic. On the other hand, it is well-known that these properties are not expressible in various well-known fragments of first-order logic for which the
satisfiability problem is decidable---including the so-called two-variable fragment and its extension with counting quantifiers, as well as their guarded sub-fragments.
The question therefore arises as to what happens to these fragments when certain distinguished binary predicates are constrained to be interpreted as transitive relations or as equivalence relations. This question has been the subject of concerted study in the past few years, and my talk summarizes the current state of play in this area.

---