Copyright
Hilary Putnam.

Trial and error predicates and the solutions to a problem of Mostowski's online

. (page 1 of 4)
Online LibraryHilary PutnamTrial and error predicates and the solutions to a problem of Mostowski's → online text (page 1 of 4)
Font size
QR-code for this ebook


AFOSR 81 7



NEW YORK UNIVERSITY

idSTITUTE OF MATHcMATlCAL SCIENCES

LIBRARY

\4 Washington Place, New York 3, N. Y.



IMM-NYU 290
JUNE 1961




new york university

RnJstitute of
mathematical sciences



Trial and Error Predicates and the
Solution to a Problem of Mostowski's



HILARY PUTNAM



PREPARED UNDER
CONTRACT NO. AF49(638)-777
MATHEMATICAL SCIENCES DIRECTORATE
AIR FORCE OFFICE OF SCIENTIFIC RESEARCH



o



d



REPRODUCTION fN WHOLE OR IN PART

IS pERMrrrED for any purpose

if, 71-£ UNiTED STATES GOVERiSMENT.



^ OF MATHEMATICAL SC/ENCFS
Wasl,.„g,o„ PUe, New YoH. 3, N. Y

New York University
Institute of Mathematical Sciences
Mathematical Sciences Directorate
Air Force Office of Scientific Research
Washington 25, D.C.
AFOSR 817



TRIAL AND ERROR PREDICATES AND THE
SOLUTION TO A PROBLEM OP MOSTOWSKI'S
Hilary Putnam

June 8, 1961 Contract No. AF 49 (638) -777

ABSTRACT: It is proved that every consistent formula of
quantification theory has a model in Mostowski's field of
sets.



"Qualified requestors may obtain copies of this report from
the ASTIA Document Service Center, Arlington Hall Station,
Arlington 12, Virginia. Department of Defense contractors must
be established for ASTIA services, or have their "need-to-know"
certified by the cognizant military agency of their project or
contract".



The research reported in this document has been sponsored by
the Mathematical Sciences Directorate, Air Force Office of
Scientific Research, under Contract No. AF 49(638)-777.



ji



1 B-



1

"TRIAL AND ERROR" PREDICATES AND TI-IE
SOLUTION TO A PROBLEM OF MOSTOV'SKI'S
By HILARY PUTNAM
1, Introduction . The purpose of this paper is to present two
groups of results vhich have turned out to have a surprisingly
close connection. The first two results (Theorems 1 and 2) were
inspired by the following question: we know what sets are "dec id-
able" namely, the recursive sets (according to Church's Thesis).

But what happens if we modify the notion of a decision procedure
by (1) allowing the procedure to "change its mind" any finite
number of times (in terms of Turing Machines: we visualize the
machine as "printing out" a finite sequence of "yesses" and "nos".
The last "yes" or "no" is always to be the correct answer); and
(2) we give up the requirement that it be possible to tell (ef-
fectively) if the computation has terminated? (i.e. if the ma-
chine has most recently printed "yes", then we know that the
appropriate nxomber must be in the set unless the machine "changes
its mind "; but we have no general procedure for telling whether
the machine will "change its mind" or not.)

In traditional philosophic parlance, the sets for which
there exist a "decision method" in this widened sense are decid-

able by "empirical" means, or by using "Humean induction" for,

