Over words, two variables are as powerful as one quantifier alternation

Abstract

We show a property of strings is expressible in the two-variable fragment of fist-order logic if and only if it is expressible by both a Cs and a II2 sentence. We thereby establish: