Primitive recursive arithmetic

Uses your system voice; voice and rate in settings.

Snapshot

≈ 6 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Primitive recursive arithmetic (PRA) is a quantifier-free formalization of the natural numbers. It was first proposed by Norwegian mathematician , as a formalization of his finitistic conception of the 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, but others believe finitism can be extended to forms of recursion beyond primitive recursion, up to ε 0 , which is the proof-theoretic ordinal of Peano arithmetic. PRA's proof theoretic ordinal is ω ω , where ω is the smallest 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 numbers 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 metamathematical formal system for proof theory, in particular for consistency proofs such as Gentzen's consistency proof of first-order arithmetic.

Primitive recursive arithmetic (PRA) is a quantifier-free formalization of the natural numbers. It was first proposed by Norwegian mathematician , as a formalization of his finitistic conception of the 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, but others believe finitism can be extended to forms of recursion beyond primitive recursion, up to ε 0 , which is the proof-theoretic ordinal of Peano arithmetic. PRA's proof theoretic ordinal is ω ω , where ω is the smallest 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 numbers 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 metamathematical formal system for proof theory, in particular for consistency proofs such as Gentzen's consistency proof of first-order arithmetic. The equality symbol =, the constant symbol 0, and the successor symbol S (meaning add one); A symbol for each primitive recursive function. The logical axioms of PRA are the: Tautologies of the propositional calculus; Usual axiomatization of equality as an equivalence relation. The logical rules of PRA are modus ponens and variable substitution. The non-logical axioms are, firstly: S(x) \neq 0 ; S(x)=S(y) \to x = y, where x \neq y always denotes the negation of x = y so that, for example, S(0) = 0 is a negated proposition. 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: f(0,y_1,\ldots,y_n) = g(y_1,\ldots,y_n) f(S(x),y_1,\ldots,y_n) = h(x,f(x,y_1,\ldots,y_n),y_1,\ldots,y_n) Especially: x+0 = x\ x+S(y) = S(x+y)\ x \cdot 0 = 0\ x \cdot S(y) = x \cdot y + x\ ... and so on. PRA replaces the axiom schema of induction for first-order arithmetic with the rule of (quantifier-free) induction: From \varphi(0) and \varphi(x)\to\varphi(S(x)) , deduce \varphi(y) , for any predicate \varphi. In first-order arithmetic, the only primitive recursive functions 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 over all natural numbers. Defining primitive recursive functions in this manner is not possible in PRA, because it lacks quantifiers. {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)}. 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 only other inference rules of Goodstein's system are substitution rules, as follows: {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}. Here A, B, and C are any terms (primitive recursive functions of zero or more variables). Finally, there are symbols for any primitive recursive functions 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: \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} Thus, the equations x=y and |x - y| = 0 are equivalent. Therefore, the equations |x - y| + |u - v| = 0 and |x - y| \cdot |u - v| = 0 express the logical conjunction and disjunction, respectively, of the equations x=y and u=v. Negation can be expressed as 1 \dot - |x - y| = 0 .

Notes

References

Additional reading

Text derived from https://en.wikipedia.org/w/index.php?oldid=1322626220 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.