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?



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.


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

  • $\begingroup$ If P is "is the the copy #1 of $\mathbb{N}$ then I see that it doesn't work. Can we say that the image of $f$ needs to be countable for any $f$? So $A$ needs to be countable, as otherwise we could construct a $P$ such that the sentence isn't true a bit like we did in the 'two copies of $\mathbb{N}$' example. Would that condition on $A$ be sufficient? $\endgroup$ – Kika Nov 25 '15 at 9:25
  • $\begingroup$ We also need $f$ to be surjective don't we? $\endgroup$ – Kika Nov 25 '15 at 9:42
  • $\begingroup$ Well, yes, although it needs some proof to conclude, we may only have countable models. There are quite some more conditions needed (especially on $f$ and its interaction with $c$) in order to conclude this. However $f$ actually may not be surjective. (I edited in a third hint in the answer above) $\endgroup$ – Ove Ahlman Nov 25 '15 at 9:47
  • $\begingroup$ I see now! Thank you so much! $\endgroup$ – Kika Nov 25 '15 at 11:59
  • $\begingroup$ $f(a) = c$ is not possible. See my answer. $\endgroup$ – Rob Arthan Nov 25 '15 at 22:38

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.