if we always "bet" that the most recently generated answer is
correct, we will make a finite nii.mber of mistakes, but we will
eventually get (and "stick to") the conreot answer. Koto,
however, that even if we have gotten to the correct answer (the



QHA



■ iQ oct Bi laqsq i. :."-

er'-t ©.^.[ . : zenla



,. 4!. .• c



r-i'/ ^-t rial predicate if there is a g.r. function f
and a fixed integer k such that (for all x,,...,x^)

(1) p(x,,...,x ) = lim f(x,,...,x ,y) = 1

. . y->oo

(2) There are at most k integers y such that
f(x^,...,x^,y) 7^ f(x^,...,x^, y+1)

[Note that i-'e do not require the fimction f to be such that

P(x^,....,x ) = lim f (x^, . ..,x^,y) =

y— >cx3r

however, this condition will always be satisfied as well if

we replace the given function f by f", where f (x^, . • •,x^,y) = 1

if f(x^,...,x^,y) = 1 and f '"'(x^, . . .,x^,y) = if f (x^, . ..,x^,y)7^ 1.

For, since there are at most k places (values of y) at which

f(x,,...,x ,y) changes its value (for fixed x^,...,x^), there

must be a value of y, say M (depending on x^,....,x^), such that

for y > M, f(x^,...,x ,y) is constant. Then lim f (x^, . « . ,x^,y ) =

^ y— >©

f(x,,«...,x ,M+1) ^ 1 unless P(x^, • . .,x^) , so P(Xj^, .. .,Xj^) =

lim f'''"(x^,...,x ,y) = 0.]
y->OD

(Question 2: ^^rhat are necessary and sufficient conditions that
there exist a k such that P is a k-trial predicate?



B-iom. fcnirfi 8cJ,i egnBdo od; , ; f -is^a sioii .©ni.' '^J^*?^ v'i^isPy

.nwl .-2,3 B zl 5j'29-1-t i+i',. ■ sL;-;^. 6..*i ei^.3?iit- • ... '• ^ '* "T t






.-J 1



, ertaiii *{ >:,*.., ^.x hdxxl -tol) eulnv etti B©Siii?.iio (v:

• • .. .... ' . 'i*



1*0 = {'%^'^(»**.%r



T©;teoxf)eiq Xsiid'-i j3 . • /.eitr flows >=



t •-



k

The investigations which resolved these questions have led
also to other questions. For example tajo have been able to prove
(though not straightforwardly) that (for every k) there is a
k+l-trial predicate which enumerptes the k~trial predicates (with
Che less argument place). This theorem is a generalization of

Dekker's result that the recursive sets are a recursively enumer-

2

able family of r.e. sets ; for the recursive sets are the 0-trial

sets in our sub-hierarchy, and the r.e. predicates are all 1-trial.
Our proof uses Dekker's result, together with the theorem in a i|-,
that the pairs < A,B > of dis. joint r.e. sets are a recursively
enumerable family of pairs of r.e. sets. This result is in sec-
tion I 5 of the present paper, together with results on the modulus

3
of oscillation of trial and error predicates: the most difficult

result in g 5 is that the trial and error predicates which possess

a recursive modulus of oscillation can be enumerated by a single

trial and error predicate. These predicates represent perhaps

the largest significant class of Yip ^ TT 2 P^^^^i^^^QS for which

there exists a "normal form" i.e., a recursively eniaraerable set

of expressions such that (a) every predicate in the class is

"designated" by one of the expressions in the setf and (b) given

any expression in the set one can effectively write down at least

one y~ g expression and at least one / f p expression^ for the

predicate it "designates".

Our second result or group of results is connected with the

meta-theory of quantification theory. A number of years ago.



■'A



X i. / 'i



r» •.■



-ooe "; 8^ -? r ^,-.-. o'KT ... ..... •■■:.-''j ".:. vr/:v.l ?. .C';^;'Xu;!i•J■^§

.*T»*. .u, «.



Mostowski reported on his xonsuccessful attempts to find a con-
sistent formula of quantification theory with no model in the
"smallest field of sets containing the recursively enumerable sets"
Since"set" here means sets of n-tuples, what Mostowski vanted is,
in oiir terminology, a formula with no model in which (1) the
universe of discourse is the natural numbers; and (2) the predicate
letters are all interpreted as r.e. predicates or truth-functions
of r«e« predicates.

The ma.in result of g 3 is : a formula of this kind (the kind
wanted by Mostowski) does not exist. Every consistent formula of
quantification theory does have a model in y~". The proof
uses Theorems 1 and 2, which were discovered as the ansv/ers to
Q,uestion 1 and 2, and the Hilbert-Bernays-Kleene result that
every consistent formula of q.t. (quantification theory) has a

a

model in JZ.oO'U'p' ^ 1957 I gave an example of a consistent
formula of q.t. with no model in which all the predicates belong
to YZ-\ U 77i (s'^swering another question of Mostowski' s); thus

y r represents the '^lowest" level which contains "enough sets"
so that it is always possible to find a model.

The penultimate section of this paper { sk.) consists of some

S

"enumeration theorems" (e.g., the potentially recursive fxmctions

are a recursively enumerable family of partial recursive functions),

some of which are needed for the final section, and others of

which are given as being of possible independent interest,

2, Characterization theorems .

Theorem 1, P is a trial and error predicate if and only if






51



, s a «^B ir:0- r. ,-,-;j - : ,,^^ t-f^i^:'^ 'i-J-iJ-Hf ilit-r;-.

' *■ . ■ - ,.,■.■.■,.■ I- « ,1... ,, ,,.',■ A, -„• -1. , J.,'^



'"^ s-SfJ ( v:^S.';53^:t r:o.f::'-pc:.!:'j;|

{z > Y & f(x^,...,x^,z) = 1))

Thus P e Tip* and by (1) v?e have P e J~ 2> since the predicate

"lim f (x, , . ..,x ,y) = l" is in T'p.

^ 1 m ■* — c.

y->00

To prove the other half of the theorem, assume

(3) P(x3^»»«-»x^) = (Ea)(b)R^(x^,...,Xj^,a,b)

P(x^,...,x^) = (Ea)(b)R2(x^, ...,Xj^,a,b)

where R, and Rp are recursive.

Let T(x, ,,.,,x ,a,c) mean that a is the smallest integer
i m

such that [(Ee) (e is the number of a proof (in, say, Robinson's

arithmetic*^) that R^(Xt , . . .,x^,a,b) for some b)(^-'^(Ee) (e is

d X m ^c

the number of a proof that R-|^(x^, . . .,x^,a,b) for some b) .v.

(Ee)^ (e is the number of a proof that R, (x , . . .,x ,a,b) for
some b)(2?''^(Ee) (e is the number of a proof that R^iyi^f**,
X >a,b) for some b)].



^".









Pi .', , . ^" ill

.c'~v



/






£,^ r.rt »■> r-



\)(sa)(Y) ::: i^^



.x)3. (L)






,x)"?: nil"



■i:-:>



* - • _■■■»»*



.H( the smallest class containing
the recursively enumerable predicates and closod under truth-func -
tions .

Proof : Suppose P is a k-trial predicate. Then by the definition
(cf. p 1) there is a g.r. function f such that

\ -

(1) P(x^,...,x^) = lim f(x^,...,x^,y) = 1

y— >CO



8






■ . ..• . .. ^ .- .. ■• /).

.. • - • » •- • .». r * • f ..-■.; ■

;.••''■ '1 r : • V : ■■ '

t K/ •- -> ^.. J- •. . ^ f • • • ^ -.% ^ I



r>':fod avari ILlv ■ - ; v,i

u-vni rio.VE legsSnJ- u^C'LlBras ofl' : .;■ ■ - ^ '< ^ ...,,.:■:) ^

•T ? » ■■ "■' r '-J r ^ r ^.'■' ■" - . *. • ■ '".■'- ■ ; ■ 'v I .- ■ - - I

rt. ♦-.*..-■ . '•' ■ - ■ ' • • i_ . • /i I fl « ' p J .-■. / . • . »^ .-.•*••-'■>,..■ 1-.* ^

■-'t:r.'- ■• .„ v,,..,^:!. ■{ rl^^od ©vijr; X..r.r-' ©i' \: "ro aaw-CRV s';-"s:i\L vl

'^ ' '^ -.-I'.N ■ * ' ■'■•-J. .■■(-■. -5 T ; .^ ."^ .* * /J> ;' :'*.'' ' -'. tf" /liiii: '■• r '^






(2) there are a_t most k integers y, for each x »•..•. ^x ,

such that f(x. ,...,x ,y) /f(x. ,...,x , y + 1),
1 . m 1 m

Now define yT(x_,...,x ) (for i = l,2,..,,k) as meaning

that there are at least i Integers y such that f (x^, « . «,x ,y) 5^

f(x,,...,x , j+1) S f(x-,...,x ,a.+l) = 1, where a is the ith
1 in i ni 1 1

integer y, in order of magnitude, such that f (x, , .« •,x ,y) j^

f(x, .....x jy+l)) and define N, (Xt,...,x ) as meaning that there
l''m'-» ilm

are at least i integers y such that f (x, , . . . ,x ,y) / f(x-,...,
x^,y+l) (§ f(x^,...,x^,a^+l) 7^1. Finally, define Yq(x^,...,x^)
as meaning that f(x-,...,x ,0) = 1, and Nq(x-,...,x ) as meaning
that f(x,,...,x ,0) =^1. Then all the predicates Y. and N. are
recursively eniomerable, and we have:

P(x^,...,x^) ^ Yj^(x^,...,x^) V (\^i, .



i.- ; ...



« ♦ • t .

J.



.-i.-^^u.':



l-'j -fw^f* ..^^•



ii»».. y»yX ^ ^C^, -''•'"■'



.1 o



-';':■ i' ' 1 T-






o'ty; j.t': jbr^B .Y SDCfsr



>. i B r.tc









• ♦ .■ ' I v\ • I > » a



['■■■'I-oi



■ V



eatlcioo
ecBiq~n erJ:t eor.



'5ef-^c



4 ■'.r-^j' -






^dS »lj.l-! rf r.



■ riXK



J..:::



*• : 1-.'^.''''



',:^) ■ : fi^,k} *^ 1



;■■■



* ,- •-. r- '- a'e:






^ ; •.)••"» i-l'-.i. i.;}'ic-'i
•1 ocli erti f>r^cC?J.y>t^:i>.'



:* 'V ■ rr«.]^.- ■ f. ^.. „ - 1» r - -' -^ '^••'r^''' -^ i. ^^ :



JE ■ ■ " ' •. - ■. V



^ ... - -t T.f rf. ,, .



(^?£.^J K .c .:; ••



^t.v



11

In this case, by the definition of f, there are i < n,
e < y (and hence < y + l) such that T(a.,x,e) ^ (e)^ T(b.,x,e);
but f(x,y + 1) = 0, so there must be an e' < y + 1 such that
T(b.,x,e')» Hence we must have e' = y, and e' must = e. (the
smallest number of a proof that x e B. ) • Since there are only
n sets B. altogether, and there Is only one e for each B , this
case can arise for at most n values of y.
case (b) f(x,y) = 0, f(x,y + 1) = 1

In this case, by the definition of f , there are i < n, e R(a) f) R(b) = A

2) Lj R(a) = N (the set of all non-negative integers)

a






i-t^t-C' ►;



!?-



Kf/i/V ( -^ ^ 1- ^


1 3 4

Online LibraryHilary PutnamTrial and error predicates and the solutions to a problem of Mostowski's → online text (page 1 of 4)