= a!×a' pred(a): (Predecessor or decrement): If a > 0 then a-1 else 0 Proper subtraction a ∸ b: If a ≥ b then a-b else 0 Minimum(a1, ... an) Maximum(a1, ... an) Absolute difference: | a-b | =def (a ∸ b) + (b ∸ a) ~sg(a): NOT[signum(a)]: If a=0 then 1 else 0 sg(a): signum(a): If a=0 then 0 else 1 a | b: (a divides b): If b=k×a for some k then 0 else 1 Remainder(a, b): the leftover if b does not divide a "evenly". Also called MOD(a, b) a = b: sg | a - b | (Kleene's convention was to represent true by 0 and false by 1; presently, especially in computers, the most common convention is the reverse, namely to represent true by 1 and false by 0, which amounts to changing sg into ~sg here and in the next item) a < b: sg( a' ∸ b ) Pr(a): a is a prime number Pr(a) =def a>1 & NOT(Exists c)1<c<a [ c|a ] pi: the i+1-st prime number (a)i: exponent of pi in a: the unique x such that pix|a & NOT(pix'|a) lh(a): the "length" or number of non-vanishing exponents in a lo(a, b): (logarithm of a to base b): If a, b > 1 then the greatest x such that bx | a else 0 In the following, the abbreviation x =def x1, ... xn; subscripts may be applied if the meaning requires. #A: A function φ definable explicitly from functions Ψ and constants q1, ... qn is primitive recursive in Ψ. #B: The finite sum Σy<z ψ(x, y) and product Πy<zψ(x, y) are primitive recursive in ψ. #C: A predicate P obtained by substituting functions χ1,..., χm for the respective variables of a predicate Q is primitive recursive in χ1,..., χm, Q. #D: The following predicates are primitive recursive in Q and R: NOT_Q(x) . Q OR R: Q(x) V R(x), Q AND R: Q(x) & R(x), Q IMPLIES R: Q(x) → R(x) Q is equivalent to R: Q(x) ≡ R(x) #E: The following predicates are primitive recursive in the predicate R: (Ey)y<z R(x, y) where (Ey)y<z denotes "there exists at least one y that is less than z such that" (y)y<z R(x, y) where (y)y<z denotes "for all y less than z it is true that" μyy<z R(x, y). The operator μyy<z R(x, y) is a bounded form of the