On the ‘definability of definable’ problem of Alfred Tarski, Part II

Abstract:

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].