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

HTML articles powered by AMS MathViewer

- by Vladimir Kanovei and Vassily Lyubetsky PDF
- Trans. Amer. Math. Soc.
**375**(2022), 8651-8686 Request permission

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

## References

- J. W. Addison,
*The undefinability of the definable*, Not. AMS**12**(1965), no. 3, 347–348. - J. W. Addison,
*Tarski’s theory of definability: common themes in descriptive set theory, recursive function theory, classical pure logic, and finite-universe logic*, Ann. Pure Appl. Logic**126**(2004), no. 1-3, 77–92. Provinces of logic determined. MR**2060926**, DOI 10.1016/j.apal.2003.10.009 - Carolin Antos and Sy-David Friedman,
*Hyperclass forcing in Morse-Kelley class theory*, J. Symb. Log.**82**(2017), no. 2, 549–575. MR**3663416**, DOI 10.1017/jsl.2016.74 - Carolin Antos, Sy-David Friedman, Radek Honzik, and Claudio Ternullo (eds.),
*The hyperuniverse project and maximality*, Birkhäuser/Springer, Cham, 2018. MR**3753568**, DOI 10.1007/978-3-319-62935-3 - J. Barwise (ed.),
*Handbook of mathematical logic*, Studies in Logic and the Foundations of Mathematics, vol. 90, North-Holland, Amst., 1977. MR**709106 (84g:03004a)** - George S. Boolos, John P. Burgess, and Richard C. Jeffrey,
*Computability and logic*, Cambridge: Cambridge University Press, 2007 (English). - Patrick Cegielski,
*Definability, decidability, complexity*, Ann. Math. Artificial Intelligence**16**(1996), no. 1-4, 311–341. MR**1389852**, DOI 10.1007/BF02127802 - William Chan,
*Ordinal definability and combinatorics of equivalence relations*, J. Math. Log.**19**(2019), no. 2, 1950009, 24. MR**4014889**, DOI 10.1142/S0219061319500090 - James Cummings, Sy-David Friedman, Menachem Magidor, Assaf Rinot, and Dima Sinapova,
*Ordinal definable subsets of singular cardinals*, Israel J. Math.**226**(2018), no. 2, 781–804. MR**3819709**, DOI 10.1007/s11856-018-1712-2 - René David,
*$\Delta ^{1}_{3}$ reals*, Ann. Math. Logic**23**(1982), no. 2-3, 121–125 (1983). MR**701123**, DOI 10.1016/0003-4843(82)90002-X - Natasha Dobrinen and Sy-David Friedman,
*Homogeneous iteration and measure one covering relative to HOD*, Arch. Math. Logic**47**(2008), no. 7-8, 711–718. MR**2448954**, DOI 10.1007/s00153-008-0103-5 - Ali Enayat and Vladimir Kanovei,
*An unpublished theorem of Solovay on OD partitions of reals into two non-OD parts, revisited*, J. Math. Log.**21**(2021), no. 3, Paper No. 2150014, 22. MR**4330522**, DOI 10.1142/S0219061321500148 - Vera Fischer, Sy David Friedman, and Lyubomyr Zdomskyy,
*Cardinal characteristics, projective wellorders and large continuum*, Ann. Pure Appl. Logic**164**(2013), no. 7-8, 763–770. MR**3037550**, DOI 10.1016/j.apal.2012.12.001 - Harvey Friedman,
*One hundred and two problems in mathematical logic*, J. Symbolic Logic**40**(1975), 113–129. MR**369018**, DOI 10.2307/2271891 - Sy D. Friedman,
*Fine structure and class forcing*, De Gruyter Series in Logic and its Applications, vol. 3, Walter de Gruyter & Co., Berlin, 2000. MR**1780138**, DOI 10.1515/9783110809114 - Sy D Friedman,
*Constructibility and class forcing*, Handbook of set theory. In 3 volumes, Springer, Dordrecht, 2010, pp. 557–604. - Sy-David Friedman, Victoria Gitman, and Vladimir Kanovei,
*A model of second-order arithmetic satisfying AC but not DC*, J. Math. Log.**19**(2019), no. 1, 1850013, 39. MR**3960895**, DOI 10.1142/S0219061318500137 - Sy David Friedman and David Schrittesser,
*Projective measure without projective Baire*, Mem. Amer. Math. Soc.**267**(2020), no. 1298, v+150. MR**4194891**, DOI 10.1090/memo/1298 - Gunter Fuchs,
*Blurry definability*, Mathematics**10 (3)**(2022), no. 3, Article No 452. DOI 10.3390/math10030452. - Gunter Fuchs, Victoria Gitman, and Joel David Hamkins,
*Ehrenfeucht’s lemma in set theory*, Notre Dame J. Form. Log.**59**(2018), no. 3, 355–370. MR**3832085**, DOI 10.1215/00294527-2018-0007 - Mohammad Golshani, Vladimir Kanovei, and Vassily Lyubetsky,
*A Groszek-Laver pair of undistinguishable $\mathsf E_0$-classes*, MLQ Math. Log. Q.**63**(2017), no. 1-2, 19–31. MR**3647830**, DOI 10.1002/malq.201500020 - J. Hadamard, R. Baire, H. Lebesgue, and E. Borel,
*Cinq lettres sur la théorie des ensembles*, Bull. Soc. Math. Fr.**33**(1905), 261–273 (French). - Joel David Hamkins and Cole Leahy,
*Algebraicity and implicit definability in set theory*, Notre Dame J. Form. Log.**57**(2016), no. 3, 431–439. MR**3521491**, DOI 10.1215/00294527-3542326 - Leo Harrington,
*The constructible reals can be anything*, Preprint dated May 1974 with several addenda dated up to October 1975: (A) Models where Separation principles fail, May 74; (B) Separation without Reduction, April 75; (C) The constructible reals can be (almost) anything, Part II, May 75. Available at http://logic-library.berkeley.edu/catalog/detail/2135. Downloadable from http://iitp.ru/upload/userpage/247/74harr.pdf. - Peter G. Hinman,
*Recursion-theoretic hierarchies*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin-New York, 1978. MR**499205**, DOI 10.1007/978-3-662-12898-5 - Thomas Jech,
*Set theory*, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003. The third millennium edition, revised and expanded. MR**1940513** - R. B. Jensen and R. M. Solovay,
*Some applications of almost disjoint sets*, Mathematical Logic and Foundations of Set Theory (Proc. Internat. Colloq., Jerusalem, 1968) North-Holland, Amsterdam, 1970, pp. 84–104. MR**0289291** - Ronald B. Jensen and Håvard Johnsbråten,
*A new construction of a non-constructible $\Delta _{3}^{1}$ subset of $\omega$*, Fund. Math.**81**(1974), 279–290. MR**419229**, DOI 10.4064/fm-81-4-279-290 - V. G. Kanoveĭ,
*The set of all analytically definable sets of natural numbers can be analytically definable*, Izv. Akad. Nauk SSSR Ser. Mat.**43**(1979), no. 6, 1259–1293 (Russian). MR**567036** - Vladimir Kanovei and Vassily Lyubetsky,
*Definable $\mathsf {E}_0$ classes at arbitrary projective levels*, Ann. Pure Appl. Logic**169**(2018), no. 9, 851–871. MR**3808398**, DOI 10.1016/j.apal.2018.04.006 - Vladimir Kanovei and Vassily Lyubetsky,
*Non-uniformizable sets of second projective level with countable cross-sections in the form of Vitali classes*, Izvestiya: Mathematics**82**(2018), no. 1, 61–90, doi:10.1070/IM8521. - Vladimir Kanovei and Vassily Lyubetsky,
*Definable minimal collapse functions at arbitrary projective levels*, J. Symb. Log.**84**(2019), no. 1, 266–289. MR**3922793**, DOI 10.1017/jsl.2018.77 - Vladimir Kanovei and Vassily Lyubetsky,
*Non-uniformizable sets with countable cross-sections on a given level of the projective hierarchy*, Fund. Math.**245**(2019), no. 2, 175–215. MR**3914942**, DOI 10.4064/fm517-7-2018 - Vladimir Kanovei and Vassily Lyubetsky,
*On the ‘definability of definable’ problem of Alfred Tarski*, Mathematics**8**(2020), no. 12, 1–36, Article No 2214, Open access doi:10.3390/math8122214. - Vladimir Kanovei and Vassily Lyubetsky,
*On the $\Delta ^1_n$ problem of Harvey Friedman*, Mathematics**8**(2020), no. 9, 1–30, Article No 1477, Open access doi:10.3390/math8091477. - Vladimir Kanovei and Vassily Lyubetsky,
*Models of set theory in which separation theorem fails*, Izv. Math.**85**(2021), no. 6, 1181–1219, doi:10.1070/IM8521. - Vladimir Kanovei and Vassily Lyubetsky,
*The full basis theorem does not imply analytic wellordering*, Ann. Pure Appl. Logic**172**(2021), no. 4, Paper No. 102929, 46. MR**4191899**, DOI 10.1016/j.apal.2020.102929 - Vladimir Kanovei and Vassily Lyubetsky,
*A generic model in which the Russell-nontypical sets satisfy ZFC strictly between HOD and the universe*, Mathematics**10**(2022), no. 3, 1–16, Article No 491, doi:10.3390/math10030491. - Asaf Karagila,
*The Bristol model: an abyss called a Cohen real*, J. Math. Log.**18**(2018), no. 2, 1850008, 37. MR**3878470**, DOI 10.1142/S0219061318500083 - S. C. Kleene,
*Arithmetical predicates and function quantifiers*, Trans. Amer. Math. Soc.**79**(1955), 312–340. MR**70594**, DOI 10.1090/S0002-9947-1955-0070594-4 - S. C. Kleene,
*Recursive functionals and quantifiers of finite types. I*, Trans. Amer. Math. Soc.**91**(1959), 1–52. MR**102480**, DOI 10.1090/S0002-9947-1959-0102480-9 - S. R. Kogalovskiĭ,
*Certain simple consequences of the axiom of constructibility*, Fund. Math.**82**(1974/75), 245–267 (Russian, with English summary). MR**363895** - S. R. Kogalovskiĭ and M. A. Rorer,
*On the question of the definability of the concept of definability*, Ivanov. Gos. Ped. Inst. Učen. Zap.**125**(1973), 46–72 (Russian). Logic, algebra and numerical analysis, Vol. 2, No. 2. MR**491003** - Roman Kossak,
*Undefinability of truth and nonstandard models*, Ann. Pure Appl. Logic**126**(2004), no. 1-3, 115–123. Provinces of logic determined. MR**2060928**, DOI 10.1016/j.apal.2003.10.011 - Kenneth Kunen,
*Set theory*, Studies in Logic (London), vol. 34, College Publications, London, 2011. MR**2905394** - Paul Larson and Jindřich Zapletal,
*Canonical models for fragments of the axiom of choice*, J. Symb. Log.**82**(2017), no. 2, 489–509. MR**3663414**, DOI 10.1017/jsl.2017.29 - A. R. D. Mathias,
*Surrealist landscape with figures (a survey of recent results in set theory)*, Period. Math. Hungar.**10**(1979), no. 2-3, 109–175. MR**539225**, DOI 10.1007/BF02025889 - Yiannis N. Moschovakis,
*Descriptive set theory*, Studies in Logic and the Foundations of Mathematics, vol. 100, North-Holland Publishing Co., Amsterdam-New York, 1980. MR**561709** - Roman Murawski,
*Undefinability of truth. The problem of priority: Tarski vs Gödel*, Hist. Philos. Logic**19**(1998), no. 3, 153–160. MR**1664747**, DOI 10.1080/01445349808837306 - Alfred Tarski,
*Der Wahrheitsbegriff in den formalisierten Sprachen*, Stud. Philos.**1**(1935), 261–401 (German). - Alfred Tarski,
*A problem concerning the notion of definability*, J. Symbolic Logic**13**(1948), 107–111. MR**26625**, DOI 10.2307/2267331 - Athanassios Tzouvaras,
*Typicality á la Russell in set theory*, Notre Dame J. Form. Logic.**63**(2):185–196, DOI 10.1215/00294527-2022-0011.

## Additional Information

**Vladimir Kanovei**- Affiliation: Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute), 19, Build.1, Bolshoy Karetny per., Moscow 127051, Russia
- MR Author ID: 97930
- ORCID: 0000-0001-7415-9784
- Email: kanovei@iitp.ru
**Vassily Lyubetsky**- Affiliation: Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute), 19, Build.1, Bolshoy Karetny per., Moscow 127051, Russia
- MR Author ID: 209834
- ORCID: 0000-0002-3739-9161
- Email: lyubetsk@iitp.ru
- Received by editor(s): April 22, 2021
- Received by editor(s) in revised form: February 20, 2022, and March 18, 2022
- Published electronically: October 3, 2022
- Additional Notes: The first author was supported by the Russian Foundation for Basic Research RFBR grant number 20-01-00670. The second author was supported by the Russian Foundation for Basic Research RFBR grant number 20-01-00670
- © Copyright 2022 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**375**(2022), 8651-8686 - MSC (2020): Primary 03E35; Secondary 03E15, 03E47, 03B38
- DOI: https://doi.org/10.1090/tran/8710