I'm trying to solve the following problem, and I'm getting stuck.
Let $L = \lbrace f, c, P\rbrace$ be a first-order language containing as non-logical symbols the unary function symbol $f$, the constant symbol $c$, and a unary predicate symbol P.
Let $\psi =$ $\big(P(c)\wedge\forall x(P(x)\rightarrow P(f(x))\big)\rightarrow\forall xP(x)$
Characterise those $L-$structures $\mathcal{A} =< A; f_\mathcal{A}; c_\mathcal{A} > $where the domain A is an infinite set, and where for every unary relation $P_\mathcal{A}$ on A, $< A; f_\mathcal{A}; c_\mathcal{A}; P_\mathcal{A} > \models \psi$.
I've tried thinking about what might make $\psi$ false for some $P_\mathcal{A}$, so I know what kind of $L-$structures don't work, but I keep getting confused.
Obviously $\psi$ will come out false for some $P_\mathcal{A}$ iff $c_\mathcal{A}\in P_\mathcal{A}$, there is some $x_0 \notin P_\mathcal{A}$, and $x \in P_\mathcal{A} \implies f(x)\in P_\mathcal{A}.$
What I can't work out are which functions - given all $P_\mathcal{A}$ such that $c_\mathcal{A}\in P_\mathcal{A}$and there is some $x_0 \notin P_\mathcal{A}$ - will have $f(x)\notin P_\mathcal{A}$ for some $x\in P_\mathcal{A}$. This is the result I'd need to ensure that there is no unary function $P_\mathcal{A}$ such that $\psi$ comes out false, but I have no idea what such a function would look like.
Any help you could offer/alternative approaches you can think of would be greatly appreciated.
As Mauro pointed out in a comment, one obvious structure that satisfies this condition is $(\mathbb{N}, 0, S)$ where $S$ denotes the successor function: $x \mapsto x + 1$. But actually there are some other structures that also satisfy this condition.
Here's one way to go about figuring out the answer. First try to prove that any such structure $\mathcal{A}$ is isomorphic to $(\mathbb{N}, 0, S)$. This proof won't quite work (because the statement is false) but the place where it goes wrong will show you what the other possibilities are.
Here's how you might go about trying to prove that $\mathcal{A}$ is isomorphic to $\mathbb{N}$. Define a map $F\colon \mathbb{N} \to A$ by induction on $\mathbb{N}$ as follows: $F(0) = c_\mathcal{A}$ and $F(n + 1) = f_\mathcal{A}(F(n))$. To show this is an isomorphism there are a few things to check.
The first point is more or less clear by the definition of $F$ (you could show it formally by induction on $\mathbb{N}$). To prove $F$ is surjective, try letting $P$ be the unary predicate on $A$ that picks out the range of $F$.
The problem comes when you try to show $F$ is injective. If $F$ is not injective then for some $n \neq m$ we have $F(n) = F(m)$. In other words, $n$ successive applications of $f_\mathcal{A}$ to $c_\mathcal{A}$ is not equal to $m$ successive applications. Try to figure out what the structure $\mathcal{A}$ has to look like in this case (and keep in mind that the map $F$ is still a surjection).