Order-Invariance in the Two-Variable Fragment of First-Order Logic

Julien Grange

We study the expressive power of the two-variable fragment of order-invariant first-order logic. This logic departs from first-order logic in two ways: first, formulas are only all…