definition implements the equality predicate. In fact, is true if, and only if, equals . Similarly, the definition implements the predicate "less-than", and implements "greater-than". Other operations on natural numbers Exponentiation and primality testing are primitive recursive. Given primitive recursive functions e, f, g, and h, a function that returns the value of g when e≤f and the value of h otherwise is primitive recursive. Operations on integers and rational numbers By using Gödel numberings, the primitive recursive functions 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. Some common primitive recursive functions The following examples and definitions are from Kleene (1952) pp. 223–231 — many appear with proofs. Most also appear with similar names, either as proofs or as examples, in Boolos-Burgess-Jeffrey 2002 pp. 63–70; they add the logarithm lo(x, y) or lg(x, y) depending on the exact derivation. In the following we observe that primitive recursive functions can be of four types: functions for short: "number-theoretic functions" from { 0, 1, 2, ...} to { 0, 1, 2, ...}, predicates: from { 0, 1, 2, ...} to truth values { t =true, f =false }, propositional connectives: from truth values { t, f } to truth values { t, f }, representing functions: from truth values { t, f } to { 0, 1, 2, ... }. Many times a predicate requires a representing function to convert the predicate's output { t, f } to { 0, 1 } (note the order "t" to "0" and "f" to "1" matches with ~sg( ) defined below). By definition a function φ(x) is a "representing function" of the predicate P(x) if φ takes only values 0 and 1 and produces 0 when P is true". In the following the mark " ' ", e.g. a', is the primitive mark meaning "the successor of", usually thought of as " +1", e.g. a +1 =def a'. The functions 16-20 and #G are of particular interest with respect to converting primitive recursive predicates to, and extracting them from, their "arithmetical" form expressed as Gödel numbers. Addition: a+b Multiplication: a×b Exponentiation: ab Factorial a! : 0! = 1, a'!