of the (finite) satisfiability problem of the logic where some relation symbols are interpreted by transitive relations, equivalence relations, linear orders, successor relations and preorders (see e.g. [@Otto01; @KieronskiT09; @Manuel10; @BojanczykDMSS11; @KieronskiO12; @SchwentickZ12; @ManuelZ13; @SzwastT13; @KieronskiMPT14]).

We establish the decidability of order-invariance for two-variable logic.

Order-invariance of ${\ensuremath{\mathrm{FO}^2}\xspace}$ is decidable.

The key to our main result is a simple observation which relates the problem to a satisfiability problem on ordered structures. A ${\ensuremath{\mathrm{FO}^2}\xspace}$-sentence $\varphi$ is *not* order-invariant if and only if there are a structure and two linear orders on its domain which are distinguished by $\varphi$. More precisely, $\varphi$ is *not* order-invariant if and only if there are two linear orders $<_{1}$ and $<_{2}$ on a finite set $D$ and a tuple of relations $\bar R$ on $D$ that interprets all relation symbols in $\varphi$ except for $<$ such that $(D,\bar R,<_{1}) \models \varphi$ and $(D,\bar R, <_{2}) \not\models \varphi$. The latter statement can be seen as a satisfiability question for a sentence of the *two-variable fragment of existential second-order logic* (${\ensuremath{\mathrm{ESO}^2}\xspace}$) on finite ordered $(<_{1},<_{2})$-structures. Here, a -structure is *ordered* if $<_{1}, <_{2}$ are interpreted by linear orders. Thus, if the finite satisfiability problem for ${\ensuremath{\mathrm{ESO}^2}\xspace}$ is decidable 