Search

For every n≥1, generic models of ZFC will be presented for either of the following two sentences: 1. There exists a linear Σn+21 set not equal to the projection of any uniform planar Πn+21 set. 2. There exists a linear Δn+21 set not equal to the projection of any uniform planar Πn+11 set. Ensuing consistency and independence corollaries are discussed.

It was established by Jensen in 1970 that there is a generic extension L[a] of the constructible universe L by a non-constructible real a∉L, minimal over L, such that a is Δ31 in L[a]. Our first main theorem generalizes Jensen’s result by constructing, for each n≥2, a generic extension L[a] by a non-constructible real a∉L, still minimal over L, such that a is Δn+11 in L[a] but all Σn1 reals are constructible in L[a]. Jensen’s forcing construction has found a number of applications in modern set theory. A problem was recently discussed as to whether Jensen’s construction can be reproduced entirely by means of second-order Peano arithmetic PA2, or, equivalently, ZFC− (minus the power set axiom). The obstacle is that the proof of the key CCC property (whether by Jensen’s original argument or the later proof using the diamond technique) essentially involves countable elementary submodels of Lω2, which is way beyond ZFC−. We demonstrate how to circumvent this difficulty by means of killing only definable antichains in the course of a Jensen-like transfinite construction of the forcing notion, and then use this modification to define a model with a minimal Δn+11 real as required as a class-forcing extension of a model of ZFC− plus V=L.

A model of set theory ZFC is defined in our recent research, in which, for a given n≥3, (An) there exists a good lightface Δn1 well-ordering of the reals, but (Bn) no well-orderings of the reals (not necessarily good) exist in the previous class Δn−11. Therefore, the conjunction (An)∧(Bn) is consistent, modulo the consistency of ZFC itself. In this paper, we significantly clarify and strengthen this result. We prove the consistency of the conjunction (An)∧(Bn) for any given n≥3 on the basis of the consistency of PA2, second-order Peano arithmetic, which is a much weaker assumption than the consistency of ZFC used in the earlier result. This is a new result that may lead to further progress in studies of the projective hierarchy.

We make use of generalized iterations of the Sacks forcing to define cardinal-preserving generic extensions of the constructible universe L in which the axioms of ZF hold and in addition either (1) the parameter-free countable axiom of choice ACω* fails, or (2) ACω* holds but the full countable axiom of choice ACω fails in the domain of reals. In another generic extension of L, we define a set X⊆P(ω), which is a model of the parameter-free part PA2* of the 2nd order Peano arithmetic PA2, in which CA(Σ21) (Comprehension for Σ21 formulas with parameters) holds, yet an instance of Comprehension CA for a more complex formula fails. Treating the iterated Sacks forcing as a class forcing over Lω1, we infer the following consistency results as corollaries. If the 2nd order Peano arithmetic PA2 is formally consistent then so are the theories: (1) PA2+¬ACω*, (2) PA2+ACω*+¬ACω, (3) PA2*+CA(Σ21)+¬CA.

The problem of the existence of analytically definable well-orderings at a given level of the projective hierarchy is considered. This problem is important as a part of the general problem of the study of the projective hierarchy in the ongoing development of descriptive set theory. We make use of a finite support product of the Jensen-type forcing notions to define a model of set theory ZFC in which, for a given n>2, there exists a good Δn1 well-ordering of the reals but there are no such well-orderings in the class Δn−11. Therefore the existence of a well-ordering of the reals at a certain level n>2 of the projective hierarchy does not imply the existence of such a well-ordering at the previous level n−1. This is a new result in such a generality (with n>2 arbitrary), and it may lead to further progress in studies of the projective hierarchy.

In this paper, we prove the following: If n≥3, there is a generic extension of L—the constructible universe—in which it is true that the Separation principle holds for both effective (lightface) classes Σn1 and Πn1 of sets of integers. The result was announced long ago by Leo Harrington with a sketch of the proof for n=3; its full proof has never been presented. Our methods are based on a countable product of almost-disjoint forcing notions independent in the sense of Jensen–Solovay.

