8
S. C. KLEENE
completely undefined. Specifically, (SO),(SI),(S3),(S5) and (S7) demand at
least one number variable, and (S6)with proper index 6,£,K demands at least
h-KL. (S7) demands at least one function variable, and (S&)with proper index
8,£,h at leastfrfl.For example, f(&jrt) with proper index 6,1,1 and
P(&) "with proper index 7 are completely undefined.
Thus each proper index f comes to be interpreted as a proper index of a
partial function A^...a^tf... ••Q^ ^§q »••• 9§±Lr&i •••&/)*
for each choice
of k,2 0.
Consider the following question, for any proper index f. How many number
variables k at the least,and how many function variables i at the least,must
we give the function $ (=Xa-...a, OC ...X£ ^(§n,...,a, ,£*.,,...,cXp)with the
proper index f in order that, in the entire irredundant sequence of schema
applications described by f, none of the applications demands more variables
of either type than are supplied? The answer is provided by taking k = mn(£)
and ^ = mf(£) ("minimum number variables" and "minimum function variables" for
ordinary use of the schemata), where mn and mf are defined by course-of-values
recursions so that the following equations hold.
mn(0,g) = max(l,mn(g)), mf(0,g)= mf(6,£,h)= mf(^),
mn(3) = mn(3)= mn(7)= 1, mf(L)= mf(2,£)= mf(3)= 0,
mn(2,g) = 0, mf(4,g,h)= mf(5,£,h)= max(mf(£),mf(h)),
nm(4,g,h)= max(mn(£)-l,mn(h)), mf(7)= 1,
mn(5,g,h)= max(l,mn(£)+l,mn(h)-l), mf(S,g,h)= max(W-l,mf(g)),
mn(6,g,h) = max(frHL,mn(g)),
mn(8,g,h)= mn(g).
The property of these functions mn(f) and mf(f)will be verified in 3»3
Lemma 34 (which,rephrased a bit, could be put here)*
1.4. Now we consider the process of computing the value (if defined) of
the function (9, of k number variables and ^ function variables, with the
A function cf, with proper index £, having less than mn(:f)number
variables or less" than mf(f) function variables can nevertheless be defined
for some sets of arguments or even all. Namely, this will happen for a given
set of arguments if the schema applications deficient in variables will be
bypassed in computing the value in question. This can result from using (S5)
so that its second equation is not called upon in the computation. For
example, taking f = 4,5,3,h,2,0» with mn(h) = 4 as a proper index of a
function J?(a) (so k = 1, i = 0), then mn(f) = 2~ k and yet fia) (= a, for
all a) is"completely defined. (Cf. Kleene~1968 Footnote 12.12)~ ~
Previous Page Next Page