Primitive recursive arithmetic: Difference between revisions

Revision as of 21:19, 28 August 2010

Latest revision as of 23:13, 6 July 2025

(76 intermediate revisions by 44 users not shown)

Line 1:

{{short description|Formalization of the natural numbers}}

'''Primitive recursive arithmetic''', or '''PRA''', is a [[quantifier]]-free formalization of the [[natural numbers]]. It was first proposed by [[Thoralf Skolem|Skolem]]<ref>[[Thoralf Skolem]] (1923) "The foundations of elementary arithmetic" in [[Jean van Heijenoort]], translator and ed. (1967) ''From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931''. Harvard Univ. Press: 302-33.</ref> as a formalization of his [[finitist]] conception of the [[foundations of mathematics|foundations of arithmetic]], and it is widely agreed that all reasoning of PRA is finitist. Many also believe that all of finitism is captured by PRA<ref>[[William W. Tait|Tait, W.W.]] (1981), "Finitism", ''Journal of Philosophy'' 78:524-46.</ref>, but others believe finitism can be extended to forms of recursion beyond primitive recursion, up to [[epsilon 0|&epsilon;₀]]<ref>[[Georg Kreisel]] (1958) "Ordinal Logics and the Characterization of Informal Notions of Proof," ''Proc. Internat. Cong. Mathematicians'': 289-99.</ref>, which is the [[proof-theoretic ordinal]] of [[Peano arithmetic]]. PRA's proof theoretic ordinal is &omega;^&omega;, where &omega; is the smallest transfinite ordinal. PRA is sometimes called '''Skolem arithmetic'''.

'''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)|&epsilon;₀]],{{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 ω^ω, 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 5 ⟶ 7:

== Language and axioms ==

The language of PRA consists of:

* A [[countably infinite]] number of variables ''x'', ''y'', ''z'',... each ranging over the [[natural number]]s.

*The [[propositional calculus|propositional]] [[Logical connective|connectives]];

*The equality symbol ''='', the constant symbol ''0'', and the [[primitive recursive function|successor]] symbol ''S'' (meaning ''add one'');

*A symbol for each [[primitive recursive function]].

Line 13 ⟶ 15:

* [[tautology (logic)|Tautologies]] of the [[propositional calculus]];

* Usual axiomatization of [[Equality (mathematics)|equality]] as an [[equivalence relation]].

The logical rules of PRA are [[modus ponens]] and [[First-order logic#SubstitutionRules of inference|variable substitution]].<br>

The non-logical axioms are, firstly:

* <math>S(x) \neneq 0</math>;

* <math>S(x)=S(y) ~\to~ x = y,</math>

where <math>x \neq y</math> always denotes the negation of <math>x = y</math> so that, for example, <math>S(0) = 0</math> is a negated proposition.

and recursive defining equations for every [[primitive recursive function]] desired, especially:

Further, recursive defining equations for every [[primitive recursive function]] may be adopted as axioms as desired. For instance, the most common characterization of the primitive recursive functions is as the 0 constant and successor function closed under projection, composition and primitive recursion. So for a (''n''+1)-place function ''f'' defined by primitive recursion over a ''n''-place base function ''g'' and (''n''+2)-place iteration function ''h'' there would be the defining equations:

* <math>f(0,y_1,\ldots,y_n) = g(y_1,\ldots,y_n)</math>

* <math>f(S(x),y_1,\ldots,y_n) = h(x,f(x,y_1,\ldots,y_n),y_1,\ldots,y_n)</math>

Especially:

* <math>x+0 = x\ </math>

* <math>x+S(y) = S(x+y)\ </math>

* <math>x \cdot 0 = 0\ </math>

* <math>x \cdot S(y) = xyx \cdot y + x\ </math>

* ... and so on.

PRA replaces the [[mathematical induction|axiom schema of induction]] for [[first-order arithmetic]] with the rule of (quantifier-free) induction:

* From <math>\phivarphi(0)</math> and <math>\phivarphi(x)</math> <math>\to</math> <math>\phivarphi(S(x))</math>, deduce <math>\phivarphi(xy)</math>, for any predicate <math>\phivarphi.</math>

In [[first-order arithmetic]], the only [[primitive recursive function]]s that need to be explicitly axiomatized are [[addition]] and [[multiplication]]. All other primitive recursive predicates can be defined using these two primitive recursive functions and [[Quantification (logic)|quantification]] over all [[natural numbers]]. Defining [[primitive recursive function]]s in this manner is not possible in PRA, because it lacks [[quantifier]]squantifiers.

== Logic-free calculus ==

It is possible to formalise PRA in such a way that it has no logical connectives at all - aall—a sentence of PRA is just an equation between two terms. In this setting a term is a primitive recursive functionsfunction of zero or more variables. In {{harvtxt|Curry|1941 [[Haskell Curry]]}} gave the first such system<ref>[[Haskell Curry]], ''[http://www.jstor.org/stable/2371522 AThe Formalizationrule of Recursiveinduction in Arithmetic]Curry''.s [[Americansystem Journalwas ofunusual. Mathematics]],A vollater 63 no 2 (1941) pp 263-282</ref>, which had a non-elementary [[rule of induction]]. Thisrefinement was later refinedgiven by [[Reuben {{harvtxt|Goodstein]]<ref>[[Reuben|1954}}. Goodstein]],The ''[http://www.digizeitschriften.de/resolveppn/GDZPPN002343355 Logic-free formalisations[Rule of recursive arithmetic]'', [[Mathematica Scandinavicainference|rule]] vol 2 (1954) pp 247-261</ref>. The rule of induction in the latterGoodstein's system is:

:<math>{F(0) = G(0) \quad F(S(x)) = H(x,F(x)) \quad G(S(x)) = H(x,G(x)) \over F(x) = G(x)}.</math>

Here ''x'' is a variable, ''S'' is the successor operation, and ''F'', ''G'', and ''H'' are any primitive recursive functions which may have parameters other than the ones shown. The rulesonly ofother substitution[[inference inrule]]s thisof Goodstein's system are substitution rules, as follows:

:<math>{F(x) = G(x) \over F(A) = G(A)} \qquad {A = B \over F(A) = F(B)} \qquad {A = B \quad A = C \over B = C}.</math>

Here ''A'', ''B'', and ''C'' are any terms (primitive recursive functions of zero or more variables). Finally, as above, there are the defining equationssymbols for any primitive recursive functions needed.with corresponding defining equations, as in Skolem's system above.

In this way the propositional calculus can be discarded entirely. Logical operators can be expressed entirely arithmetically, for instance, the absolute value of the difference of two numbers can be defined by primitive recursion:

:<math>
\begin{align}

P(0) = 0 \quad & \quad P(S(x)) = x \\

x \dot - 0 = x \quad & \quad x \mathrel{\dot -} S(y) = P(x \mathrel{\dot -} y) \\

|x - y| = & (x \mathrel{\dot -} y) + (y \mathrel{\dot -} x). \\

\end{align}
</math>

Thus, the equations x=y and |''x''-=''y'' and <math>|x - y| = 0</math> are equivalent. Therefore, the equations <math>|x - y| + |u - v| = 0 \!</math> and <math>|x - y| \cdot |u - v| = 0 \!</math> express the logical [[Logical conjunction|conjunction]] and [[disjunction]], respectively, of the equations ''x''=''y'' and ''u''=''v''. [[Negation]] can be expressed as <math>1 \dot - |x - y| = 0</math>.

== See also ==

* [[Elementary recursive arithmetic]]

* [[Finite-valued logic]]

* [[Heyting arithmetic]]

* [[Peano arithmetic]]

* [[Primitive recursive function]]

* [[Robinson arithmetic]]

* [[Second-order arithmetic]]

* [[primitiveSkolem recursive functionarithmetic]]

==ReferencesNotes==

<references/>

==External linksReferences==

* [[Solomon Feferman|Feferman, S]] (1992) ''[http://citeseer.ist.psu.edu/feferman92what.html What rests on what? The proof-theoretic analysis of mathematics]''. Invited lecture, 15^th int'l Wittgenstein symposium.

*{{cite journal

|last= Curry

|first= Haskell B.

|author-link= Haskell Curry

|year= 1941

|title= A formalization of recursive arithmetic

|journal= [[American Journal of Mathematics]]

|mr= 0004207

|pages= 263–282

|volume= 63

|issue= 2

|doi= 10.2307/2371522

|jstor= 2371522

}}

*{{cite journal

|last= Goodstein

|first= R. L.

|author-link= Reuben Goodstein

|year= 1954

|title= Logic-free formalisations of recursive arithmetic

|journal= Mathematica Scandinavica

|mr= 0087614

|pages= 247–261

|volume= 2

|doi= 10.7146/math.scand.a-10412

|doi-access= free

}}

*{{Cite conference

|last= Kreisel

|first= Georg

|author-link= Georg Kreisel

|year= 1960

|contribution= Ordinal logics and the characterization of informal concepts of proof

|contribution-url = http://www.mathunion.org/ICM/ICM1958/Main/icm1958.0289.0299.ocr.pdf

|archive-url=https://web.archive.org/web/20170510093701/http://www.mathunion.org/ICM/ICM1958/Main/icm1958.0289.0299.ocr.pdf

|archive-date=10 May 2017

|___location= New York

|mr= 0124194

|pages= 289–299

|publisher= Cambridge University Press

|title= Proceedings of the International Congress of Mathematicians, 1958

}}

*{{cite journal

|last= Skolem

|first= Thoralf

|authorlink= Thoralf Skolem

|year= 1923

|title= Begründung der elementaren Arithmetik durch die rekurrierende Denkweise ohne Anwendung scheinbarer Veränderlichen mit unendlichem Ausdehnungsbereich

|trans-title= The foundations of elementary arithmetic established by means of the recursive mode of thought without the use of apparent variables ranging over infinite domains

|language= German

|url= https://www.ucalgary.ca/rzach/files/rzach/skolem1923.pdf

|journal= Skrifter Utgit av Videnskapsselskapet I Kristiania. I, Matematisk-naturvidenskabelig Klasse

|volume= 6

|pages= 1–38

}}

**{{cite book

|chapter=The foundations of elementary arithmetic established by means of the recursive mode of thought, without the use of apparent variables ranging over infinite domains

|title=From Frege to Gödel

|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

|first= William W.

|authorlink= William W. Tait

|year= 1981

|title= Finitism

|journal= [[The Journal of Philosophy]]

|volume= 78

|issue= 9

|pages= 524–546

|doi= 10.2307/2026089

|jstor= 2026089

}}

*{{cite book

|last= Tait

|first= William W.

|authorlink= William W. Tait

|date= June 2012

|chapter= Primitive Recursive Arithmetic and its Role in the Foundations of Arithmetic: Historical and Philosophical Reflections

|title= Epistemology versus Ontology

|pages=161–180

|chapter-url=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

}}

*{{cite book

|last= Feferman

|first= Solomon

|author-link= Solomon Feferman

|year=1998

|chapter= What rests on what? The proof-theoretic analysis of mathematics

|chapter-url=https://math.stanford.edu/~feferman/papers/whatrests.pdf

|doi=10.1093/oso/9780195080308.003.0010

|title=In The Light Of Logic

}}

===Additional reading===

*{{cite journal

|last= Rose

|first= H. E.

|year= 1961

|title= On the consistency and undecidability of recursive arithmetic

|journal= Zeitschrift für Mathematische Logik und Grundlagen der Mathematik

|mr= 0140413

|pages= 124–135

|volume= 7

|issue= 7–10

|doi= 10.1002/malq.19610070707

}}

{{Mathematical logic}}

[[Category:MathematicalConstructivism constructivism(mathematics)]]

[[Category:Formal theories of arithmetic]]