μ-recursive Function - Symbolism

Symbolism

A number of different symbolisms are used in the literature. An advantage to using the symbolism is a derivation of a function by "nesting" of the operators one inside the other is easier to write in a compact form. In the following we will abbreviate the string of parameters x₁, ..., x_n as x:

• Constant function: Kleene uses " C_qn(x) = q " and Boolos-Burgess-Jeffry (2002) (B-B-J) use the abbreviation " const_n( x) = n ":

e.g. C₁₃7 ( r, s, t, u, v, w, x ) = 13

e.g. const₁₃ ( r, s, t, u, v, w, x ) = 13

• Successor function: Kleene uses x' and S for "Successor". As "successor" is considered to be primitive, most texts use the apostrophe as follows:

S(a) = a +1 =_def a', where 1 =_def 0', 2 =_def 0 ' ', etc.

• Identity function: Kleene (1952) uses " U_in " to indicate the identity function over the variables x_i; B-B-J use the identity function id_in over the variables x₁ to x_n:

U_in( x ) = id_in( x ) = x_i

e.g. U₃7 = id₃7 ( r, s, t, u, v, w, x ) = t

• Composition (Substitution) operator: Kleene uses a bold-face S_nm (not to be confused with his S for "successor" ! ). The superscript "m" refers to the mth of function "f_m", whereas the subscript "n" refers to the nth variable "x_n":

If we are given h( x )= g( f₁(x), ..., f_m(x) )

h(x) = S_mn(g, f₁, ..., f_m )

In a similar manner, but without the sub- and superscripts, B-B-J write:

h(x')= Cn(x)

• Primitive Recursion: Kleene uses the symbol " Rn(base step, induction step) " where n indicates the number of variables, B-B-J use " Pr(base step, induction step)(x)". Given:

• base step: h( 0, x )= f( x ), and
• induction step: h( y+1, x ) = g( y, h(x,y),x )

Example: primitive recursion definition of a + b:

• base step: f( 0, a ) = a = U₁1(a)
• induction step: f( b', a ) = ( f ( b, a ) )' = g( b, f( b, a), a ) = g( b, c, a ) = c' = S(U₂3( b, c, a )

R2 { U₁1(a), S }

Pr{ U₁1(a), S }

Example: Kleene gives an example of how to perform the recursive derivation of f(b, a) = b + a (notice reversal of variables a and b). He starting with 3 initial functions

1. S(a) = a'
2. U₁1(a) = a
3. U₂3( b, c, a ) = c
4. g(b, c, a) = S(U₂3( b, c, a )) = c'
5. base step: h( 0, a ) = U₁1(a)

induction step: h( b', a ) = g( b, h( b, a ), a )

He arrives at:

a+b = R2