Primitive recursive arithmetic: Difference between revisions

Browse history interactively

← Previous edit

Content deleted Content added

VisualWikitext

Revision as of 14:54, 12 April 2025 edit 160.39.125.168 (talk) No edit summary Tags: Reverted harv or sfn error ← Previous edit		Latest revision as of 23:13, 6 July 2025 edit undo Citation bot (talk \| contribs) Bots 5,862,077 edits Alter: pages, chapter-url. URLs might have been anonymized. Add: archive-date, archive-url. Formatted dashes. \| Use this bot. Report bugs. \| #UCB_CommandLine
(One intermediate revision by one other user 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\|~~Thoralf~~ 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)}}; however, Feferman calls this extension "no longer clearly finitary".</ref> PRA's proof theoretic ordinal is ω<sup>ω</sup>, where ω is the smallest [[transfinite number\|transfinite ordinal]]. PRA is sometimes called ''Skolem arithmetic'', although that has another meaning, see [[Skolem arithmetic]]. 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 139: \|editor-last=van Heijenoort \|editor-link=Jean van Heijenoort \|pages=302–333 ~~\|pp=302-333~~ \|last=Skolem \|first=Thoralf Line 166: \|title= Epistemology versus Ontology \|pages=161–180 \|chapter-url=~~https://web.archive.org/web/20240524221357/~~https://home.uchicago.edu/~wwtx/PRA2.pdf \|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 }}