1. Is this relation recursive?

Suppose 'Fx' is a unary recursive relation. Also suppose that (∃x)Fx is a consequence of the standard model for number theory. Is the function on natural numbers f recursive that returns 0 if
Fn and, for m < n, Fm is not a consequence of the standard model
and returns 1 otherwise?

2. Re: Is this relation recursive?

Welcome to the forum.

Originally Posted by MLP
Is the function on natural numbers f recursive that returns 0 if
Fn and, for m < n, Fm is not a consequence of the standard model
and returns 1 otherwise?
What is the argument of f? Is it n?

3. Re: Is this relation recursive?

Originally Posted by emakarov
Welcome to the forum.

What is the argument of f? Is it n?
Thanks for the welcome. I apologize, yes the argument of f is n.

4. Re: Is this relation recursive?

Since $\displaystyle Fx$ is recursive, one can check for each number $\displaystyle n$ whether $\displaystyle \mathbb{N}\models Fn$ and $\displaystyle \mathbb{N}\models \forall m < n\,\neg Fm$. So yes, $\displaystyle f$ is recursive. The assumption that $\displaystyle \mathbb{N}\models\exists x\,Fx$ is not used here.

This question is more suitable for the Discrete Mathematics, Set Theory and Logic section of the forum.