Content deleted Content added
m →References: rm dup ref w less specific info |
Citation bot (talk | contribs) Alter: pages, chapter-url. URLs might have been anonymized. Add: archive-date, archive-url. Formatted dashes. | Use this bot. Report bugs. | #UCB_CommandLine |
||
| (5 intermediate revisions by 4 users not shown) | |||
Line 1:
{{short description|Formalization of the natural numbers}}
'''Primitive recursive arithmetic''' ('''PRA''') is a [[Quantification (logic)|quantifier]]-free formalization of the [[natural numbers]]. It was first proposed by Norwegian mathematician {{harvtxt|Skolem|1923}},<ref>reprinted in translation in {{harvtxt|van Heijenoort|1967}}</ref> as a formalization of his [[finitist]]ic conception of the [[foundations of mathematics|foundations of arithmetic]], and it is widely agreed that all reasoning of PRA is finitistic. Many also believe that all of finitism is captured by PRA,{{sfn|Tait|1981}} but others believe finitism can be extended to forms of recursion beyond primitive recursion, up to [[epsilon zero (mathematics)|ε<sub>0</sub>]],{{sfn|Kreisel|1960}} which is the [[proof-theoretic ordinal]] of [[Peano arithmetic]].<ref>{{harvtxt|Feferman|1998|p=4 (of personal website version)}};
The language of PRA can express arithmetic propositions involving [[natural number]]s and any [[primitive recursive function]], including the operations of [[addition]], [[multiplication]], and [[exponentiation]]. PRA cannot explicitly quantify over the ___domain of natural numbers. PRA is often taken as the basic [[metamathematic]]al [[formal system]] for [[proof theory]], in particular for [[consistency proof]]s such as [[Gentzen's consistency proof]] of [[first-order arithmetic]].
Line 136:
|year=1967
|orig-year=1923
|editor-first=Jean
|editor-last=van Heijenoort
|editor-link=Jean van Heijenoort
|pages=302–333
|last=Skolem
|first=Thoralf
|mr=0209111
|publisher=Harvard University Press|ref=CITEREFvan_Heijenoort1967}} {{IAp|https://archive.org/details/fromfregetogodel0025unse/page/302/mode/2up}}
*{{cite journal
|last= Tait
Line 168 ⟶ 166:
|title= Epistemology versus Ontology
|pages=161–180
|chapter-url=
|doi=10.1007/978-94-007-4435-6_8
|archive-url= https://web.archive.org/web/20240524221357/https://home.uchicago.edu/~wwtx/PRA2.pdf
|archive-date= 24 May 2024
}}
| |||