The forcing method and the upper semilattice of hyperdegrees

Abstract

1.1.Introduction.The method of forcing was invented by Cohen [C] for application to set theory.Feferman [F, §2] has adapted the Cohen techniques to first-order number theory.With Feferman's adaptation it is possible directly to obtain theorems concerning the existence of sets of natural numbers with prescribed arithmetical properties.(An arithmetical property is one expressible by a formula F (Xx,..., Xn, xlt..., xm) of second-order number theory having no bound set variables.)Feferman's basic methods, applied with considerable ingenuity, suffice to prove some theorems referring to nonarithmetical properties of sets; this has been done by Feferman [F, §2], Addison [A2], Hinman [H], and others.It seems, however, that the basic method has limited nonarithmetical applicability.This fact is not surprising; one should not expect the power of the forcing method, as applied to a particular language, to extend much beyond the properties expressible in that language.Thus one is led to attempt to define forcing for stronger languages.Of course, set theory is itself such a stronger language.But in order to get good upper bounds on the "computational complexity" of sets constructed by forcing techniques, it is necessary to use languages which are as weak as possible.Moreover, the use of the language of set theory introduces unpleasant complications regarding consistency, absoluteness, etc. Presumably motivated by these considerations, Feferman in [F, §3] extended forcing to a language of ramified analysis.This paper comprises two parts.In the first we shall extend Feferman's notion of number-theoretic forcing to a stronger language.This construction is rather complicated, and occupies § §1.2-1.5.In §1.6, the method will be used to deduce the existence of a pair of sets of numbers possessing a rather strong "incomparability property," namely they are both hyperarithmetic in Kleene's set O of constructive ordinal notations, yet neither is arithmetically definable from the hyperjump of the other.Our original program was to investigate the structure of the upper semilattice of hyperdegrees, and the outcome of this investigation, using Presented to the Society, in part, June 19, 1965 under the title Hyperarithmetic ^comparability; received by the editors May 20, 1966 and, in revised form, October 3, 1966.