You are not logged in | Log in

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.