First-order aspects of tree paths

Loading...
Thumbnail Image

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.