On the Δ n 1 Problem of Harvey Friedman

In this paper, we prove the following. If n ≥ 3 , then there is a generic extension of L , the constructible universe, in which it is true that the set P ( ω ) ∩ L of all constructible reals (here—subsets of ω ) is equal to the set P ( ω ) ∩ Δ n 1 of all (lightface) Δ n 1 reals. The result was announced long ago by Leo Harrington, but its proof has never been published. Our methods are based on almost-disjoint forcing. To obtain a generic extension as required, we make use of a forcing notion of the form Q = C ℂ × ∏ ν Q ν in L , where C adds a generic collapse surjection b from ω onto P ( ω ) ∩ L , whereas each Q ν , ν < ω 2 L , is an almost-disjoint forcing notion in the ω 1 -version, that adjoins a subset S ν of ω 1 L . The forcing notions involved are independent in the sense that no Q ν -generic object can be added by the product of C and all Q ξ , ξ ≠ ν . This allows the definition of each constructible real by a Σ n 1 formula in a suitably constructed subextension of the Q -generic extension. The subextension is generated by the surjection b , sets S ω · k + j with j ∈ b ( k ) , and sets S ξ with ξ ≥ ω · ω . A special character of the construction of forcing notions Q ν is L , which depends on a given n ≥ 3 , obscures things with definability in the subextension enough for vice versa any Δ n 1 real to be constructible; here the method of hidden invariance is applied. A discussion of possible further applications is added in the conclusive section.