Page 17

		that . The domain and range of  y  are denoted by domain( y ) and range( y ), respectively. denotes the class . denotes the class of all total recursive functions. denotes the class of all partial recursive functions. denotes the class of recursive functions with range in N+ , , and occasionally other script capital letters range over classes of recursive functions.

		We often identify a (partial) function,  h  with its set of ordered pairs (that is . Thus is used to denote the everywhere undefined function. means that  h  is defined on x, and means that  h  is defined on x and  h (x) = y; and both mean that  h  is not defined on x. Thus and .  h (x) =  q (x) means that either or else both and . means that the graph of  h  is contained in the graph of  q  or, equivalently, for all ,  h (x) =  q (x). denotes the composition of  h  and  q , that is, for each x,

		h [n] denotes the partial function such that, for each x,

		For each and partial function  h , . For each ,  h =n q means that ;  h  and  q  are called n-variants. Also  h  =*  q  means that is finite;  h  and  q  are called finite variants. The characteristic function of a set A is denoted by  c A, that is, for all x,

		Suppose Q is an n-ary predicate. Then,

		Suppose that is an expression with xl, . . ., xn as its only free variables. Then denotes the function that maps (x1, . . ., xn) to the value . For example, denotes the function that maps x to x + 1, and denotes the function that maps (x, y) to x + y.