Describing all infinite models for the sentence $\psi :((P(c) \land \forall x_0(P(x_0) \to P(f(x_0)))) \to \forall x_0 P(x_0))$

Question

I work in a first-order language containing only a unary function symbol $f$, a unary predicate symbol $P$ and a constant symbol $c$. Consider the formula:

$$\psi :((P(c) \land \forall x_0(P(x_0) \to P(f(x_0)))) \to \forall x_0 P(x_0))$$

I'd like to caracterise the structures $< A;f;c >$ where $A$ is infinite and such that for every unary relation $P$ on $A$

$$<A;f;c;P> \vDash \psi$$

I'm confused here, letting $\phi$ be $(P(c) \land \forall x_0(P(x_0) \to P(f(x_0))))$ and $\alpha$ be $\forall x_0 P(x_0)$, we want to make sure that for no $P$ on $A$ we'll have $\phi$ true and $\alpha$ false. When $P(c)$ is false, we're all good but we cannot choose $c$ such that $P(c)$ is false for all $P$. I'm not sure where the infinite size of $A$ has any impact on this... Could you hint me? Am I misunderstanding everything?

Answer 1

Hint:

The axiom of induction is the following: For any formula $\varphi(x)$ $$\Big(\varphi(0)\wedge \forall x\big(\varphi(x)\rightarrow \varphi(x+1)\big)\Big)\rightarrow \forall x\varphi(x)$$

So in some sence your question regards models which satisfy the induction axiom with respect to the function $f$ and constant $c$. Thus clearly the natural numbers together with $f(x)= x+1$ and $c=0$ is a model satisfying $\psi$ for any $P$. However, how may other models look like? Note that If we take two disjoint copies of the natural numbers together with $f(x)=x+1$ and $c=0$ (in one of the copies), then this will not satisfy $\psi$ for some special $P$.

What is special about $x+1$ and 0?

Note that applying $f$ to an element and iterating can only take us a finite amount of steps away from $c$. Thus the following question arrise:

Can we have an uncountable model?

Do note the quite important difference between the regular induction axiom and this question: Here $P$ is any new unary relation which we add, while in the induction axiom $\varphi(x)$ needs to be a formula in the language.

Edit:

Could we have that $f(a)= c$ for some element $a$ in the structure?

Answer 2

Any such structure must be isomorphic to $(\Bbb{N}, 0, x \mapsto x + 1)$. To see this define $P(x)$ to hold iff for some $n \in \Bbb{N}$, $x = f^n(c)$. Then $P(c)$ and $\forall x (P(x) \to P(f(x))$ hold, so by $\psi$, $P(x)$ holds for all $x \in A$. So the function $g$ defined by $g(n) = f^n(c)$ maps $\Bbb{N}$ onto $A$. But then, if $A$ is infinite, $f$ must be one-to-one, because if not, as $g$ is onto $A$, $f(g(m)) = f(g(n))$ for some $m < n \in \Bbb{N}$ and then $A$ would have at most $n+1$ elements.