Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-23T01:05:23.688Z Has data issue: false hasContentIssue false
  • English
  • Français

APPROXIMATING TREES AS COLOURED LINEAR ORDERS AND COMPLETE AXIOMATISATIONS OF SOME CLASSES OF TREES

Part of: General logic Model theory Ordered sets

Published online by Cambridge University Press:  08 June 2021

RUAAN KELLERMAN  and
VALENTIN GORANKO
RUAAN KELLERMAN
Affiliation:
DEPARTMENT OF MATHEMATICS AND APPLIED MATHEMATICS UNIVERSITY OF PRETORIAPRETORIA, SOUTH AFRICAE-mail:[email protected]
VALENTIN GORANKO
Affiliation:
DEPARTMENT OF PHILOSOPHY STOCKHOLM UNIVERSITYSTOCKHOLM, SWEDEN and SCHOOL OF MATHEMATICS (VISITING PROFESSORSHIP) UNIVERSITY OF THE WITWATERSRAND JOHANNESBURG, SOUTH AFRICA E-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We study the first-order theories of some natural and important classes of coloured trees, including the four classes of trees whose paths have the order type respectively of the natural numbers, the integers, the rationals, and the reals. We develop a technique for approximating a tree as a suitably coloured linear order. We then present the first-order theories of certain classes of coloured linear orders and use them, along with the approximating technique, to establish complete axiomatisations of the four classes of trees mentioned above.

Keywords

axiomatisationfirst-order theorycoloured linear ordertree

MSC classification

Primary: 03C07: Basic properties of first-order languages and structures
Secondary: 03B10: Classical first-order logic 03C64: Model theory of ordered structures; o-minimality 03C68: Other classical first-order model theory 06A05: Total order 06A06: Partial order, general
Type
Article
Information
The Journal of Symbolic Logic , Volume 86 , Issue 3 , September 2021 , pp. 1035 - 1065
Check for updates
Copyright
© Association for Symbolic Logic 2021

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Doets, K., Completeness and definability: Applications of the Ehrenfeucht game in second-order and intensional logic, Ph.D. thesis, University of Amsterdam, 1987.Google Scholar
Doets, K., Monadic ${\Pi}_1^1$ -theories of ${\Pi}_1^1$ -properties. Notre Dame Journal of Formal Logic, vol. 30 (1989), no. 2, pp. 224–240.CrossRefGoogle Scholar
Doets, K., Basic Model Theory , CSLI Publications & The European Association for Logic Language and Information, Stanford, 1996.Google Scholar
Droste, M., Structure of Partially Ordered Sets with Transitive Automorphism Groups,, Memoirs of the American Mathematical Society, vol. 57, no. 334, American Mathematical Society, Providence, 1985.Google Scholar
Ebbinghaus, H.D., Flum, J., and Thomas, W., Mathematical Logic, Springer, New York, 1996.Google Scholar
Feferman, S. and Vaught, R.L., The first order properties of products of algebraic systems. Fundamenta Mathematicae, vol. 47 (1959), pp. 57–103.10.4064/fm-47-1-57-103CrossRefGoogle Scholar
Goranko, V., Trees and finite branching. Proceedings of the 2nd Panhellenic Logic Symposium, 1999, pp. 91–101.Google Scholar
Goranko, V. and Kellerman, R., Classes and theories of trees associated with a class of linear orders. Logic Journal of the IGPL, vol. 19 (2010), pp. 217–232.CrossRefGoogle Scholar
Gurevich, Y. and Shelah, S., The decision problem for branching time logic, this Journal, vol. 50 (1985), pp. 668–681.Google Scholar
Gurevich, Y. and Shelah, S., To the decision problem for branching time logic, Foundations of Logic and Linguistics: Problems and Their Solutions (Dorn, G. and Weingartner, P., editors), Plenum, New York, 1985, pp. 181–198.CrossRefGoogle Scholar
Kellerman, R., First-order theories of bounded trees, 2019, under submission.Google Scholar
Kellerman, R., Goranko, V., and Zanardo, A., Structural theory of trees. II. Completeness and completions of trees, 2021, under submission.Google Scholar
Mwesigye, F. and Truss, J.K., Classification of finite coloured linear orderings. Order, vol. 28 (2011), pp. 387–397.CrossRefGoogle Scholar
Mwesigye, F. and Truss, J.K., Ehrenfeucht–Fraïssé games on ordinals. Annals of Pure and Applied Logic, vol. 169 (2018), no. 7, pp. 616–636.CrossRefGoogle Scholar
Rogers, J., Backofen, R., and Vijay-Shankar, K., A first-order axiomatization of the theory of finite trees. Journal of Logic, Language and Information, vol. 4 (1995), pp. 5–39.Google Scholar
Rosenstein, J.G., Linear Orderings , Academic Press, New York, 1982.Google Scholar
Rubin, M., The Reconstruction of Trees from Their Automorphism Groups , Contemporary Mathematics, vol. 151, American Mathematical Society, Providence, 1993.CrossRefGoogle Scholar
Schmerl, J., On ${\mathrm{\aleph}}_0$ -categoricity and the theory of trees. Fundamenta Mathematicae, vol. 94 (1977), pp. 121–128.CrossRefGoogle Scholar