# First order sentence only satisfiable in finite models if domain has an even number of elements

As the title says, I'm trying to find a first order sentence for which all finite models which satisfy it have a domain with an even number of elements and for which every finite set with an even number of elements is the domain of some model of the sentence.

The problem I'm attempting requires that I do this in the language $$L=\{ f\}$$ where $$f$$ is a unary function and is the only non-logical symbol (so I can't use any relations).

One option I think might only be satisfiable by even sets is the sentence $$\forall x ((f(f(x))=x) \land\neg(f(x)=x))$$, but I'm not sure how I'd go about explaining no model with an odd finite domain could satisfy it.

Any help would be really appreciated.

• Now suppose $$M$$ satisfies your sentence. Can you think of a way to use $$f$$ to break $$M$$ into a bunch of pairs?
• (HINT: can you show that $$M$$ satisfies $$\forall x,y[f(x)=f(y)\iff x=y]$$? This is really the key part of the verification.)
• Finally, you need to show that your sentence has a model of size $$2k$$ for every positive integer $$k$$. Consider (for example) the set $$\{0,1\}\times \{1,2,...,k\}$$ - do you see a way to turn this into a model of your sentence?