Results 1 to 4 of 4

Thread: Is this relation recursive?

  1. #1
    MLP
    MLP is offline
    Newbie
    Joined
    Dec 2011
    Posts
    3

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    Re: Is this relation recursive?

    Welcome to the forum.

    Quote Originally Posted by MLP View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MLP
    MLP is offline
    Newbie
    Joined
    Dec 2011
    Posts
    3

    Re: Is this relation recursive?

    Quote Originally Posted by emakarov View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: Apr 6th 2011, 11:46 PM
  2. Recursive relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jul 20th 2010, 10:59 PM
  3. Replies: 4
    Last Post: Apr 27th 2010, 07:57 AM
  4. Replies: 1
    Last Post: Mar 1st 2010, 07:24 AM
  5. Primitive Recursive vs Recursive Functions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Jan 29th 2009, 07:32 AM

Search Tags


/mathhelpforum @mathhelpforum