The lattice of definability. Origins and Directions of Research
https://doi.org/10.22405/2226-8383-2021-22-1-304-327
Abstract
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 structures
are described. Research methods include the study of automorphism groups of elementary extensions of the structures under consideration, application of the Svenonius theorem.
About the Authors
Alexey Lvovich Semenov
Lomonosov Moscow State University, Axel Berg Institute of
Cybernetics and Educational Computing FRC SCS of the Russian Academy of Sciences
Russian Federation
Russian Federation
Sergey Fedorovich Soprunov
Center for pedagogical excellence, Axel Berg Institute of
Cybernetics and Educational Computing FRC SCS of the Russian Academy of Sciences
Russian Federation
Russian Federation
References
1. Addison, Jr. J. W. 1965, “The undefinability of the definable“, Notices Amer. Math. Soc., 12,
2. pp. 347.
3. Ahlbrandt, Gisela & Ziegler, Martin. 1992, “Invariant subgroups of 𝑉 𝑉 “, J. Algebra, 151, no. 1,
4. pp. 26–38.
5. B`es, Alexis & C´egielski, Patrick. 2008, “Weakly maximal decidable structures“, RAIRO –
6. Theoretical Informatics and Applications, 42.01, pp. 137–145.
7. B`es, Alexis & C´egielski, Patrick. 2009, “Nonmaximal decidable structures“, Journal of Mathematical
8. Sciences, 158.5, pp. 615–622.
9. Beth, Evert W. 1953, “On Padoa’s method in the theory of definition“, Indag. Math, 15, pp. 330–
10.
11. Bodirsky, M. & Macpherson, D. 2013, “Reducts of structures and maximal-closed permutation
12. groups“, arXiv:1310.6393.
13. Bodirsky, Manuel, Pinsker, Michael & Pongr´acz, Andr´as. 2013, “The 42 reducts of the random
14. ordered graph“, arXiv:1309.2165.
15. Bodirsky, Manuel, Pinsker, Michael & Tsankov, Todor. 2011, “Decidability of definability.“ IEEE
16. th Annual Symposium on Logic in Computer Science, pp. 321–328.
17. Boole, George. 1847, The mathematical analysis of logic, Philosophical Library.
18. Buchi, J. Richard & Danhof, Kenneth J. 1973, “Definibility in normal theories“, Israel Journal
19. of Mathematics, 14.3, pp. 248–256.
20. Cameron, Peter J. 1976, “Transitivity of permutation groups on unordered sets“. Mathematische
21. Zeitschrift, 148.2. – Pp. 127–139.
22. Duporcq, Ernest, ed. 1902, Compte rendu du deuxi`eme congr`es international des math´ematiciens
23. tenu `a Paris du 6 au 12 aoˆut 1900: proc`es-verbaux et communications, Gauthier-Villars,
24. imprimeur-library, 455 pp.
25. Elgot, Calvin C. & Rabin, Michael O. 1966, “Decidability and Undecidability of Extensions
26. of Second (First) Order Theory of (Generalized) Successor“, J. Symb. Log., Vol. 31, No. 2,
27. pp. 169–181.
28. Frasnay, Claude. 1965, “Quelques probl`emes combinatoires concernant les ordres totaux et les
29. relations monomorphes“, Annales de l’ institut Fourier, vol. 15, No. 2, pp. 415–524.
30. Frege, G. 1879, Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen
31. Denkens, Halle. Translated in van Heijenoort J. 1931, Begriffsschrift, a formula language,
32. modeled upon that of arithmetic, for pure thought. From Frege to G¨odel: A Source Book in
33. Mathematical Logic, pp. 3–82.
34. Frege, G. 1893, Grundgesetze der arithmetik, Publ. in 1964 by Jena: Verlag Hermann Pohle,
35. Band I/II. Partial translation of Band I, The Basic Laws of Arithmetic, by M. Furth, Berkeley:
36. U. of California Press.
37. Hilbert, David. 1900, “Mathematische probleme“, Nachrichten von der Gesellschaft der Wissenschaften
38. zu G¨ottingen, Mathematisch-Physikalische Klasse, pp. 253–297.
39. Hodges, Wilfrid. 1993, “Model theory“, Encyclopedia of Mathematics and its Applications,
40. vol. 42, Cambridge University Press, Cambridge.
41. Hodges, Wilfrid. 2000, Model Theory (Draft 20 Jul 2000). Available at: http://wilfridhodges.
42. co.uk/history07.pdf (accessed 25 December 2020).
43. Huntington, Edward V. 1904, “The continuum as a type of order: an exposition of the model
44. theory“, Ann. Math., 6, pp. 178–179.
45. Huntington, Edward V. 1906, “The Fundamental Laws of Addition and Multiplication in
46. Elementary Algebra“, The Annals of Mathematics, 8.1, pp. 1–44.
47. Huntington, Edward V. 1935, “Inter-Relations Among the Four Principal Types of Order“,
48. Transactions of the American Mathematical Society, 38.1, pp. 1–9.
49. International Congress of Philosophy. 1900–1903, Biblioth`eque du Congr`es International de
50. Philosophie, Four volumes. Paris: Librairie Armand Colin.
51. Junker, Markus & Ziegler, Martin. 2008, “The 116 reducts of (Q, <, 𝑎)“, Journal of Symbolic
52. Logic, vol. 73, issue 3, pp. 861–884. DOI: https://doi.org/10.2178/jsl/1230396752
53. Kaplan, I. & Simon, P. 2013, “The affine and projective groups are maximal“, arXiv:1310.8157.
54. Klein, Felix. 1872, Vergleichende betrachtungen ¨uber neuere geometrische forsuchungen,
55. A. Deichert.
56. Korec, Ivan. 2001, “A list of arithmetical structures complete with respect to the first-order
57. definability“, Theoretical computer science, 257.1, pp. 115–151.
58. Langford, Cooper Harold. 1926–1927, “Some theorems on deducibility“, Annals of Mathematics
59. Second Series, Vol. 28, No. 1/4, pp. 16–40.
60. Langford, Cooper Harold. 1926–1927, “Theorems on Deducibility (Second paper)“, Annals of
61. Mathematics, Second Series, Vol. 28, No. 1/4, pp. 459–471.
62. Lindenbaum, A. & Tarski, A. 1935, “ ¨Uber die Beschr¨anktheit der Ausdrucksmittel deduktiver
63. Theorien“, Ergebnisse eines Mathematischen Kolloquiums, Heft 7, pp. 15–22. (Engl. trans.: “On
64. the Limitations of the Means of Expression of Deductive Theories“, In Alfred Tarski: Logic,
65. Semantics, Metamathematics, J. Corcoran, ed., Hackett, Indianapolis, 1956, pp. 384–392.
66. L¨owenheim, Leopold. 1915, “ ¨Uber m¨oglichkeiten im relativkalk¨ul“, Mathematische Annalen,
67. 4, pp. 447–470.
68. Macpherson, D. 2011, “A survey of homogeneous structures“, Discrete Mathematics, vol. 311,
69. No 15, pp. 1599–1634.
70. Marker, D.& Pillay, A. 1990, “Reducts of (𝐶,+, ·) which contain +“, Journal of Symbolic Logic,
71. vol. 55, issue 3, pp. 1243–1251.
72. Marker, D., Peterzil, Y. A.& Pillay, A. 1992, “Additive reducts of real closed fields“, The Journal
73. of symbolic logic, vol. 57, issue 1, pp. 109–117. DOI: https://doi.org/10.2307/2275179.
74. Mostowski, Andrzej. 1952, “On direct products of theories“, Journal of Symbolic Logic, vol. 17,
75. pp. 1–31.
76. Muchnik, An. A. 1992, “Games on infinite trees and automata with dead-ends. A new proof
77. for the decidability of the monadic second order theory of two successors“, Bull. EATCS, 48,
78. pp. 220–267.
79. Muchnik, An. A. 2003, “The definable criterion for definability in Presburger arithmetic and its
80. applications“, Theoretical Computer Science, 290.3, pp. 1433–1444.
81. Padoa Alessandro. 1900, “Logical introduction to any deductive theory“, In From Frege to G¨odel.
82. A Source Book in Mathematical Logic, 1879–1931. Ed. by Jean van Heijenoort. Cambridge,
83. Mass., Harvard University Press, pp. 118—123.
84. Peacock, George. 1834, “Report on the recent progress and present state of certain branches of
85. analysis“, Report of the third meeting of the British Association for the Advancement of Science
86. held at Cambridge in 1833, John Murrary, London, pp. 185–352.
87. Peirce, Charles Sanders. 1873, “Description of a notation for the logic of relatives, resulting
88. from an amplification of the conceptions of Boole’s calculus of logic“, Memoirs of the American
89. academy of arts and sciences, vol. 9, part 2, pp. 317–378.
90. Peirce, Charles Sanders. 1885, “On the algebra of logic: A contribution to the philosophy of
91. notation“, American journal of mathematics, 7.2, pp. 180–196.
92. Peterzil, Ya’acov. 1993, “Reducts of some structures over the reals“, Journal of Symbolic Logic,
93. 3, pp. 955–966. DOI: https://doi.org/10.2307/2275107.
94. Pieri, Mario. 1908, “La geometria elementare istituita sulle nozioni ‘punto’ ´e ‘sfera’“, Memorie
95. di matematica e di fisica della Societ`a italiana delle scienze, 15, pp. 345–450.
96. Presburger, M. 1930, “ ¨Uber die Vollst¨andigkeit eines gewissen Systems der Arithmetik
97. ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt“, Sprawozdanie z
98. Kongresu Matematyk´ow Krajow Slowianskich, Ksiaznica Atlas. pp. 92–10. (Translated: “On
99. the completeness of a certain system of arithmetic of whole numbers in which addition occurs
100. as the only operation“, History and Philosophy of Logic, 12(2), 1991, pp. 225–233.)
101. Rabin, Michael O. 1969, “Decidability of second-order theories and automata on infinite trees“,
102. Transactions of the American Mathematical Society, 141, pp. 1–35.
103. Rado, Richard. 1964, “Universal graphs and universal functions“, Acta Arithmetica, 9.4, pp. 331–
104.
105. Schr¨oder, Ernst. 1898, “On Pasigraphy. Its Present State and the Pasigraphic Movement in
106. Italy“, The Monist, 9.1, pp. 44–62.
107. Schr¨oder, Ernst. 1966, Vorlesungen ¨uber die Algebra der Logik, Volumes 1 to 3. Teubner, Leipzig.
108. Reprinted by Chelsea, New York.
109. Semenov, A. L. 1977, “Presburgerness of Predicates Regular in Two Number Systems“, Siberian
110. Math. J., 18.2, pp. 289–300.
111. Semenov, A. L. 1980, “On certain extensions of the arithmetic of addition of natural numbers”,
112. Izvestiya: Mathematics, 15.2, pp. 401–418.
113. Semenov, A. L. 2003, “Finiteness Conditions for Algebras of Relations“, Proceedings of the
114. Steklov Institute of Mathematics, 242, pp. 92–96.)
115. Semenov, A. & Soprunov, S. 2011, “Finite quantifier hierarchies in relational algebras“,
116. Proceedings of the Steklov I Institute of Mathematics, 274.1, pp. 267–272.
117. Semenov, A. L. & Soprunov, S. F. 2012, “Lattice of relational algebras definable in integers with
118. successor“, arXiv:1201.4439.
119. Semenov, A. L. & Soprunov, S. F. 2013, A combinatorial version of the Svenonius theorem on
120. definability, Logic Journal of IGPL. – 23.6 (2015): 966–975.
121. Skolem, Thoralf. 1920, “Logisch-kombinatorische Untersuchungen ¨uber die Erfullbarkeit oder
122. Beweisbarkeit mathematischer Sdtze nebst einem Theorem ¨uber dichte Mengen“, Videnskapsselskapets
123. skrifter, I. Matematisk-naturvidenskabelig klasse 4.
124. Skolem, Torlaf. 1930, “ ¨Uber gewisse Satzfunktionen in der Arithmetik“, Skrifter utgit av
125. Videnskapsselskapet i Kristiania, I. klasse 7.
126. Smith, James T. 2010, “Definitions and Nondefinability in Geometry“, The American Mathematical
127. Monthly, 117.6, pp. 475–489.
128. Soprunov, S. 1988, “Razreshimye obogashchenia struktur – Decidable expansions of structures“,
129. Vopr. Kibern., 134, pp. 175–179 (in Russian).
130. Svenonius, Lars. 1959, “A theorem on permutations in models“, Theoria, 25.3, pp. 173–178.
131. Tanaka, Hisao. 1967, “Some results in the effective descriptive set theory“, Publications of the
132. Research Institute for Mathematical Sciences, 3.1, pp. 11–52.
133. Tarski, Alfred. 1935, “DerWahrheitsbegriff in den formalisierten Sprachen“, Studia Philosophica,
134. vol. 1, pp. 261–405.
135. Tarski, Alfred. 1935, “Einige methodologifche Unterfuchungen ¨uber die Definierbarkeit der
136. Begriffe“, Erkenntnis, 5.1, pp. 80–100.
137. Tarski, Alfred. 1951, A decision method for elementary algebra and geometry. Prepared for
138. publication with the assistance of J. C. C. McKinsey. Second edition, revised. Lithoprinted.
139. University of California Press, Berkeley and Los Angeles, iii + 63 pp.
140. Tarski, Alfred. 1983, “The Concept of Truth in Formalized Languages“, Alfred Tarski: Logic,
141. Semantics, Metamathematics. Trans. J. H. Woodger, second edition ed. and introduced by John
142. Corcoran, Hackett, Indianapolis, pp. 152–278.
143. Tarski, Alfred. 1986, “What are logical notions?“ History and philosophy of logic, 7.2, pp. 143–
144.
145. Thomas, Simon. 1991, “Reducts of the random graph“, Journal of Symbolic Logic, 56(1), pp. 176–
146.
147. Thomas, Simon. 1996, “Reducts of random hypergraphs“, Annals of Pure and Applied Logic,
148. 2, pp. 165–193.
149. Winkler, Peter. 1993, Random structures and zero-one laws. Finite and infinite combinatorics
150. in sets and logic, Springer Netherlands, pp. 399–420.
Review
For citations:
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
Views:
340
Email this article 