The lattice of definability. Origins and directions of research

A. L. Semenov ; S. F. Soprunov

Čebyševskij sbornik, Tome 22 (2021) no. 1, pp. 304-327.

Résumé

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.

Détail

Keywords: definability, definability space, reducts, Svenonius theorem, quantifier elimination, decidability, automorphisms.

Bibliographie

[1] Tarski A., What are logical notions?, History and philosophy of logic, 7:2 (1986), 143–154 | DOI | MR | Zbl

[2] Buchi J. Richard, Danhof Kenneth J., “Definibility in normal theories”, Israel Journal of Mathematics, 14:3 (1973), 248–256 | DOI | MR | Zbl

[3] Smith James T., “Definitions and nondefinability in geometry”, The American Mathematical Monthly, 117:6 (2010), 475–489 | DOI | MR | Zbl

[4] Hodges Wilfrid, Model Theory, Draft 20 Jul 2000, , 2000 (data obrascheniya 25 dekabrya 2020 g.) http://wilfridhodges.co.uk/history07.pdf

[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, 185–352

[6] Boole George, The mathematical analysis of logic, Philosophical Library, 1847 | MR

[7] van Heijenoort J., “Begriffsschrift, a formula language, modeled upon that of arithmetic, for pure thought”, From Frege to Gödel: A Source Book in Mathematical Logic, 1931, 3–82 | MR

[8] M. Furth (transl.), The Basic Laws of Arithmetic, U. of California Press, Berkeley, 1964 | MR | MR

[9] 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, 9:2 (1873), 317–378 | DOI

[10] Peirce Charles Sanders, “On the algebra of logic: A contribution to the philosophy of notation”, American journal of mathematics, 7:2 (1885), 180–196 | DOI | MR

[11] Löwenheim Leopold, “Über möglichkeiten im relativkalkül”, Mathematische Annalen, 76:4 (1915), 447–470 | DOI | MR

[12] Skolem Thoralf, Logisch-kombinatorische Untersuchungen über die Erfullbarkeit oder Beweisbarkeit mathematischer Sdtze nebst einem Theorem über dichte Mengen, Videnskapsselskapets skrifter, I. Matematisk-naturvidenskabelig klasse 4, 1920

[13] Schröder Ernst, “On Pasigraphy. Its Present State and the Pasigraphic Movement in Italy”, The Monist, 9:1 (1898), 44–62 | DOI

[14] Schröder E., Vorlesungen über die Algebra der Logik, v. 1–3, Teubner, Leipzig; Chelsea, New York, 1966

[15] International Congress of Philosophy, Bibliothèque du Congrès International de Philosophie, 4, Librairie Armand Colin, Paris, 1900–1903

[16] Compte rendu du deuxième songrès international des mathématiciens tenu à Paris du 6 au 12 août 1900 : procès-verbaux et communications, Publies par Ernest Duporcq. Gauthier-Villars, imprimeur-libraire, 1902, 455 pp. | MR

[17] Hilbert David, “Mathematische probleme”, Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen, Mathematisch-Physikalische Klasse, 1900, 253–297

[18] Padoa Alessandro, “Logical introduction to any deductive theory (1900)”, From Frege to Gödel. A Source Book in Mathematical Logic, 1879-1931, ed. Jean van Heijenoort, Harvard University Press, Cambridge, Mass., 1967, 118–123 | MR

[19] Pieri Mario, “La geometria elementare istituita sulle nozioni ‘punto’ é ‘sfera’”, Memorie di matematica e di fisica della Società italiana delle scienze, 15 (1908), 345–450

[20] Lindenbaum A., Tarski A., “Über die Beschränktheit der Ausdrucksmittel deduktiver Theorien”, Ergebnisse eines Mathematischen Kolloquiums, v. 7, 1935, 15–22; Alfred Tarski, “On the Limitations of the Means of Expression of Deductive Theories”, ed. J. Corcoran, Hackett, Indianapolis, 1956, 384–392

[21] Huntington Edward V., “Inter-Relations Among the Four Principal Types of Order”, Transactions of the American Mathematical Society, 38:1 (1935), 1–9 | DOI | MR | Zbl

[22] Tarski Alfred, “The Concept of Truth in Formalized Languages”, Logic, Semantics, Metamathematics, Trans. J. H. Woodger, second edition, Hackett, Indianapolis, 1983, 152–278 | MR

[23] Langford Cooper Harold, “Some theorems on deducibility”, Annals of Mathematics Second Series, 28:1/4 (1926–1927), 16–40 | DOI | MR

[24] Langford Cooper Harold, “Theorems on Deducibility (Second paper)”, Annals of Mathematics, Second Series, 28:1/4 (1926–1927), 459–471 | DOI | MR

[25] Presburger M., “Über die vollständigkeit eines gewissen systems der arithmetik ganzer zahlen, in welchem die addition als einzige operation hervortritt”, Sprawozdanie z 1 Kongresu Matematyków Krajow Slowianskich, Ksiaznica Atlas, 1930, 92–10; “On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation”, History and Philosophy of Logic, 12:2 (1991), 225–233 | DOI | MR | Zbl

[26] Skolem Torlaf, “Über gewisse Satzfunktionen in der Arithmetik”, Skrifter utgit av Videnskapsselskapet i Kristiania, I. klasse 7, 1930

[27] Mostowski Andrzej, “On direct products of theories”, Journal of Symbolic Logic, 17 (1952), 1–31 | DOI | MR | Zbl

[28] Tarski Alfred, A decision method for elementary algebra and geometry, Prepared for publication with the assistance of J. C. C. McKinsey. Second edition, revised. Lithoprinted, University of California Press, Berkeley–Los Angeles, 1951, 63 pp. | MR

[29] Semenov A. L., “Usloviya konechnosti dlya algebr otnoshenii”, Trudy matematicheskogo instituta im. V. A. Steklova, 242, 2003, 103–107 | Zbl

[30] Semenov A. L., Soprunov S. F., “Konechnye kvantornye ierarkhii v algebrakh otnoshenii”, Trudy Matematicheskogo instituta im. V. A. Steklova, 274, 2011, 291–296 | Zbl

[31] Semenov A. L., “O nekotorykh rasshireniyakh arifmetiki slozheniya naturalnykh chisel”, Izvestiya Akademii nauk SSSR. Seriya matematicheskaya, 43:5 (1979), 1175–1195 | MR | Zbl

[32] Rabin Michael O., “Decidability of second-order theories and automata on infinite trees”, Transactions of the American Mathematical Society, 141 (1969), 1–35 | MR | Zbl

[33] Muchnik An. A., “Games on infinite trees and automata with dead-ends. A new proof for the decidability of the monadic second order theory of two successors”, Bull. EATCS, 48 (1992), 220–267 | Zbl

[34] Elgot Calvin C., Rabin Michael O., “Decidability and Undecidability of Extensions of Second (First) Order Theory of (Generalized) Successor”, J. Symb. Log., 31:2 (1966), 169–181 | DOI | Zbl

[35] Soprunov S. F., “Razreshimye obogascheniya struktur”, Voprosy kibernetiki, 134 (1988), 175–179 | Zbl

[36] Bès Alexis, Cégielski Patrick, “Weakly maximal decidable structures”, RAIRO – Theoretical Informatics and Applications, 42:01 (2008), 137–145 | DOI | MR | Zbl

[37] Bès Alexis, Cégielski Patrick, “Nonmaximal decidable structures”, Journal of Mathematical Sciences, 158:5 (2009), 615–622 | DOI | MR | Zbl

[38] Tarski Alfred, “Der Wahrheitsbegriff in den formalisierten Sprachen”, Studia Philosophica, 1 (1935), 261–405 | Zbl

[39] Tarski Alfred, “Einige methodologifche Unterfuchungen über die Definierbarkeit der Begriffe”, Erkenntnis, 5:1 (1935), 80–100 | DOI | Zbl

[40] Beth Evert W., “On Padoa's method in the theory of definition”, Indag. Math., 15 (1953), 330–339 | DOI | MR

[41] Svenonius Lars, “A theorem on permutations in models”, Theoria, 25:3 (1959), 173–178 | DOI | MR

[42] Klein Felix, Vergleichende betrachtungen über neuere geometrische forsuchungen, A. Deichert, 1872

[43] Huntington Edward V., “The fundamental laws of addition and multiplication in elementary algebra”, The Annals of Mathematics, 8:1 (1906), 1–44 | DOI | MR

[44] Semenov A. L., Soprunov S. F., “A combinatorial version of the Svenonius theorem on definability”, Logic Journal of IGPL, 23:6 (2015), 966–975 | DOI | MR | Zbl

[45] Macpherson D., “A survey of homogeneous structures”, Discrete Mathematics, 311:15 (2011), 1599–1634 | DOI | MR | Zbl

[46] Hodges Wilfrid, “Model theory”, Encyclopedia of Mathematics and its Applications, 42, Cambridge University Press, Cambridge, 1993 | MR | Zbl

[47] Korec Ivan, “A list of arithmetical structures complete with respect to the first-order definability”, Theoretical computer science, 257:1 (2001), 115–151 | DOI | MR | Zbl

[48] Semenov A. L., “Presburgerovost predikatov, regulyarnykh v dvukh sistemakh schisleniya”, Sibirskii matematicheskii zhurnal, 18:2 (1977), 403–418 | MR | Zbl

[49] Frasnay Claude, “Quelques problèmes combinatoires concernant les ordres totaux et les relations monomorphes”, Annales de l' institut Fourier, 15:2 (1965), 415–524 | DOI | MR | Zbl

[50] Huntington Edward V., “The continuum as a type of order: an exposition of the model theory”, Ann. Math., 6 (1904), 178–179 | MR

[51] Cameron Peter J., “Transitivity of permutation groups on unordered sets”, Mathematische Zeitschrift, 148:2 (1976), 127–139 | DOI | MR | Zbl

[52] Winkler Peter, “Random structures and zero-one laws”, Finite and infinite combinatorics in sets and logic, Springer Netherlands, 1993, 399–420 | DOI | MR

[53] Rado Richard, “Universal graphs and universal functions”, Acta Arithmetica, 9:4 (1964), 331–340 | DOI | MR | Zbl

[54] Thomas Simon, “Reducts of random hypergraphs”, Annals of Pure and Applied Logic, 80:2 (1996), 165–193 | DOI | MR | Zbl

[55] Thomas Simon, “Reducts of the random graph”, Journal of Symbolic Logic, 56:1 (1991), 176–181 | DOI | MR | Zbl

[56] Bodirsky Manuel, Pinsker Michael, Pongrácz András, The 42 reducts of the random ordered graph, 2013, arXiv: 1309.2165 | MR

[57] Junker Markus, Ziegler Martin, “The 116 reducts of $({\mathbb Q},,a)$”, Journal of Symbolic Logic, 73:3 (2008), 861–884 | DOI | MR | Zbl

[58] Ahlbrandt Gisela, Ziegler Martin, “Invariant subgroups of $^VV$”, J. Algebra, 151:1 (1992), 26–38 | DOI | MR | Zbl

[59] Bodirsky M., Macpherson D., Reducts of structures and maximal-closed permutation groups, 2013, arXiv: 1310.6393

[60] Kaplan I., Simon P., The affine and projective groups are maximal, 2013, arXiv: 1310.8157

[61] Marker D., Peterzil Y. A., Pillay A., “Additive reducts of real closed fields”, The Journal of symbolic logic, 57:1 (1992), 109–117 | DOI | MR | Zbl

[62] Peterzil Ya'acov, “Reducts of some structures over the reals”, Journal of Symbolic Logic, 58:3 (1993), 955–966 | DOI | MR | Zbl

[63] Marker D., Pillay A., “Reducts of $(C,+,\cdot)$ which contain $+$”, Journal of Symbolic Logic, 55:3 (1990), 1243–1251 | DOI | MR | Zbl

[64] Semenov A. L., Soprunov S. F., Lattice of relational algebras definable in integers with successor, 2012, arXiv: 1201.4439

[65] Bodirsky Manuel, Pinsker Michael, Tsankov Todor, “Decidability of definability”, IEEE 26th Annual Symposium on Logic in Computer Science, 2011, 321–328 | MR

[66] Muchnik An. A., “The definable criterion for definability in Presburger arithmetic and its applications”, Theoretical Computer Science, 290:3 (2003), 1433–1444 | DOI | MR | Zbl

[67] Addison Jr. J. W., “The undefinability of the definable”, Notices Amer. Math. Soc., 12 (1965), 347

[68] Tanaka Hisao, “Some results in the effective descriptive set theory”, Publications of the Research Institute for Mathematical Sciences, 3:1 (1967), 11–52 | DOI | MR | Zbl