# Thread: Is this relation recursive?

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 $Fx$ is recursive, one can check for each number $n$ whether $\mathbb{N}\models Fn$ and $\mathbb{N}\models \forall m < n\,\neg Fm$. So yes, $f$ is recursive. The assumption that $\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.