Results 1 to 2 of 2

Math Help - Help with first order peanos arithemtic

  1. #1
    Junior Member
    Joined
    Sep 2010
    Posts
    54

    Help with first order peanos arithemtic

    Let A(c,d) be a first order peano arithmetic formula containing no free variables occurence other than c and d. LLet X be a subset of N^2 ( N is the set of natural numbers)

    What does A(c,d) represent X mean?

    also why does (m,n) element X iff A(m,n) interpreted in the natural way as a statement in number theory is true?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Help with first order peanos arithemtic

    What does A(c,d) represent X mean?
    There are few definitions in mathematical logic that don't vary between textbooks. I see two options.

    (1) A represents X if \mathcal{N}\models A(\vec{x}) iff \vec{x}\in X for all \vec{x}\in\mathbb{N}^2.

    (2) A represents X in PA if
    (a) \mathrm{PA}\vdash A(\vec{x}) for all \vec{x}\in X, and
    (b) \mathrm{PA}\vdash \neg A(\vec{x}) for all \vec{x}\notin X.

    Here \mathcal{N} is the standard model of natural numbers, PA is Peano arithmetic, and if \vec{x} is a pair of natural numbers, then A(\vec{x}) denotes A with corresponding numerals substituted for the variables c, d.

    Basically, representability can be relative to truth in an interpretation or relative to provability in a theory. Representable functions are usually defined relative to provability in PA. See "Computability and logic" by Boolos and Jeffrey, chapter "Representability of Recursive Functions."

    also why does (m,n) element X iff A(m,n) interpreted in the natural way as a statement in number theory is true?
    Under option (1) above this is true by definition.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: May 26th 2011, 05:03 AM
  2. [SOLVED] Re-writing higher order spatial derivatives as lower order system
    Posted in the Differential Equations Forum
    Replies: 11
    Last Post: July 27th 2010, 09:56 AM
  3. Replies: 3
    Last Post: August 25th 2009, 03:07 AM
  4. Replies: 2
    Last Post: February 23rd 2009, 06:54 AM
  5. Replies: 2
    Last Post: November 25th 2008, 10:29 PM

Search Tags


/mathhelpforum @mathhelpforum