chebЧебышевский сборникChebyshevskii Sbornik2226-8383Tula State Lev Tolstoy Pedagogical University10.22405/2226-8383-2021-22-1-304-327cheb-948Research ArticleСтатьиArticleРешетка определимости. Источники и направления исследованийThe lattice of definability. Origins and Directions of ResearchСеменовАлексей ЛьвовичSemenovAlexey Lvovichalsemno@ya.ruСопруновСергей ФедоровичSoprunovSergey Fedorovichsoprunov@mail.ruМосковский государственный университет им. М. В. Ломоносова, Институт кибернетики и образовательной информатики им. А. И. Берга ФИЦ ИУ РАНРоссияLomonosov Moscow State University, Axel Berg Institute of Cybernetics and Educational Computing FRC SCS of the Russian Academy of SciencesRussian FederationЦентр педагогического мастерства Департамента образования и науки Москвы, Институт кибернетики и образовательной информатики им. А. И. Берга ФИЦ ИУ РАНРоссияCenter for pedagogical excellence, Axel Berg Institute of Cybernetics and Educational Computing FRC SCS of the Russian Academy of SciencesRussian Federation202106042021221304327Copyright © Семенов А.Л., Сопрунов С.Ф., 20212021Семенов А.Л., Сопрунов С.Ф.Semenov A.L., Soprunov S.F.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.chebsbornik.ru/jour/article/view/948

В статье представлены результаты и открытые проблемы, относящиеся к пространствам определимости (редуктам), а также источникам этой области, начиная с XIX века. Исследуются условия конечности и ограничения, в том числе глубина чередования кванторов и число аргументов. Описаны результаты, относящиеся к описанию решетокпространств определимости для числовых и других естественных структур. Методы исследования включают изучение групп автоморфизмов элементарных расширений рассматриваемых структур, использование теоремы Свенониуса

The article presents results and open problems related to definability spaces (reducts) and sources of this field since the XIX century. Finiteness conditions and constraints are investigated,including the depth of quantifier alternation and the number of arguments. Results related to the description of lattices of definability spaces for numerical and other natural structuresare described. Research methods include the study of automorphism groups of elementary extensions of the structures under consideration, application of the Svenonius theorem.

