First-order aspects of tree paths
Loading...
Date
Authors
Kellerman, Ruaan
Journal Title
Journal ISSN
Volume Title
Publisher
Oxford University Press
Abstract
Tree paths are investigated using first-order logic. The following
results are obtained: (i) every definable path can be defined by a firstorder
formula using at most one parameter chosen from the path itself;
(ii) a canonical representation of the formulas that define definable
paths is obtained; and (iii) every tree that has only finitely many paths
that are not definable is n-equivalent to a tree of which all paths are
definable. Moreover, a certain property that might be expected to
hold, involving the transfer of n-equivalence between trees, is shown
not to be true.
Description
Keywords
Tree paths, First-order logic
Sustainable Development Goals
Citation
Kellerman, R 2015, 'First-order aspects of tree paths', Logic Journal of the IGPL, vol. 23, no. 4, pp. 688-704.