The notion of ordinal definability and the related notions of ordinal definable sets (class OD) and hereditarily ordinal definable sets (class HOD) belong to the key concepts of modern set theory. Recent studies have discovered more general types of sets, still based on the notion of ordinal definability, but in a more blurry way. In particular, Tzouvaras has recently introduced the notion of sets nontypical in the Russell sense, so that a set x is nontypical if it belongs to a countable ordinal definable set. Tzouvaras demonstrated that the class HNT of all hereditarily nontypical sets satisfies all axioms of ZF and satisfies HOD⊆HNT. In view of this, Tzouvaras proposed a problem—to find out whether the class HNT can be separated from HOD by the strict inclusion HOD⫋HNT, and whether it can also be separated from the universe V of all sets by the strict inclusion HNT⫋V, in suitable set theoretic models. Solving this problem, a generic extension L[a,x] of the Gödel-constructible universe L, by two reals a,x, is presented in this paper, in which the relation L=HOD⫋L[a]=HNT⫋L[a,x]=V is fulfilled, so that HNT is a model of ZFC strictly between HOD and the universe. Our result proves that the class HNT is really a new rich class of sets, which does not necessarily coincide with either the well-known class HOD or the whole universe V. This opens new possibilities in the ongoing study of the consistency and independence problems in modern set theory.

Examples of effectively indiscernible projective sets of real numbers in various models of set theory are presented. We prove that it is true, in Miller and Laver generic extensions of the constructible universe, that there exists a lightface Π21 equivalence relation on the set of all nonconstructible reals, having exactly two equivalence classes, neither one of which is ordinal definable, and therefore the classes are OD-indiscernible. A similar but somewhat weaker result is obtained for Silver extensions. The other main result is that for any n, starting with 2, the existence of a pair of countable disjoint OD-indiscernible sets, whose associated equivalence relation belongs to lightface Πn1, does not imply the existence of such a pair with the associated relation in Σn1 or in a lower class.

In this paper we prove that for any m≥1 there exists a generic extension of L, the constructible universe, in which it is true that the set of all constructible reals (here subsets of ω) is equal to the set D1m of all reals definable by a parameter free type-theoretic formula with types bounded by m, and hence the Tarski ‘definability of definable’ sentence D1m∈D2m (even in the form D1m∈D21) holds for this particular m. This solves an old problem of Alfred Tarski (1948). Our methods, based on the almost-disjoint forcing of Jensen and Solovay, are significant modifications and further development of the methods presented in our two previous papers in this Journal.

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(ω)∩Δn1 of all (lightface) Δn1 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ν, ν<ω2L, is an almost-disjoint forcing notion in the ω1-version, that adjoins a subset Sν of ω1L. 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 Σn1 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 Δn1 real to be constructible; here the method of hidden invariance is applied. A discussion of possible further applications is added in the conclusive section.

Models of set theory are defined, in which nonconstructible reals first appear on a given level of the projective hierarchy. Our main results are as follows. Suppose that n ≥ 2 . Then: 1. If it holds in the constructible universe L that a ⊆ ω and a ∉ Σ n 1 ∪ Π n 1 , then there is a generic extension of L in which a ∈ Δ n + 1 1 but still a ∉ Σ n 1 ∪ Π n 1 , and moreover, any set x ⊆ ω , x ∈ Σ n 1 , is constructible and Σ n 1 in L . 2. There exists a generic extension L in which it is true that there is a nonconstructible Δ n + 1 1 set a ⊆ ω , but all Σ n 1 sets x ⊆ ω are constructible and even Σ n 1 in L , and in addition, V = L [ a ] in the extension. 3. There exists an generic extension of L in which there is a nonconstructible Σ n + 1 1 set a ⊆ ω , but all Δ n + 1 1 sets x ⊆ ω are constructible and Δ n + 1 1 in L . Thus, nonconstructible reals (here subsets of ω ) can first appear at a given lightface projective class strictly higher than Σ 2 1 , in an appropriate generic extension of L . The lower limit Σ 2 1 is motivated by the Shoenfield absoluteness theorem, which implies that all Σ 2 1 sets a ⊆ ω are constructible. Our methods are based on almost-disjoint forcing. We add a sufficient number of generic reals to L , which are very similar at a given projective level n but discernible at the next level n + 1 .