Following this conception, we say that an element $a$ is to the *left* or *right* of an element $b$ if $a <_1 b$ or $b <_1 a$, respectively, and that it is *below* or *above* $b$ if $a <_2 b$ or $b <_2 a$. Accordingly, we will speak of *leftmost* and *rightmost* elements.

Two-Variable Logic
------------------

The *two-variable fragment of first-order logic* (short: ${\ensuremath{\mathrm{FO}^2}\xspace}$) is the restriction of first-order logic where only two variables can be used, though those two variables can be quantified multiple times. The *two-variable fragment of existential second-order logic* (short: ${\ensuremath{\mathrm{ESO}^2}\xspace}$) consists of all formulas of the form $\exists \bar R \varphi$ where $\bar R$ is a tuple of relation variables and $\varphi$ is a ${\ensuremath{\mathrm{FO}^2}\xspace}$-sentence. Since each ${\ensuremath{\mathrm{FO}^2}\xspace}$-atom can contain at most two variables we assume, in the entire article and without loss of generality, that all relation symbols are of arity at most two; see [@GradelKV97 page 5] for a justification.

Two ${\ensuremath{\mathrm{ESO}^2}\xspace}$-sentences $\psi$ and $\psi'$ are *${{\cal K}\xspace}$-equivalent* for a class of structures ${{\cal K}\xspace}$, if ${\ensuremath{\mathfrak{A}}}\models \psi$ if and only if ${\ensuremath{\mathfrak{A}}}\models \psi'$ for all structures ${\ensuremath{\mathfrak{A}}}\in {{\cal K}\xspace}$. An ${\ensuremath{\mathrm{ESO}^2}\xspace}$-sentence is *satisfiable on a class of structures ${{\cal K}\xspace}$* if it 