Is there any recursively axiomized system with infinitely many proofs for some propositions or a proposition? So we will have at least one proposition which is deduced from the recursively axiomatic system in infinite ways.Could any one give an example or proof?


**EDIT**:We define a proof or a reduced proof as one which could not omit any proposition in the arguments,otherwise would be invalid. Or we can view it as question of formal language,that is :is there a formal language with at least one word which can be parsed in infinitely many ways?Of course there have to be no rewriting like "irrelevent padding or stupid detours"



Is there  an recursively axiomatized system with infinitely many proofs for some propositions or a proposition
How about the theorem "There exists at least one prime number?" There are infinitely many distinct proofs of this result, none of which includes another as a subproof. Certainly this example is trivial in some sense, but I think it is not obvious how to pin down why this shouldn't be counted.


Perhaps a better example is "There is at least one Turing machine which halts." Now - in a precise sense - any possible logical deduction is paralleled by a proof that some specific machine halts, so if there are infinitely many "distinct" deductions at all, then there are infinitely many "distinct" proofs of this proposition.


EDIT: This is entirely tangential, but I think you may find it interesting. There is a strong and fruitful tradition in mathematical logic - especially on the constructive side - of drawing analogies between (or equating) proofs and algorithms; so an at-least-vaguely related question is, "How do we tell if two algorithms are the same?" This paper (<http://research.microsoft.com/en-us/um/people/gurevich/Opera/192.pdf>) by Andreas Blass, Nachum Dershowitz, and Yuri Gurevich argues that there is no entirely satisfactory answer to this question. I think at least one thing to take away from this is that one should not be cavalier about the notion of "distinct proof": finding a satisfactory such notion would be a huge advancement in logic!


