Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Primitive recursive arithmetic
open-in-new
<p>Primitive recursive arithmetic (PRA) is a <a href="/facts/Quantification_(logic)/bgmvwxoo">quantifier</a>-free formalization of the <a href="/facts/Natural_numbers/u65og8JE">natural numbers</a>. It was first proposed by Norwegian mathematician Skolem (1923), as a formalization of his <a href="/facts/Finitist/UudNtdnd">finitistic</a> conception of the <a href="/facts/Foundations_of_mathematics/yjpbbUkt">foundations of arithmetic</a>, and it is widely agreed that all reasoning of PRA is finitistic. Many also believe that all of finitism is captured by PRA, but others believe finitism can be extended to forms of recursion beyond primitive recursion, up to <a href="/facts/Epsilon_zero_(mathematics)/t7w8KgA9">ε0</a>, which is the <a href="/facts/Proof-theoretic_ordinal/bx5joaVU">proof-theoretic ordinal</a> of <a href="/facts/Peano_arithmetic/DhhDnNug">Peano arithmetic</a>. PRA's proof theoretic ordinal is ωω, where ω is the smallest <a href="/facts/Transfinite_number/m2oTjXaj">transfinite ordinal</a>. PRA is sometimes called <i>Skolem arithmetic</i>, although that has another meaning, see <a href="/facts/Skolem_arithmetic/4DYh7RYP">Skolem arithmetic</a>. </p><p>The language of PRA can express arithmetic propositions involving <a href="/facts/Natural_number/u65og8JE">natural numbers</a> and any <a href="/facts/Primitive_recursive_function/4z97gRnl">primitive recursive function</a>, including the operations of <a href="/facts/Addition/apFWJBFB">addition</a>, <a href="/facts/Multiplication/VtcUjpNv">multiplication</a>, and <a href="/facts/Exponentiation/pac6QY2g">exponentiation</a>. PRA cannot explicitly quantify over the domain of natural numbers. PRA is often taken as the basic <a href="/facts/Metamathematic/yeIm8vqC">metamathematical</a> <a href="/facts/Formal_system/KaeDAjK7">formal system</a> for <a href="/facts/Proof_theory/kopBdQn9">proof theory</a>, in particular for <a href="/facts/Consistency_proof/IHkdnA9M">consistency proofs</a> such as <a href="/facts/Gentzen%2527s_consistency_proof/LTDpe0V8">Gentzen's consistency proof</a> of <a href="/facts/First-order_arithmetic/DhhDnNug">first-order arithmetic</a>. </p>