Approximating trees as coloured linear orders and complete axiomatisations of some classes of trees

Journal of Symbolic Logic 86 (3):1035-1065 (2021)
  Copy   BIBTEX

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.

Similar books and articles

Countably categorical coloured linear orders.Feresiano Mwesigye & John K. Truss - 2010 - Mathematical Logic Quarterly 56 (2):159-163.
Decidable discrete linear orders.M. Moses - 1988 - Journal of Symbolic Logic 53 (2):531-539.
Gap structure after forcing with a coherent Souslin tree.Carlos Martinez-Ranero - 2013 - Archive for Mathematical Logic 52 (3-4):435-447.
A first-order axiomatization of the theory of finite trees.Rolf Backofen, James Rogers & K. Vijay-Shanker - 1995 - Journal of Logic, Language and Information 4 (1):5-39.
The isomorphism problem for classes of computable fields.Wesley Calvert - 2004 - Archive for Mathematical Logic 43 (3):327-336.

Analytics

Added to PP
2021-12-06

Downloads
74 (#203,030)

6 months
74 (#52,140)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Valentin Goranko
Stockholm University

Citations of this work

First-order theories of bounded trees.Ruaan Kellerman - 2021 - Archive for Mathematical Logic 61 (1):263-297.

Add more citations

References found in this work

A first-order axiomatization of the theory of finite trees.Rolf Backofen, James Rogers & K. Vijay-Shanker - 1995 - Journal of Logic, Language and Information 4 (1):5-39.
The decision problem for branching time logic.Yuri Gurevich & Saharon Shelah - 1985 - Journal of Symbolic Logic 50 (3):668-681.
Linear Orderings.Joseph G. Rosenstein - 1983 - Journal of Symbolic Logic 48 (4):1207-1209.
Ehrenfeucht–Fraïssé games on ordinals.F. Mwesigye & J. K. Truss - 2018 - Annals of Pure and Applied Logic 169 (7):616-636.

View all 8 references / Add more references