Sur le Semi-Réseau Constitué par les Degrés d'Indécidabilité Récursive. by Daniel LacombeReview by: Hartley Rogers, Jr.The Journal of Symbolic Logic, Vol. 23, No. 2 (Jun., 1958), p. 226Published by: Association for Symbolic LogicStable URL: http://www.jstor.org/stable/2964426 .

Accessed: 15/06/2014 12:36

Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at .http://www.jstor.org/page/info/about/policies/terms.jsp

.JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range ofcontent in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new formsof scholarship. For more information about JSTOR, please contact support@jstor.org.

.

Association for Symbolic Logic is collaborating with JSTOR to digitize, preserve and extend access to TheJournal of Symbolic Logic.

http://www.jstor.org

This content downloaded from 62.122.73.86 on Sun, 15 Jun 2014 12:36:57 PMAll use subject to JSTOR Terms and Conditions

226 REVIEWS

point. Notation and terminology are similar to that of Kleene and Post. The result is obtained with an explicit construction of the two sets. The construction and the accompanying non-constructive proof that the sets are incomparable proceed by an ingenious multiple induction. The desired sets, S1 and S2, are each obtained as the limit of an increasing chain of successive finite sets. Furthermore, the construction is arranged so that for each integer e, values xl(e) and x2(e) exist such that xl(e) e S. if and only if (iff) xl(e) is enumerated by the eth enumeration procedure recursive in S2. and x2(e) e S2 iff a2(e)... recursive in S1.. Flom this it follows that S1 and S2 are incomparable; for, e.g., S1 (recursively enumerable) is recursive in S2 iff there exists an e such that S1 is given by the eth enumeration procedure recursive in S2. The existence of the "invalidating" values xl(e) and x2(e) is brought about by a procedure according to which, at any stage, trial values of xl(e) and x2(e) are used and invalidations are sought with respect to the obtained finite approximations to S1 and S2. Since bringing about such invalidations may force enlargement of the finite approximations, conflicts can arise. These are resolved by an ingenious "priority" system according to which a successful invalidation with respect to any e takes preference over invali- dations with respect to all integers > e; conflicts are then avoided by recommencing a search for the latter invalidations using, as new trial values, integers that have not yet been considered in any way.

The functions xl and x2 are not recursive. It is not difficult to show that for any two incomparable sets,- any two such invalidating functions cannot be recursive. This essential non-constructive difficulty and the need for a new idea to overcome it provide a partial explanation for the long period between the formulation and the solution of Post's problem.

The author obtains, as a corollary, the result that for any set A, incomparable sets exist recursively enumerable in A.

On page 237, line 21, read "2.1" for "1.2". Friedberg and Mudnik merit much praise for a notable discovery.

HARTLEY ROGERS, Jr.

DANIEL LACOMBE. Sur le semi-reseau constitute par les degres d'indicidabilite re'- cursive. Comptes rendus hebdomadaires des seances de 1'Academie des Sciences (Paris), vol. 239 (1954), pp. 1108-1109.

The author announces a general lemma from which, in conjunction with Kleene and Post XXI 407, it follows (1) that the semilattice of arithmetic degrees of unsolv- ability is not a lattice and (2) that certain infinite increasing sequences of degrees have no least upper bound. (1) and (2) answer questions posed in XXI 407. As in- dicated in footnote 3 of that paper, these questions (among others) were independently answered by Spector. Spector's results were unpublished at the time of the present author's work.

The lemma is of independent interest and represents an extension of results of Kleene and Post. It is as follows. Let a0, al, .. . be an increasing sequence of degrees satisfying either the condition (i) that (3b)(Vj)[b < a, < by or the condition (ii) that

(Vj)[a+.1 = (aj)'. Let A be the collection of all degrees dominated by the given sequence and let c be any degree not in A. Then there exist two degrees d1 and d4, , neither of which dominates c, such iha4 A comprises exactly those degrees dominated by both d1 and d.2 Furthermore, in the case of condition (i) with b arithmetical, d, and d2 can be taken to be arithmetical provided that there exists an arithmetical function j of two variables such that (Vj)[Ay#(j, y) e aj]. A proof of the lemma is not given.

The lemma makes an interesting companion result to Spector's stronger form of (2): No infinite increasing sequence of degrees has a least upper bound (XXII 374).

HARTLEY ROGERS, Jr.

This content downloaded from 62.122.73.86 on Sun, 15 Jun 2014 12:36:57 PMAll use subject to JSTOR Terms and Conditions