Some Results on the Length of Proofs TeX Export

@article{citeulike:5880664, abstract = {Given a theory T, let \$\vdash \_{T}^{k}A\$ mean "A has a proof in T of at most k lines". We consider a formulation \$PA^{\ast}\$ of Peano arithmetic with full induction but addition and multiplication being ternary relations. We show that \$\vdash ^{k}A\$ is decidable for \$PA^{\ast}\$ and hence \$PA^{\ast}\$ is closed under a weak \$\omega \text{-rule}\$ . An analogue of G\"{o}del's theorem on the length of proofs is an easy corollary.}, author = {Parikh, R. J.}, citeulike-article-id = {5880664}, citeulike-linkout-0 = {http://dx.doi.org/10.2307/1996581}, citeulike-linkout-1 = {http://www.jstor.org/stable/1996581}, doi = {10.2307/1996581}, issn = {00029947}, journal = {Transactions of the American Mathematical Society}, pages = {29--36}, posted-at = {2009-10-03 11:37:43}, priority = {2}, publisher = {American Mathematical Society}, title = {Some Results on the Length of Proofs}, url = {http://dx.doi.org/10.2307/1996581}, volume = {177}, year = {1973} }

TY - JOUR ID - citeulike:5880664 L3 - citeulike-article-id:5880664 N2 - Given a theory T, let $\vdash _{T}^{k}A$ mean "A has a proof in T of at most k lines". We consider a formulation $PA^{\ast}$ of Peano arithmetic with full induction but addition and multiplication being ternary relations. We show that $\vdash ^{k}A$ is decidable for $PA^{\ast}$ and hence $PA^{\ast}$ is closed under a weak $\omega \text{-rule}$ . An analogue of Gödel's theorem on the length of proofs is an easy corollary. JF - Transactions of the American Mathematical Society SN - 00029947 EP - 36 TI - Some Results on the Length of Proofs PB - American Mathematical Society VL - 177 SP - 29 AU - Parikh, RJ PY - 1973/// UR - http://dx.doi.org/10.2307/1996581 ER -