1
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Your candidate sentence works perfectly. Re: verification, I think with problems like this it's easy to start second-guessing oneself. Let me propose the following hints (the motto being "don't try too hard"):

  • Show that a (finite) set is even iff it can be written as a disjoint union of two-element sets (more simply: iff it can be partitioned into pairs).

  • 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?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .