-1
$\begingroup$

How does one generally show syntactical statements in PA about primitive recursive functions or relations?

For example something like:

Let $A$ be a prim. rec. relation such that $n\in A$ for every numeral $n$. Show $PA \vdash \forall x A(x)$ (where $A$ denotes the relation as well as the formula representing the relation in PA).

Improve this question
$\endgroup$
4
  • $\begingroup$ Uh? Often by induction, sometimes in the flavor of a recursion: show that $\forall x\,A(x)=0$ by showing that $A(0) = 0$ and $A(x+1) = F(x,A(x))$ where $\foral x\,F(x,0) = 0$... $\endgroup$
    – François G. Dorais
    Commented May 30, 2012 at 22:24
  • 1
    $\begingroup$ Please don't alter the question to become void. If you really want to delete, use the "delete" option $\endgroup$
    – Yemon Choi
    Commented May 30, 2012 at 23:36
  • 1
    $\begingroup$ Yemon, unregistered users cannot delete their own questions and it is impossible to delete questions with upvoted answers. $\endgroup$
    – Asaf Karagila ♦
    Commented May 31, 2012 at 6:03
  • 1
    $\begingroup$ Sorry. I just found this website, then asked a question, then read the faq, then decided that my question is too basic and tried to delete it. The answers were helpful nevertheless. $\endgroup$
    – AGISGA
    Commented May 31, 2012 at 14:32

2 Answers 2

Reset to default
2
$\begingroup$

Sometimes you can't prove what you asked for. For example, it is routine to give a primitive recursive definition of the predicate $A(x)$ formalizing in a natural way "$x$ is not the Gödel number of a proof in PA of a contradiction." Then, for each natural number $n$, this predicate holds of $n$ (because PA is consistent). But PA cannot prove $\forall x\,A(x)$, because, by Gödel's second incompleteness theorem, PA cannot prove its own consistency.

Improve this answer
$\endgroup$
0
$\begingroup$

Examine why $A$ is primitive recursive. The proof in PA should parallel the informal proof that it is primitive recursive.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .