Logic: building a sentence

Question

Let $L$ be a language with a 1-place function symbol $f$. Give an $L$-sentence $\phi$ that is true in every $L$-structure $M$ if the following holds: if $M \models \phi$, then $M$ is infinite.

My idea is to construct a sentence that, given $n$ different variables, all the values of those variables under the evaluation of $f$, must be different. Is this a good way to start? Any help will be much appreciated!

Edit

Now, to work further with the given hints, the answer should be a sentence which states that all the elements $f(x),f(f(x)), \dots$ are different. But this is not finitely axiomatizable, or is it?

Answer 1

Hint: Write down a sentence which ensures that $f$ is successor-like (there's a `zero' element which isn't an $f$ successor; every element has an $f$ successor; different elements have different $f$-successors ...).

Added $\forall x\forall y(fx = fy \to x = y)$ tells you that different elements have different $f$-successors. From which it follows, using $n$ applications, that if $f^m(0) = f^n(0)$, with $m \geq n$, then $f^{(m - n)}(0) = 0$ which implies $m = n$ since the zero isn't an $f$-successor. So indeed $0, f(0), f^2(0), f^3(0), \ldots$ are all different.

Answer 2

Hint:

• What you would like to do is to ensure that $x, f(x), f(f(x)), \ldots$ are different elements.
• The simplest way to do it is to disallow any loops in the above sequence (it might be hard to deal with some other loops somewhere else, but that does not concern you).

I hope this helps $\ddot\smile$