определимостьпространство определимостиредуктытеорема Све- нониусаэлиминация кванторовразрешимостьавтоморфизмыdefinabilitydefinability spacereductsSvenonius theoremquantifier eliminationdecidabilityautomorphismsРабота выполнена при поддержке РНФ (А. Л. Семенов, грант № 17-11-01377 – разделы 1, 3, 5) и РФФИ (С. Ф. Сопрунов, грант № 19-29-14199 – разделы 2, 4)ReferencesTarski Alfred. What are logical notions? // History and philosophy of logic, 1986, 7.2. — Pp. 143–154.Addison, Jr. J. W. 1965, “The undefinability of the definable“, Notices Amer. Math. Soc., 12,Buchi J. Richard, Danhof Kenneth J. Definibility in normal theories. // Israel Journal of Mathematics, 1973, 14.3. — Pp. 248–256.pp. 347.Smith James T. Definitions and nondefinability in geometry. // The American Mathematical Monthly, 2010, 117.6. — Pp. 475–489.Ahlbrandt, Gisela & Ziegler, Martin. 1992, “Invariant subgroups of 𝑉 𝑉 “, J. Algebra, 151, no. 1,Hodges Wilfrid. Model Theory (Draft 20 Jul 2000) // 2000. [Электронный ресурс] URL: http://wilfridhodges.co.uk/history07.pdf (дата обращения 25 декабря 2020 г.).pp. 26–38.Peacock George. Report on the recent progress and present state of certain branches of analysis. // Report of the third meeting of the British Association for the Advancement of Science held at Cambridge in 1833, John Murrary, London, 1834. — Pp. 185–352.B`es, Alexis & C´egielski, Patrick. 2008, “Weakly maximal decidable structures“, RAIRO –Boole George. The mathematical analysis of logic. // Philosophical Library, 1847.Theoretical Informatics and Applications, 42.01, pp. 137–145.Frege Gottlob. Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinenB`es, Alexis & C´egielski, Patrick. 2009, “Nonmaximal decidable structures“, Journal of MathematicalDenkens. // Halle, 1879. Translated in van Heijenoort J. Begriffsschrift, a formula language,Sciences, 158.5, pp. 615–622.modeled upon that of arithmetic, for pure thought. From Frege to G¨odel: A Source Book in Mathematical Logic. 1931. — Pp. 3–82.Beth, Evert W. 1953, “On Padoa’s method in the theory of definition“, Indag. Math, 15, pp. 330–Frege Gottlob. Grundgesetze der Arithmetik. // 1893. Publ. by Jena: Verlag Hermann Pohle, Band I/II. Partial translation of Band I, The Basic Laws of Arithmetic, by M. Furth. Berkeley:Frege Gottlob. Grundgesetze der Arithmetik. // 1893. Publ. by Jena: Verlag Hermann Pohle, Band I/II. Partial translation of Band I, The Basic Laws of Arithmetic, by M. Furth. Berkeley:U. of California Press, 1964.Bodirsky, M. & Macpherson, D. 2013, “Reducts of structures and maximal-closed permutationPeirce Charles Sanders. Description of a notation for the logic of relatives, resulting from an amplification of the conceptions of Boole’s calculus of logic. // Memoirs of the American academy of arts and sciences, 1873, vol. 9, part 2. — Pp. 317–378.groups“, arXiv:1310.6393.Peirce Charles Sanders. On the algebra of logic: A contribution to the philosophy of notation.Bodirsky, Manuel, Pinsker, Michael & Pongr´acz, Andr´as. 2013, “The 42 reducts of the random// American journal of mathematics, 1885, 7.2. – Pp. 180–196.ordered graph“, arXiv:1309.2165.L¨owenheim Leopold. ¨Uber m¨oglichkeiten im relativkalk¨ul. // Mathematische Annalen, 1915,Bodirsky, Manuel, Pinsker, Michael & Tsankov, Todor. 2011, “Decidability of definability.“ IEEE4. – Pp. 447–470.th Annual Symposium on Logic in Computer Science, pp. 321–328.Skolem Thoralf. Logisch-kombinatorische Untersuchungen ¨uber die Erfullbarkeit oder BeweisbarkeitBoole, George. 1847, The mathematical analysis of logic, Philosophical Library.mathematischer Sdtze nebst einem Theorem ¨uber dichte Mengen. // VidenskapsselskapetsBuchi, J. Richard & Danhof, Kenneth J. 1973, “Definibility in normal theories“, Israel Journalskrifter, I. Matematisk-naturvidenskabelig klasse 4, 1920.of Mathematics, 14.3, pp. 248–256.Schr¨oder Ernst. On Pasigraphy. Its Present State and the Pasigraphic Movement in Italy. //Cameron, Peter J. 1976, “Transitivity of permutation groups on unordered sets“. MathematischeThe Monist, 1898, 9.1. – Pp. 44–62.Zeitschrift, 148.2. – Pp. 127–139.Schr¨oder E. Vorlesungen ¨uber die Algebra der Logik. Volumes 1 to 3. // Teubner, Leipzig.Duporcq, Ernest, ed. 1902, Compte rendu du deuxi`eme congr`es international des math´ematiciensReprinted by Chelsea, New York, 1966.tenu `a Paris du 6 au 12 aoˆut 1900: proc`es-verbaux et communications, Gauthier-Villars,International Congress of Philosophy. // Biblioth`eque du Congr`es International de Philosophie,imprimeur-library, 455 pp.Four volumes. Paris: Librairie Armand Colin, 1900–1903.Elgot, Calvin C. & Rabin, Michael O. 1966, “Decidability and Undecidability of ExtensionsCompte rendu du deuxi`eme сongr`es international des math´ematiciens tenu `a Paris du 6 au 12of Second (First) Order Theory of (Generalized) Successor“, J. Symb. Log., Vol. 31, No. 2,aoˆut 1900: proc`es-verbaux et communications. // Publies par Ernest Duporcq. Gauthier-Villars, imprimeur-libraire, 1902. – 455 pp.pp. 169–181.Hilbert David. Mathematische probleme. // Nachrichten von der Gesellschaft der WissenschaftenFrasnay, Claude. 1965, “Quelques probl`emes combinatoires concernant les ordres totaux et leszu G¨ottingen, Mathematisch-Physikalische Klasse, 1900. – Pp. 253–297.relations monomorphes“, Annales de l’ institut Fourier, vol. 15, No. 2, pp. 415–524.Padoa Alessandro. Logical introduction to any deductive theory. // 1900. Опубл. в сб. FromFrege, G. 1879, Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinenFrege to G¨odel. A Source Book in Mathematical Logic, 1879–1931. Ed. by Jean van Heijenoort.Denkens, Halle. Translated in van Heijenoort J. 1931, Begriffsschrift, a formula language,Cambridge, Mass., Harvard University Press, 1967. – Pp. 118—123.modeled upon that of arithmetic, for pure thought. From Frege to G¨odel: A Source Book inPieri Mario. La geometria elementare istituita sulle nozioni ‘punto’ ´e ‘sfera’. // Memorie diMathematical Logic, pp. 3–82.matematica e di fisica della Societ`a italiana delle scienze, 1908, 15. – Pp. 345–450.Frege, G. 1893, Grundgesetze der arithmetik, Publ. in 1964 by Jena: Verlag Hermann Pohle,Lindenbaum A., Tarski A. ¨Uber die Beschr¨anktheit der Ausdrucksmittel deduktiver Theorien.Band I/II. Partial translation of Band I, The Basic Laws of Arithmetic, by M. Furth, Berkeley:// Ergebnisse eines Mathematischen Kolloquiums, Heft 7, 1935. – Pp. 15–22. Пер. на англ.:U. of California Press.On the Limitations of the Means of Expression of Deductive Theories. // Alfred Tarski. Logic,Hilbert, David. 1900, “Mathematische probleme“, Nachrichten von der Gesellschaft der WissenschaftenSemantics, Metamathematics. // J. Corcoran, ed., Hackett, Indianapolis, 1956. – Pp. 384–392.zu G¨ottingen, Mathematisch-Physikalische Klasse, pp. 253–297.Huntington Edward V. Inter-Relations Among the Four Principal Types of Order. //Hodges, Wilfrid. 1993, “Model theory“, Encyclopedia of Mathematics and its Applications,Transactions of the American Mathematical Society, 1935, 38.1. – Pp. 1–9.vol. 42, Cambridge University Press, Cambridge.Tarski Alfred. The Concept of Truth in Formalized Languages. // Alfred Tarski: Logic,Hodges, Wilfrid. 2000, Model Theory (Draft 20 Jul 2000). Available at: http://wilfridhodges.Semantics, Metamathematics. Trans. J. H.Woodger, second edition ed. and introduced by Johnco.uk/history07.pdf (accessed 25 December 2020).Corcoran, Hackett, Indianapolis, 1983. – Pp. 152–278.Huntington, Edward V. 1904, “The continuum as a type of order: an exposition of the modelLangford Cooper Harold. Some theorems on deducibility. // Annals of Mathematics Secondtheory“, Ann. Math., 6, pp. 178–179.Series, 1926–1927, vol. 28, No. 1/4. – Pp. 16–40.Huntington, Edward V. 1906, “The Fundamental Laws of Addition and Multiplication inLangford Cooper Harold. Theorems on Deducibility (Second paper). // Annals of Mathematics,Elementary Algebra“, The Annals of Mathematics, 8.1, pp. 1–44.Second Series, 1926–1927,Vol. 28, No. 1/4. – Pp. 459–471.Huntington, Edward V. 1935, “Inter-Relations Among the Four Principal Types of Order“,Presburger M. ¨Uber die vollst¨andigkeit eines gewissen systems der arithmetik ganzer zahlen,Transactions of the American Mathematical Society, 38.1, pp. 1–9.in welchem die addition als einzige operation hervortritt. // Sprawozdanie z 1 KongresuInternational Congress of Philosophy. 1900–1903, Biblioth`eque du Congr`es International deMatematyk´ow Krajow Slowianskich, Ksiaznica Atlas, 1930. – Pp. 92–10. Пер. на англ.: OnPhilosophie, Four volumes. Paris: Librairie Armand Colin.the completeness of a certain system of arithmetic of whole numbers in which addition occursJunker, Markus & Ziegler, Martin. 2008, “The 116 reducts of (Q, <, 𝑎)“, Journal of Symbolicas the only operation. // History and Philosophy of Logic, 12(2), 1991. – Pp. 225–233.Logic, vol. 73, issue 3, pp. 861–884. DOI: https://doi.org/10.2178/jsl/1230396752Skolem Torlaf. ¨Uber gewisse Satzfunktionen in der Arithmetik. // Skrifter utgit av VidenskapsselskapetKaplan, I. & Simon, P. 2013, “The affine and projective groups are maximal“, arXiv:1310.8157.i Kristiania, I. klasse 7, 1930.Klein, Felix. 1872, Vergleichende betrachtungen ¨uber neuere geometrische forsuchungen,Mostowski Andrzej. On direct products of theories. // Journal of Symbolic Logic, 1952, vol. 17. –A. Deichert.Pp. 1—31.Korec, Ivan. 2001, “A list of arithmetical structures complete with respect to the first-orderTarski Alfred. A decision method for elementary algebra and geometry. // Prepared fordefinability“, Theoretical computer science, 257.1, pp. 115–151.publication with the assistance of J. C. C. McKinsey. Second edition, revised. Lithoprinted.Langford, Cooper Harold. 1926–1927, “Some theorems on deducibility“, Annals of MathematicsUniversity of California Press, Berkeley and Los Angeles, 1951. – 63 pp.Second Series, Vol. 28, No. 1/4, pp. 16–40.Семенов А. Л. Условия конечности для алгебр отношений. // Труды математического ин-Langford, Cooper Harold. 1926–1927, “Theorems on Deducibility (Second paper)“, Annals ofститута им. В. А. Стеклова, 2003, т. 242. — С. 103–107.Mathematics, Second Series, Vol. 28, No. 1/4, pp. 459–471.Семенов А. Л., Сопрунов С. Ф. Конечные кванторные иерархии в алгебрах отношений. //Lindenbaum, A. & Tarski, A. 1935, “ ¨Uber die Beschr¨anktheit der Ausdrucksmittel deduktiverТруды Математического института им. В. А. Стеклова, 2011, т. 274. – C. 291–296.Theorien“, Ergebnisse eines Mathematischen Kolloquiums, Heft 7, pp. 15–22. (Engl. trans.: “OnСеменов А. Л. О некоторых расширениях арифметики сложения натуральных чисел //the Limitations of the Means of Expression of Deductive Theories“, In Alfred Tarski: Logic,Известия Академии наук СССР. Серия математическая. 1979. Т. 43, № 5. – С. 1175–1195.Semantics, Metamathematics, J. Corcoran, ed., Hackett, Indianapolis, 1956, pp. 384–392.Rabin Michael O. Decidability of second-order theories and automata on infinite trees. //L¨owenheim, Leopold. 1915, “ ¨Uber m¨oglichkeiten im relativkalk¨ul“, Mathematische Annalen,Transactions of the American Mathematical Society, 1969, 141. – pp. 1–35.4, pp. 447–470.Muchnik An. A. Games on infinite trees and automata with dead-ends. A new proof for theMacpherson, D. 2011, “A survey of homogeneous structures“, Discrete Mathematics, vol. 311,decidability of the monadic second order theory of two successors. // Bull. EATCS, 1992, 48. –No 15, pp. 1599–1634.Pp. 220–267.Marker, D.& Pillay, A. 1990, “Reducts of (𝐶,+, ·) which contain +“, Journal of Symbolic Logic,Elgot Calvin C., Rabin Michael O. Decidability and Undecidability of Extensions of Secondvol. 55, issue 3, pp. 1243–1251.(First) Order Theory of (Generalized) Successor. // J. Symb. Log., 1966, vol. 31, No. 2. –Marker, D., Peterzil, Y. A.& Pillay, A. 1992, “Additive reducts of real closed fields“, The JournalPp. 169–181.of symbolic logic, vol. 57, issue 1, pp. 109–117. DOI: https://doi.org/10.2307/2275179.Сопрунов С. Ф. Разрешимые обогащения структур. // Вопросы кибернетики, 1988, т. 134. –Mostowski, Andrzej. 1952, “On direct products of theories“, Journal of Symbolic Logic, vol. 17,С. 175–179.pp. 1–31.B`es Alexis, C´egielski Patrick. Weakly maximal decidable structures. // RAIRO – TheoreticalMuchnik, An. A. 1992, “Games on infinite trees and automata with dead-ends. A new proofInformatics and Applications, 2008, 42.01. – Pp. 137–145.for the decidability of the monadic second order theory of two successors“, Bull. EATCS, 48,B`es Alexis, C´egielski Patrick. Nonmaximal decidable structures. // Journal of Mathematicalpp. 220–267.Sciences, 2009, 158.5. – Pp. 615–622.Muchnik, An. A. 2003, “The definable criterion for definability in Presburger arithmetic and itsTarski Alfred. Der Wahrheitsbegriff in den formalisierten Sprachen. // Studia Philosophica,applications“, Theoretical Computer Science, 290.3, pp. 1433–1444., vol. 1. – Pp. 261–405.Padoa Alessandro. 1900, “Logical introduction to any deductive theory“, In From Frege to G¨odel.Tarski Alfred. Einige methodologifche Unterfuchungen ¨uber die Definierbarkeit der Begriffe. //A Source Book in Mathematical Logic, 1879–1931. Ed. by Jean van Heijenoort. Cambridge,Erkenntnis, 1935, 5.1. – Pp. 80–100.Mass., Harvard University Press, pp. 118—123.Beth Evert W. On Padoa’s method in the theory of definition. // Indag. Math, 1953, 15. –Peacock, George. 1834, “Report on the recent progress and present state of certain branches ofPp. 330–339.analysis“, Report of the third meeting of the British Association for the Advancement of ScienceSvenonius Lars. A theorem on permutations in models. // Theoria, 1959, 25.3. – Pp. 173–178.held at Cambridge in 1833, John Murrary, London, pp. 185–352.Klein Felix. Vergleichende betrachtungen ¨uber neuere geometrische forsuchungen. //Peirce, Charles Sanders. 1873, “Description of a notation for the logic of relatives, resultingA. Deichert, 1872.from an amplification of the conceptions of Boole’s calculus of logic“, Memoirs of the AmericanHuntington Edward V. The fundamental laws of addition and multiplication in elementaryacademy of arts and sciences, vol. 9, part 2, pp. 317–378.algebra. // The Annals of Mathematics, 1906, 8.1. – Pp. 1–44.Peirce, Charles Sanders. 1885, “On the algebra of logic: A contribution to the philosophy ofSemenov A. L., Soprunov S. F. A combinatorial version of the Svenonius theorem on definability,notation“, American journal of mathematics, 7.2, pp. 180–196.Logic Journal of IGPL. – 23.6 (2015): 966–975.Peterzil, Ya’acov. 1993, “Reducts of some structures over the reals“, Journal of Symbolic Logic,Macpherson D. A survey of homogeneous structures. // Discrete Mathematics, 2011, vol. 311,3, pp. 955–966. DOI: https://doi.org/10.2307/2275107.No. 15. – Pp. 1599–1634.Pieri, Mario. 1908, “La geometria elementare istituita sulle nozioni ‘punto’ ´e ‘sfera’“, MemorieHodges Wilfrid. Model theory. // Encyclopedia of Mathematics and its Applications, 1993,di matematica e di fisica della Societ`a italiana delle scienze, 15, pp. 345–450.vol. 42, Cambridge University Press, Cambridge.Presburger, M. 1930, “ ¨Uber die Vollst¨andigkeit eines gewissen Systems der ArithmetikKorec Ivan. A list of arithmetical structures complete with respect to the first-order definability.ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt“, Sprawozdanie z// Theoretical computer science, 2001, 257.1. – Pp. 115–151.Kongresu Matematyk´ow Krajow Slowianskich, Ksiaznica Atlas. pp. 92–10. (Translated: “OnСеменов А. Л. Пресбургеровость предикатов, регулярных в двух системах счисления. //the completeness of a certain system of arithmetic of whole numbers in which addition occursСибирский математический журнал, 1977, т. 18, № 2. — С. 403–418.as the only operation“, History and Philosophy of Logic, 12(2), 1991, pp. 225–233.)Frasnay Claude. Quelques probl`emes combinatoires concernant les ordres totaux et les relationsRabin, Michael O. 1969, “Decidability of second-order theories and automata on infinite trees“,monomorphes. // Annales de l’ institut Fourier, 1965, vol. 15, No. 2. – Pp. 415–524.Transactions of the American Mathematical Society, 141, pp. 1–35.Huntington Edward V. The continuum as a type of order: an exposition of the model theory.Rado, Richard. 1964, “Universal graphs and universal functions“, Acta Arithmetica, 9.4, pp. 331–// Ann. Math., 1904, 6. – Pp. 178–179.// Ann. Math., 1904, 6. – Pp. 178–179.Cameron Peter J. Transitivity of permutation groups on unordered sets. // MathematischeSchr¨oder, Ernst. 1898, “On Pasigraphy. Its Present State and the Pasigraphic Movement inZeitschrift, 1976, 148.2, Pp. 127–139.Italy“, The Monist, 9.1, pp. 44–62.Winkler Peter. Random structures and zero-one laws. Finite and infinite combinatorics in setsSchr¨oder, Ernst. 1966, Vorlesungen ¨uber die Algebra der Logik, Volumes 1 to 3. Teubner, Leipzig.and logic, Springer Netherlands, 1993. – Pp. 399–420.Reprinted by Chelsea, New York.Rado Richard. Universal graphs and universal functions. // Acta Arithmetica, 1964, 9.4. –Semenov, A. L. 1977, “Presburgerness of Predicates Regular in Two Number Systems“, SiberianPp. 331–340.Math. J., 18.2, pp. 289–300.Thomas Simon. Reducts of random hypergraphs. // Annals of Pure and Applied Logic, 1996,Semenov, A. L. 1980, “On certain extensions of the arithmetic of addition of natural numbers”,2. – Pp. 165–193.Izvestiya: Mathematics, 15.2, pp. 401–418.Thomas Simon. Reducts of the random graph. // Journal of Symbolic Logic, 1991, 56(1). –Semenov, A. L. 2003, “Finiteness Conditions for Algebras of Relations“, Proceedings of thePp. 176–181.Steklov Institute of Mathematics, 242, pp. 92–96.)Bodirsky Manuel, Pinsker Michael, Pongr´acz Andr´as. The 42 reducts of the random orderedSemenov, A. & Soprunov, S. 2011, “Finite quantifier hierarchies in relational algebras“,graph. // 2013, arXiv:1309.2165.Proceedings of the Steklov I Institute of Mathematics, 274.1, pp. 267–272.Junker Markus, Ziegler Martin. The 116 reducts of (Q, <, 𝑎). // Journal of Symbolic Logic,Semenov, A. L. & Soprunov, S. F. 2012, “Lattice of relational algebras definable in integers with, vol. 73, issue 3. – Pp. 861–884. DOI: https://doi.org/10.2178/jsl/1230396752.successor“, arXiv:1201.4439.Ahlbrandt Gisela, Ziegler Martin. Invariant subgroups of 𝑉 𝑉 . // J. Algebra, 1992, 151, no. 1. –Semenov, A. L. & Soprunov, S. F. 2013, A combinatorial version of the Svenonius theorem onPp. 26–38.definability, Logic Journal of IGPL. – 23.6 (2015): 966–975.Bodirsky M., Macpherson D. Reducts of structures and maximal-closed permutation groups.Skolem, Thoralf. 1920, “Logisch-kombinatorische Untersuchungen ¨uber die Erfullbarkeit oder// 2013, arXiv:1310.6393.Beweisbarkeit mathematischer Sdtze nebst einem Theorem ¨uber dichte Mengen“, VidenskapsselskapetsKaplan I., Simon P. The affine and projective groups are maximal. // 2013, arXiv:1310.8157.skrifter, I. Matematisk-naturvidenskabelig klasse 4.Marker D., Peterzil Y. A., Pillay A. Additive reducts of real closed fields. // The Journal ofSkolem, Torlaf. 1930, “ ¨Uber gewisse Satzfunktionen in der Arithmetik“, Skrifter utgit avsymbolic logic, 1992, vol. 57, issue 1. – Pp. 109–117. DOI: https://doi.org/10.2307/2275179.Videnskapsselskapet i Kristiania, I. klasse 7.Peterzil Ya’acov. Reducts of some structures over the reals. // Journal of Symbolic Logic, 1993,Smith, James T. 2010, “Definitions and Nondefinability in Geometry“, The American Mathematical3. – Pp. 955–966. DOI: https://doi.org/10.2307/2275107.Monthly, 117.6, pp. 475–489.Marker D., Pillay A. Reducts of (C,+, ·) which contain +. // Journal of Symbolic Logic, 1990,Soprunov, S. 1988, “Razreshimye obogashchenia struktur – Decidable expansions of structures“,vol. 55, issue 3. – Pp. 1243–1251.Vopr. Kibern., 134, pp. 175–179 (in Russian).Semenov A. L., Soprunov S. F. Lattice of relational algebras definable in integers with successor.Svenonius, Lars. 1959, “A theorem on permutations in models“, Theoria, 25.3, pp. 173–178.// 2012, arXiv:1201.4439Tanaka, Hisao. 1967, “Some results in the effective descriptive set theory“, Publications of theBodirsky Manuel, Pinsker Michael, Tsankov Todor. Decidability of definability. // IEEE 26thResearch Institute for Mathematical Sciences, 3.1, pp. 11–52.Annual Symposium on Logic in Computer Science, 2011. – Pp. 321–328.Tarski, Alfred. 1935, “DerWahrheitsbegriff in den formalisierten Sprachen“, Studia Philosophica,Muchnik An. A. The definable criterion for definability in Presburger arithmetic and itsvol. 1, pp. 261–405.applications. // Theoretical Computer Science, 2003, 290.3. – Pp. 1433–1444.Tarski, Alfred. 1935, “Einige methodologifche Unterfuchungen ¨uber die Definierbarkeit derAddison Jr. J. W. The undefinability of the definable. // Notices Amer. Math. Soc., 1965, 12. –Begriffe“, Erkenntnis, 5.1, pp. 80–100.Pp. 347.Tarski, Alfred. 1951, A decision method for elementary algebra and geometry. Prepared forTanaka Hisao. Some results in the effective descriptive set theory. // Publications of thepublication with the assistance of J. C. C. McKinsey. Second edition, revised. Lithoprinted.Research Institute for Mathematical Sciences, 1967, 3.1. – Pp. 11–52.University of California Press, Berkeley and Los Angeles, iii + 63 pp.Tarski, Alfred. 1983, “The Concept of Truth in Formalized Languages“, Alfred Tarski: Logic,Tarski, Alfred. 1983, “The Concept of Truth in Formalized Languages“, Alfred Tarski: Logic,Semantics, Metamathematics. Trans. J. H. Woodger, second edition ed. and introduced by JohnSemantics, Metamathematics. Trans. J. H. Woodger, second edition ed. and introduced by JohnCorcoran, Hackett, Indianapolis, pp. 152–278.Corcoran, Hackett, Indianapolis, pp. 152–278.Tarski, Alfred. 1986, “What are logical notions?“ History and philosophy of logic, 7.2, pp. 143–Tarski, Alfred. 1986, “What are logical notions?“ History and philosophy of logic, 7.2, pp. 143–Thomas, Simon. 1991, “Reducts of the random graph“, Journal of Symbolic Logic, 56(1), pp. 176–Thomas, Simon. 1991, “Reducts of the random graph“, Journal of Symbolic Logic, 56(1), pp. 176–Thomas, Simon. 1996, “Reducts of random hypergraphs“, Annals of Pure and Applied Logic,Thomas, Simon. 1996, “Reducts of random hypergraphs“, Annals of Pure and Applied Logic,2, pp. 165–193.2, pp. 165–193.Winkler, Peter. 1993, Random structures and zero-one laws. Finite and infinite combinatoricsWinkler, Peter. 1993, Random structures and zero-one laws. Finite and infinite combinatoricsin sets and logic, Springer Netherlands, pp. 399–420.in sets and logic, Springer Netherlands, pp. 399–420.

The authors declare that there are no conflicts of interest present.