Is there a first-order formula expressing this property? Suppose $R$ is a binary relation on $\{0,1\}^*$ (where $\{0,1\}^*$ is the set of all finite words over the alphabet $\{0,1\}$), and suppose that for all $x \in \{0,1\}^*$, the number of $y$ such that $x \mathrel{R}y$ is finite.
Is there a formula $\phi(x)$ in first-order logic (using only the relation $R$ and the lexicographic order on $\{0,1\}^*$) such that $\phi(x) \iff \text{there is an even number of } y \text{ such that } x \mathrel{R} y$?
 A: There is no such first-order formula. By contradiction, suppose there is a first-order formula $\varphi$ using only the relation $R$ and the lexicographic order $\leqslant_{lex}$ on $\{0,1\}^*$ such that $\varphi(x)$ is true if and only if
$$
\textit{ there is an even number of $y$ such that $x \mathrel{R} y$}.
$$
Let $R$ be the relation on $\{0,1\}^*$ defined as follows:
$$
x \mathrel{R} y \iff \text{$x = 0^n$, $y = 0^m$ and $m < n$}
$$
Observe that the restriction to $0^*$ of the lexicographic order is defined by 
$$ 
0^n \leqslant_{lex} 0^m \iff n \leqslant m,
$$ 
which is equivalent to $\neg (0^n \mathrel{R} 0^m)$. It follows that on $0^*$, any formula of $FO[R, \leqslant_{lex}]$  is equivalent to a formula of $FO[\leqslant_{lex}]$. Moreover $(0^*, \leqslant_{lex})$ is isomorphic to $(\mathbb{N}, \leqslant)$ and the property 
$$
\textit{there is an even number of $y$ such that $0^n \mathrel{R} y$}
$$
simply means that $n$ is even. It follows that if $\varphi$ existed, then the subset of even numbers of $\mathbb{N}$ would be definable in $F0[\leqslant]$. But it is a well-known result that this is not the case. If you prefer a language theoretic argument, you could say that the language $(00)^+$ is not first-order definable since it is not star-free.
