Logical theories of trees
Date
2011-03-11
Authors
Kellerman, Ruaan
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Summary
Trees occur naturally in many mathematical settings as important partial
orders yet no systematic study of their rst-order theories exists. We investigate
some of the rst-order theories of trees. The two problems which
motivate the thesis are (i) the rst-order de nability of sets within a given
tree, and (ii) the rst-order de nability and axiomatisability of particular
classes of trees.
Of particular interest is the correspondence between the rst-order theory
of a tree and the rst-order theory of the class of linear orders which comprise
the paths in the tree. For every class C of linear orders we introduce eight
classes of trees collectively called the C-classes of trees, the paths of which
are related in various natural ways to the linear orders in C. We completely
establish both the set-theoretical relationships between these eight classes
of trees as well as the relationships between the rst-order theories of these
eight classes of trees. We also investigate some of the properties of these
rst-order theories.
A special case is where the class C consists of a single ordinal with
< !! since such ordinals are nitely axiomatisable. We obtain the rstorder
theory of the class of trees where every path is isomorphic to the ordinal
for any nite ordinal and also for the case where = !. The remaining
cases are more di cult because of the existence of unde nable paths in the
tree. For the cases where ! < < !! we introduce the notion of an almost
-tree and show that every almost -tree can be elementarily extended in a
natural way to a tree of which every path, de nable or unde nable, satis es
the rst-order theory of . We also examine what this elementary extension
of the almost -tree looks like for the case where = ! + 1.
Throughout the thesis we also investigate various rst-order properties
and theories of trees and establish some results in this regard.