Results 1 to 4 of 4

Math Help - 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,501
    Thanks
    765

    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,501
    Thanks
    765

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

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum