Решетка определимости. Источники и направления исследований
https://doi.org/10.22405/2226-8383-2021-22-1-304-327
Аннотация
В статье представлены результаты и открытые проблемы, относящиеся к пространствам определимости (редуктам), а также источникам этой области, начиная с XIX века. Исследуются условия конечности и ограничения, в том числе глубина чередования кванторов и число аргументов. Описаны результаты, относящиеся к описанию решеток
пространств определимости для числовых и других естественных структур. Методы исследования включают изучение групп автоморфизмов элементарных расширений рассматриваемых структур, использование теоремы Свенониуса
Ключевые слова
определимость,
пространство определимости,
редукты,
теорема Све- нониуса,
элиминация кванторов,
разрешимость,
автоморфизмы
При поддержке: Работа выполнена при поддержке РНФ (А. Л. Семенов, грант № 17-11-01377 – разделы 1, 3, 5) и РФФИ (С. Ф. Сопрунов, грант № 19-29-14199 – разделы 2, 4)
Об авторах
Алексей Львович Семенов
Московский государственный университет им. М. В. Ломоносова, Институт кибернетики и образовательной информатики им. А. И. Берга ФИЦ ИУ РАН
Россия
Россия
Сергей Федорович Сопрунов
Центр педагогического мастерства Департамента образования и науки Москвы, Институт кибернетики и образовательной информатики им. А. И. Берга ФИЦ ИУ РАН
Россия
Россия
Список литературы
1. Tarski Alfred. What are logical notions? // History and philosophy of logic, 1986, 7.2. — Pp. 143–154.
2. Buchi J. Richard, Danhof Kenneth J. Definibility in normal theories. // Israel Journal of Mathematics, 1973, 14.3. — Pp. 248–256.
3. Smith James T. Definitions and nondefinability in geometry. // The American Mathematical Monthly, 2010, 117.6. — Pp. 475–489.
4. Hodges Wilfrid. Model Theory (Draft 20 Jul 2000) // 2000. [Электронный ресурс] URL: http://wilfridhodges.co.uk/history07.pdf (дата обращения 25 декабря 2020 г.).
5. 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.
6. Boole George. The mathematical analysis of logic. // Philosophical Library, 1847.
7. Frege Gottlob. Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen
8. Denkens. // Halle, 1879. Translated in van Heijenoort J. Begriffsschrift, a formula language,
9. modeled upon that of arithmetic, for pure thought. From Frege to G¨odel: A Source Book in Mathematical Logic. 1931. — Pp. 3–82.
10. 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:
11. U. of California Press, 1964.
12. Peirce 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.
13. Peirce Charles Sanders. On the algebra of logic: A contribution to the philosophy of notation.
14. // American journal of mathematics, 1885, 7.2. – Pp. 180–196.
15. L¨owenheim Leopold. ¨Uber m¨oglichkeiten im relativkalk¨ul. // Mathematische Annalen, 1915,
16. 4. – Pp. 447–470.
17. Skolem Thoralf. Logisch-kombinatorische Untersuchungen ¨uber die Erfullbarkeit oder Beweisbarkeit
18. mathematischer Sdtze nebst einem Theorem ¨uber dichte Mengen. // Videnskapsselskapets
19. skrifter, I. Matematisk-naturvidenskabelig klasse 4, 1920.
20. Schr¨oder Ernst. On Pasigraphy. Its Present State and the Pasigraphic Movement in Italy. //
21. The Monist, 1898, 9.1. – Pp. 44–62.
22. Schr¨oder E. Vorlesungen ¨uber die Algebra der Logik. Volumes 1 to 3. // Teubner, Leipzig.
23. Reprinted by Chelsea, New York, 1966.
24. International Congress of Philosophy. // Biblioth`eque du Congr`es International de Philosophie,
25. Four volumes. Paris: Librairie Armand Colin, 1900–1903.
26. Compte rendu du deuxi`eme сongr`es international des math´ematiciens tenu `a Paris du 6 au 12
27. aoˆut 1900: proc`es-verbaux et communications. // Publies par Ernest Duporcq. Gauthier-Villars, imprimeur-libraire, 1902. – 455 pp.
28. Hilbert David. Mathematische probleme. // Nachrichten von der Gesellschaft der Wissenschaften
29. zu G¨ottingen, Mathematisch-Physikalische Klasse, 1900. – Pp. 253–297.
30. Padoa Alessandro. Logical introduction to any deductive theory. // 1900. Опубл. в сб. From
31. Frege to G¨odel. A Source Book in Mathematical Logic, 1879–1931. Ed. by Jean van Heijenoort.
32. Cambridge, Mass., Harvard University Press, 1967. – Pp. 118—123.
33. Pieri Mario. La geometria elementare istituita sulle nozioni ‘punto’ ´e ‘sfera’. // Memorie di
34. matematica e di fisica della Societ`a italiana delle scienze, 1908, 15. – Pp. 345–450.
35. Lindenbaum A., Tarski A. ¨Uber die Beschr¨anktheit der Ausdrucksmittel deduktiver Theorien.
36. // Ergebnisse eines Mathematischen Kolloquiums, Heft 7, 1935. – Pp. 15–22. Пер. на англ.:
37. On the Limitations of the Means of Expression of Deductive Theories. // Alfred Tarski. Logic,
38. Semantics, Metamathematics. // J. Corcoran, ed., Hackett, Indianapolis, 1956. – Pp. 384–392.
39. Huntington Edward V. Inter-Relations Among the Four Principal Types of Order. //
40. Transactions of the American Mathematical Society, 1935, 38.1. – Pp. 1–9.
41. Tarski Alfred. The Concept of Truth in Formalized Languages. // Alfred Tarski: Logic,
42. Semantics, Metamathematics. Trans. J. H.Woodger, second edition ed. and introduced by John
43. Corcoran, Hackett, Indianapolis, 1983. – Pp. 152–278.
44. Langford Cooper Harold. Some theorems on deducibility. // Annals of Mathematics Second
45. Series, 1926–1927, vol. 28, No. 1/4. – Pp. 16–40.
46. Langford Cooper Harold. Theorems on Deducibility (Second paper). // Annals of Mathematics,
47. Second Series, 1926–1927,Vol. 28, No. 1/4. – Pp. 459–471.
48. Presburger M. ¨Uber die vollst¨andigkeit eines gewissen systems der arithmetik ganzer zahlen,
49. in welchem die addition als einzige operation hervortritt. // Sprawozdanie z 1 Kongresu
50. Matematyk´ow Krajow Slowianskich, Ksiaznica Atlas, 1930. – Pp. 92–10. Пер. на англ.: On
51. the completeness of a certain system of arithmetic of whole numbers in which addition occurs
52. as the only operation. // History and Philosophy of Logic, 12(2), 1991. – Pp. 225–233.
53. Skolem Torlaf. ¨Uber gewisse Satzfunktionen in der Arithmetik. // Skrifter utgit av Videnskapsselskapet
54. i Kristiania, I. klasse 7, 1930.
55. Mostowski Andrzej. On direct products of theories. // Journal of Symbolic Logic, 1952, vol. 17. –
56. Pp. 1—31.
57. Tarski Alfred. A decision method for elementary algebra and geometry. // Prepared for
58. publication with the assistance of J. C. C. McKinsey. Second edition, revised. Lithoprinted.
59. University of California Press, Berkeley and Los Angeles, 1951. – 63 pp.
60. Семенов А. Л. Условия конечности для алгебр отношений. // Труды математического ин-
61. ститута им. В. А. Стеклова, 2003, т. 242. — С. 103–107.
62. Семенов А. Л., Сопрунов С. Ф. Конечные кванторные иерархии в алгебрах отношений. //
63. Труды Математического института им. В. А. Стеклова, 2011, т. 274. – C. 291–296.
64. Семенов А. Л. О некоторых расширениях арифметики сложения натуральных чисел //
65. Известия Академии наук СССР. Серия математическая. 1979. Т. 43, № 5. – С. 1175–1195.
66. Rabin Michael O. Decidability of second-order theories and automata on infinite trees. //
67. Transactions of the American Mathematical Society, 1969, 141. – pp. 1–35.
68. Muchnik An. A. Games on infinite trees and automata with dead-ends. A new proof for the
69. decidability of the monadic second order theory of two successors. // Bull. EATCS, 1992, 48. –
70. Pp. 220–267.
71. Elgot Calvin C., Rabin Michael O. Decidability and Undecidability of Extensions of Second
72. (First) Order Theory of (Generalized) Successor. // J. Symb. Log., 1966, vol. 31, No. 2. –
73. Pp. 169–181.
74. Сопрунов С. Ф. Разрешимые обогащения структур. // Вопросы кибернетики, 1988, т. 134. –
75. С. 175–179.
76. B`es Alexis, C´egielski Patrick. Weakly maximal decidable structures. // RAIRO – Theoretical
77. Informatics and Applications, 2008, 42.01. – Pp. 137–145.
78. B`es Alexis, C´egielski Patrick. Nonmaximal decidable structures. // Journal of Mathematical
79. Sciences, 2009, 158.5. – Pp. 615–622.
80. Tarski Alfred. Der Wahrheitsbegriff in den formalisierten Sprachen. // Studia Philosophica,
81. , vol. 1. – Pp. 261–405.
82. Tarski Alfred. Einige methodologifche Unterfuchungen ¨uber die Definierbarkeit der Begriffe. //
83. Erkenntnis, 1935, 5.1. – Pp. 80–100.
84. Beth Evert W. On Padoa’s method in the theory of definition. // Indag. Math, 1953, 15. –
85. Pp. 330–339.
86. Svenonius Lars. A theorem on permutations in models. // Theoria, 1959, 25.3. – Pp. 173–178.
87. Klein Felix. Vergleichende betrachtungen ¨uber neuere geometrische forsuchungen. //
88. A. Deichert, 1872.
89. Huntington Edward V. The fundamental laws of addition and multiplication in elementary
90. algebra. // The Annals of Mathematics, 1906, 8.1. – Pp. 1–44.
91. Semenov A. L., Soprunov S. F. A combinatorial version of the Svenonius theorem on definability,
92. Logic Journal of IGPL. – 23.6 (2015): 966–975.
93. Macpherson D. A survey of homogeneous structures. // Discrete Mathematics, 2011, vol. 311,
94. No. 15. – Pp. 1599–1634.
95. Hodges Wilfrid. Model theory. // Encyclopedia of Mathematics and its Applications, 1993,
96. vol. 42, Cambridge University Press, Cambridge.
97. Korec Ivan. A list of arithmetical structures complete with respect to the first-order definability.
98. // Theoretical computer science, 2001, 257.1. – Pp. 115–151.
99. Семенов А. Л. Пресбургеровость предикатов, регулярных в двух системах счисления. //
100. Сибирский математический журнал, 1977, т. 18, № 2. — С. 403–418.
101. Frasnay Claude. Quelques probl`emes combinatoires concernant les ordres totaux et les relations
102. monomorphes. // Annales de l’ institut Fourier, 1965, vol. 15, No. 2. – Pp. 415–524.
103. Huntington Edward V. The continuum as a type of order: an exposition of the model theory.
104. // Ann. Math., 1904, 6. – Pp. 178–179.
105. Cameron Peter J. Transitivity of permutation groups on unordered sets. // Mathematische
106. Zeitschrift, 1976, 148.2, Pp. 127–139.
107. Winkler Peter. Random structures and zero-one laws. Finite and infinite combinatorics in sets
108. and logic, Springer Netherlands, 1993. – Pp. 399–420.
109. Rado Richard. Universal graphs and universal functions. // Acta Arithmetica, 1964, 9.4. –
110. Pp. 331–340.
111. Thomas Simon. Reducts of random hypergraphs. // Annals of Pure and Applied Logic, 1996,
112. 2. – Pp. 165–193.
113. Thomas Simon. Reducts of the random graph. // Journal of Symbolic Logic, 1991, 56(1). –
114. Pp. 176–181.
115. Bodirsky Manuel, Pinsker Michael, Pongr´acz Andr´as. The 42 reducts of the random ordered
116. graph. // 2013, arXiv:1309.2165.
117. Junker Markus, Ziegler Martin. The 116 reducts of (Q, <, 𝑎). // Journal of Symbolic Logic,
118. , vol. 73, issue 3. – Pp. 861–884. DOI: https://doi.org/10.2178/jsl/1230396752.
119. Ahlbrandt Gisela, Ziegler Martin. Invariant subgroups of 𝑉 𝑉 . // J. Algebra, 1992, 151, no. 1. –
120. Pp. 26–38.
121. Bodirsky M., Macpherson D. Reducts of structures and maximal-closed permutation groups.
122. // 2013, arXiv:1310.6393.
123. Kaplan I., Simon P. The affine and projective groups are maximal. // 2013, arXiv:1310.8157.
124. Marker D., Peterzil Y. A., Pillay A. Additive reducts of real closed fields. // The Journal of
125. symbolic logic, 1992, vol. 57, issue 1. – Pp. 109–117. DOI: https://doi.org/10.2307/2275179.
126. Peterzil Ya’acov. Reducts of some structures over the reals. // Journal of Symbolic Logic, 1993,
127. 3. – Pp. 955–966. DOI: https://doi.org/10.2307/2275107.
128. Marker D., Pillay A. Reducts of (C,+, ·) which contain +. // Journal of Symbolic Logic, 1990,
129. vol. 55, issue 3. – Pp. 1243–1251.
130. Semenov A. L., Soprunov S. F. Lattice of relational algebras definable in integers with successor.
131. // 2012, arXiv:1201.4439
132. Bodirsky Manuel, Pinsker Michael, Tsankov Todor. Decidability of definability. // IEEE 26th
133. Annual Symposium on Logic in Computer Science, 2011. – Pp. 321–328.
134. Muchnik An. A. The definable criterion for definability in Presburger arithmetic and its
135. applications. // Theoretical Computer Science, 2003, 290.3. – Pp. 1433–1444.
136. Addison Jr. J. W. The undefinability of the definable. // Notices Amer. Math. Soc., 1965, 12. –
137. Pp. 347.
138. Tanaka Hisao. Some results in the effective descriptive set theory. // Publications of the
139. Research Institute for Mathematical Sciences, 1967, 3.1. – Pp. 11–52.
Рецензия
Для цитирования:
Семенов А.Л., Сопрунов С.Ф. Решетка определимости. Источники и направления исследований. Чебышевский сборник. 2021;22(1):304-327. https://doi.org/10.22405/2226-8383-2021-22-1-304-327
For citation:
Semenov A.L., Soprunov S.F. The lattice of definability. Origins and Directions of Research. Chebyshevskii Sbornik. 2021;22(1):304-327. (In Russ.) https://doi.org/10.22405/2226-8383-2021-22-1-304-327
Просмотров:
336
Послать статью по эл. почте 