Article ID Journal Published Year Pages File Type
4662353 Annals of Pure and Applied Logic 2009 15 Pages PDF
Abstract

We prove that for any k≥3 each element of the h-quasiorder of finite k-labeled forests is definable in the ordinary first order language and, respectively, each element of the h-quasiorder of (at most) countable k-labeled forests is definable in the language Lω1ω, in both cases provided that the minimal non-smallest elements are allowed as parameters. As corollaries, we characterize the automorphism groups of both structures and show that the structure of finite k-forests is atomic. Similar results hold true for two other relevant structures: the h-quasiorder of finite (resp. countable) k-labeled trees and of finite (resp. countable) k-labeled trees with a fixed label of the root element.

Related Topics
Physical Sciences and Engineering Mathematics Logic