Abstract
The paper presents recent results and open problems on classes of definable relations (definability spaces, reducts, relational algebras) as well as sources for the research starting from the XIX century. Finiteness conditions are investigated, including quantifier alternation depth and number of arguments width. The infinite lattice of definability for integers with a successor function (a non ω-categorical structure) is described. Methods of investigation include study of automorphism groups of elementary extensions of structures under consideration, using Svenonius theorem and a generalization of it.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Addison Jr., J.W.: The undefinability of the definable. Notices Amer. Math. Soc. 12, 347 (1965)
Ahlbrandt, G., Ziegler, M.: Invariant subgroups of V V. J. Algebra 151(1), 26–38 (1992)
Bès, A., Cégielski, P.: Weakly maximal decidable structures. RAIRO - Theoretical Informatics and Applications 42(1), 137–145 (2008)
Bès, A., Cégielski, P.: Nonmaximal decidable structures. Journal of Mathematical Sciences 158(5), 615–622 (2009)
Beth, E.W.: On Padoa’s method in the theory of definition. Indag. Math. 15, 330–339 (1953)
Bodirsky, M., Macpherson, D.: Reducts of structures and maximal-closed permutation groups. arXiv:1310.6393. (2013)
Boole, G.: The mathematical analysis of logic. Philosophical Library (1847)
Bodirsky, M., Pinsker, M., Pongrácz, A.: The 42 reducts of the random ordered graph. arXiv:1309.2165 (2013)
Bodirsky, M., Pinsker, M., Tsankov, T.: Decidability of definability. In: 26th Annual IEEE Symposium on Logic in Computer Science (LICS). IEEE (2011)
Buchi, J.R., Danhof, K.J.: Definibility in normal theories. Israel Journal of Mathematics 14(3), 248–256 (1973)
Cameron, P.J.: Aspects of infinite permutation groups. London Mathematical Society Lecture Note Series 339, 1 (2007)
Cameron, P.J.: Transitivity of permutation groups on unordered sets. Mathematische Zeitschrift 148(2), 127–139 (1976)
Elgot, C.C., Rabin, M.O.: Decidability and Undecidability of Extensions of Second (First) Order Theory of (Generalized) Successor. J. Symb. Log. 31(2), 169–181 (1966)
Frasnay, C.: Quelques problèmes combinatoires concernant les ordres totaux et les relations monomorphes. Annales de l’ institut Fourier 15(2). Institut Fourier (1965)
Frege, G.: Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. Halle. (1879); van Heijenoort J. (trans.) Begriffsschrift, a formula language, modeled upon that of arithmetic, for pure thought. From Frege to Gödel: A Source Book in Mathematical Logic, 3–82 (1879-1931)
Frege, G.: Grundgesetze der Arithmetik, Jena: Verlag Hermann Pohle, Band I/II. The Basic Laws of Arithmetic, by M. Furth. U. of California Press, Berkeley (1964)
Hilbert, D.: Mathematische probleme. Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen, Mathematisch-Physikalische Klasse 1900, 253–297 (1900)
Hodges, W.: Model Theory (Draft July 20, 2000), http://wilfridhodges.co.uk/history07.pdf
Hodges, W.: Tarski on Padoa’s method (2007), http://wilfridhodges.co.uk/history06.pdf
Hodges, W.: Model theory, Encyclopedia of Mathematics and its Applications, vol. 42. Cambridge University Press, Cambridge (1993)
Huntington, E.V.: The Fundamental Laws of Addition and Multiplication in Elementary Algebra. The Annals of Mathematics 8(1), 1–44 (1906)
Huntington, E.V.: Inter-Relations Among the Four Principal Types of Order. Transactions of the American Mathematical Society 38(1), 1–9 (1935)
Huntington, E.V.: A complete set of postulates for the theory of absolute continuous magnitude. Transactions of the American Mathematical Society 3(2), 264–279 (1902)
Huntington, E.V.: The continuum as a type of order: an exposition of the model theory. Ann. Math. 6, 178–179 (1904)
Duporcq, E. (ed.): Compte rendu du deuxième Congrès international des mathématiciens: tenu à Paris du 6 au 12 août 1900: procès-verbaux et communications. Gauthier-Villars (1902)
International Congress of Philosophy. 1900–1903. Bibliothèque du Congrès International de Philosophie. Four volumes. Paris: Librairie Armand Colin
Junker, M., Ziegler, M.: The 116 reducts of (ℚ, < ,a). Journal of Symbolic Logic, 861–884 (2008)
Kaplan, I., Simon, P.: The affine and projective groups are maximal. arXiv:1310.8157 (2013)
Klein, F.: Vergleichende betrachtungen über neuere geometrische forsuchungen. A. Deichert (1872)
Korec, I.: A list of arithmetical structures complete with respect to the first-order definability. Theoretical Computer Science 257(1), 115–151 (2001)
Langford, C.H.: Some theorems on deducibility. Annals of Mathematics Second Series 28(1/4), 16–40 (1926–1927)
Langford, C.H.: Theorems on Deducibility (Second paper). Annals of Mathematics, Second Series 28(1/4), 459–471 (1926–1927)
Lindenbaum, A., Tarski, A.: Über die Beschränktheit der Ausdrucksmittel deduktiver Theorien. Ergebnisse eines Mathematischen Kolloquiums, fascicule 7 (1934–1935) (Engl. trans.: On the Limitations of the Means of Expression of Deductive Theories. In: Corcoran, J. (ed.) Alfred Tarski: Logic, Semantics, Metamathematics, Hackett, Indianapolis, 384–392 (1935))
Löwenheim, L.: Über möglichkeiten im relativkalkül. Mathematische Annalen 76(4), 447–470 (1915)
Macpherson, D.: A survey of homogeneous structures. Discrete Mathematics 311(15), 1599–1634 (2011)
Marker, D., Peterzil, Y.A., Pillay, A.: Additive reducts of real closed fields. The Journal of Symbolic Logic, 109–117 (1992)
Marker, D., Pillay, A.: Reducts of (C, + ,·) which contain +. Journal of Symbolic Logic, 1243–1251 (1990)
Mostowski, A.: On direct products of theories. Journal of Symbolic Logic, 1–31 (1952)
Muchnik, A.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, 220–267 (1992)
Muchnik, A.A.: The definable criterion for definability in Presburger arithmetic and its applications. Theoretical Computer Science 290(3), 1433–1444 (2003)
Peacock, G.: Report on the recent progress and present state of certain branches of analysis. British Association for the Advancement of Science (1833)
Peirce, C.S.: 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, 317–378 (1873)
Peirce, C.S.: On the algebra of logic: A contribution to the philosophy of notation. American Journal of Mathematics 7(2), 180–196 (1885)
Peterzil, Y.: Reducts of some structures over the reals. Journal of Symbolic Logic 58(3), 955–966 (1993)
Pieri, M.: La geometria elementare istituita sulle nozioni ‘punto’ é ‘sfera’. Memorie di Matematica e di Fisica della Società Italiana delle Scienze 15, 345–450 (1908)
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. pp. 92-10 (Translated: 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, 225–233 (1930))
Rabin, M.O.: Decidability of second-order theories and automata on infinite trees. Transactions of the American Mathematical Society 141, 1–35 (1969)
Rado, R.: Universal graphs and universal functions. Acta Arithmetica 9(4), 331–340 (1964)
Schröder, E.: On Pasigraphy. Its Present State and the Pasigraphic Movement in Italy. The Monist 9(1), 44–62 (1898)
Schröder, E.: Vorlesungen über die Algebra der Logik, Volumes 1 to 3. Teubner, Leipzig. Reprinted by Chelsea, New York (1966)
Semenov, A.L.: Finiteness Conditions for Algebras of Relations. Trudy Matematicheskogo Instituta im. V.A. Steklova 242, 103–107 (2003); English version: Proceedings of the Steklov Institute of Mathematics 242, 92–96 (2003)
Semenov, A.L.: On certain extensions of the arithmetic of addition of natural numbers. Izvestiya: Mathematics 15(2), 401–418 (1980)
Semenov, A.L.: Predicates that are regular in two positional systems are definable in Presburger arithmetic. Siberian Math. J. 18(2), 403–418 (1977)
Semenov, A., Soprunov, S.: Finite quantifier hierarchies in relational algebras. Proceedings of the Steklov Institute of Mathematics 274(1), 267–272 (2011)
Semenov, A.L., Soprunov, S.F.: Remark on Svenonius theorem. arXiv:1301.2412 (2013)
Semenov, A.L., Soprunov, S.F.: Lattice of relational algebras definable in integers with successor. arXiv:1201.4439 (2012)
Skolem, T.: Logisch-kombinatorische Untersuchungen über die Erfullbarkeit oder Beweisbarkeit mathematischer Sdtze nebst einem Theorem über dichte Mengen. Videnskapsselskapets skrifter. I. Matematisk-naturvidenskabelig klasse 4 (1920)
Skolem, T.: Über gewisse Satzfunktionen in der Arithmetik. Skrifter utgit av Videnskapsselskapet i Kristiania, I. klasse 7 (1930)
Smith, J.T.: Definitions and Nondefinability in Geometry. The American Mathematical Monthly 117(6), 475–489 (2010)
Soprunov, S.: Decidable expansions of structures. Vopr. Kibern. 134, 175–179 (1988) (in Russian)
Svenonius, L.: A theorem on permutations in models. Theoria 25(3), 173–178 (1959)
Tanaka, H.: Some results in the effective descriptive set theory. Publications of the Research Institute for Mathematical Sciences 3(1), 11–52 (1967)
Tarski, A.: The Concept of Truth in Formalized Languages. In: Alfred Tarski: Logic, Semantics, Metamathematics. Trans. J. H. Woodger, second edition ed. and introduced by John Corcoran, Hackett, Indianapolis, 152–278 (1983)
Tarski, A.: A Decision Method for Elementary Algebra and Geometry Report R-109 (second revised edn.). The Rand Corporation, Santa Monica, CA (1951)
Tarski, A.: Der Wahrheitsbegriff in den formalisierten Sprachen. Studia Philosophica 1 (1935); reprinted in Tarski 2, 51–198 (1986)
Tarski, A.: Einige methodologifche Unterfuchungen über die Definierbarkeit der Begriffe. Erkenntnis 5(1), 80–100 (1935)
Tarski, A.: What are logical notions? History and Philosophy of Logic 7(2), 143–154 (1986)
Thomas, S.: Reducts of random hypergraphs. Annals of Pure and Applied Logic 80(2), 165–193 (1996)
Thomas, S.: Reducts of the random graph. Journal of Symbolic Logic 56(1), 176–181 (1991)
Winkler, P.: Random structures and zero-one laws. Finite and infinite combinatorics in sets and logic, pp. 399–420. Springer, Netherlands (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Semenov, A., Soprunov, S., Uspensky, V. (2014). The Lattice of Definability. Origins, Recent Developments, and Further Directions. In: Hirsch, E.A., Kuznetsov, S.O., Pin, JÉ., Vereshchagin, N.K. (eds) Computer Science - Theory and Applications. CSR 2014. Lecture Notes in Computer Science, vol 8476. Springer, Cham. https://doi.org/10.1007/978-3-319-06686-8_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-06686-8_3
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06685-1
Online ISBN: 978-3-319-06686-8
eBook Packages: Computer ScienceComputer Science (R0)