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
Re: Help with first order peanos arithemtic
Quote:
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
iff
for all
.
(2) A represents X in PA if
(a)
for all
, and
(b)
for all
.
Here
is the standard model of natural numbers, PA is Peano arithmetic, and if
is a pair of natural numbers, then
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."
Quote:
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.