Note on a Translation from First-Order Logic into the Calculus of Relations Preserving Validity and Finite Validity
Yoshiki Nakamura · Fundamenta Informaticae · 2025
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.