The list of primitive recursive functions

• addition

• mul

• exp

• monus

• abs

• absolute difference

• predecessor

• factorial

• primality testing

• nth prime

• divisibility, x-divides-y

• EQ

• LE

• LT

• GE

• GT

• α(x), (== 0), isZero predicate

• floor

• integer division (with flooring)

• pairing function (x,y)

• Gödel's number (pairing function)

• Lt(x) where x = [a₁, …, aₙ]

• projection, index ([a₁, …, aₙ])ᵢ

Operations on integers and rational numbers

By using Gödel numberings, the PRFs can be extended to operate on other objects such as integers and rational numbers. If integers are encoded by Gödel numbers in a standard way, the arithmetic operations including addition, subtraction, and multiplication are all primitive recursive. Similarly, if the rationals are represented by Gödel numbers then the field operations are all primitive recursive.