MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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).

share|cite|improve this question

closed as no longer relevant by Dan Petersen, Andy Putman, Qiaochu Yuan, Gjergji Zaimi, Asaf Karagila May 30 '12 at 23:02

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

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$... – François G. Dorais May 30 '12 at 22:24
Please don't alter the question to become void. If you really want to delete, use the "delete" option – Yemon Choi May 30 '12 at 23:36
Yemon, unregistered users cannot delete their own questions and it is impossible to delete questions with upvoted answers. – Asaf Karagila May 31 '12 at 6:03
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. – AGISGA May 31 '12 at 14:32
up vote 2 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.