Define a signature Σ and an FO+TC formula ϕ over Σ, such that:
- there is no infinite structure satisfying ϕ
- for every even natural number n>0 there is a structure of size n satisfying ϕ
- for every odd natural number m>0 there is no structure of size m satisfying ϕ.
FO+TC is First-order logic with transitive closure, for example you can have formula $\phi := TC{a,b}(b = a + a)(x,y)$ which can be translated to $y = 2^n * x$
using transitive closure we can define the natural numbers or define a path in graph
There are several possibilities. For example, you could decide that your structure should be a cyclic group of even order.
"Group" is a well-known (finitely axiomatized) first-order theory.
Requiring an element of order 2 will prevent it from having odd order, by Lagrange's theorem.
And your transitive-closure operator allows you to express that there's an element that generates the group (by positive powers only).
Alternatively, your structure could be a strongly connected bipartite directed graph where every node has out-degree 1 (which is to say, a cycle of even length -- though that needs to be proved).
Or it could be a discrete linear order with maximal and minimal element where every two elements are a finite distance from each other, and structures are forced to have even size by a separate relation that pairs the elements up two by two.