Note on a Translation from First-Order Logic into the Calculus of Relations Preserving Validity and Finite Validity

Abstract

In this note, we give a linear-size translation from formulas of first-order logic into equations of the calculus of relations preserving validity and finite validity. Our translation also gives a linear-size conservative reduction from formulas of first-order logic into formulas of the three-variable fragment of first-order logic.