Transitivity and Equivalence in Two-Variable First-Order Logic

Speaker(s)

Ian Pratt-Hartmann

Affiliation

School of Computer Science University of Manchester

Date

Jan. 16, 2019, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

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.

---