Logic Seminar

The back-and-forth relations, arising from the Ehrenfeucht-Fraisse games, are a central tool of countable structure theory. Each play of the Ehrenfeucht-Fraisse games takes two quantifiers, a universal quantifier and an existential quantifier, and so defining back-and-forth equivalence at the nth level takes 2n alternations of quantifiers. We will consider several situations in which this upper bound is sharp, and see how understanding this phenomenon has interesting applications, e.g., to degree spectra and to continuous reducibility between isomorphism equivalence relations.