A tagged $d$-dimensional first-order interpretation of a relational vocabulary $L'$ in a vocabulary $L$ maps an $L$-structure with universe $A$ to the $L'$-structure with universe $\mathrm{Tag} \times A^d$, in which an $n$-ary symbol $R$ holds of the tagged tuples $(t_1, \bar a_1), \dots, (t_n, \bar a_n)$ exactly when the first-order $L$-formula chosen for $R$ and the tags $t_1, \dots, t_n$ holds in $A$ of the coordinates $\bar a_1, \dots, \bar a_n$. The tags play the role of the constantly many sorts that textbook reductions carve out of an ordered universe.

A first-order reduction from a problem $P$ to a problem $Q$ is such an interpretation mapping yes-instances of $P$ exactly to yes-instances of $Q$, on every finite nonempty structure. An ordered first-order reduction is one over the expansion of $L$ by a linear order, correct for every linear order put on the input; since $P$ does not depend on the order, neither does whether the image is a yes-instance of $Q$, so the reduction is order-invariant. Both kinds are computable in $\mathrm{AC}^0$ on encodings of finite structures, hence in particular polynomial-time many-one reductions; this standard fact is not part of the formalization.