On the 'definability of definable' problem of Alfred Tarski, Part II.

Alfred Tarski [J. Symbolic Logic 13 (1948), pp. 107–111] defined \mathbf {D}_{pm} to be the set of all sets of type p, type-theoretically definable by parameterfree formulas of type {\le m}, and asked whether it is true that \mathbf {D}_{1m}\in \mathbf {D}_{2m} for m\ge 1. Tarski noted that the negative solution is consistent because the axiom of constructibility \mathbf {V}=\mathbf {L} implies \mathbf {D}_{1m}\notin \mathbf {D}_{2m} for all m\ge 1, and he left the consistency of the positive solution as a major open problem. This was solved in our recent paper [Mathematics 8 (2020), pp. 1–36], where it is established that for any m\ge 1 there is a generic extension of \mathbf {L}, the constructible universe, in which it is true that \mathbf {D}_{1m}\in \mathbf {D}_{2m}. In continuation of this research, we prove here that Tarski's sentences \mathbf {D}_{1m}\in \mathbf {D}_{2m} are not only consistent, but also independent of each other, in the sense that for any set Y\subseteq \omega \smallsetminus \{0\} in \mathbf {L} there is a generic extension of \mathbf {L} in which it is true that \mathbf {D}_{1m}\in \mathbf {D}_{2m} holds for all m\in Y but fails for all m\ge 1, m\notin Y. This gives a full and conclusive solution of the Tarski problem. The other main result of this paper is the consistency of \mathbf {D}_{1}\in \mathbf {D}_{2} via another generic extension of \mathbf {L}, where \mathbf {D}_{p}=\bigcup _m\mathbf {D}_{pm}, the set of all sets of type p, type-theoretically definable by formulas of any type. Our methods are based on almost-disjoint forcing of Jensen and Solovay [Some applications of almost disjoint sets, North-Holland, Amsterdam, 1970, pp. 84–104]. [ABSTRACT FROM AUTHOR]