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 $\displaystyle \mathcal{N}\models A(\vec{x})$ iff $\displaystyle \vec{x}\in X$ for all $\displaystyle \vec{x}\in\mathbb{N}^2$.

(2) A represents X *in PA* if

(a) $\displaystyle \mathrm{PA}\vdash A(\vec{x})$ for all $\displaystyle \vec{x}\in X$, and

(b) $\displaystyle \mathrm{PA}\vdash \neg A(\vec{x})$ for all $\displaystyle \vec{x}\notin X$.

Here $\displaystyle \mathcal{N}$ is the standard model of natural numbers, PA is Peano arithmetic, and if $\displaystyle \vec{x}$ is a pair of natural numbers, then $\displaystyle 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."

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.