UNIFORMIZATION AND SKOLEM FUNCTIONS IN THE CLASS OF TREES

The monadic second-order theory of trees allows quantification over el ements and over arbitrary subsets. We classify the class of trees with respect to the question: does a tree T have definable Skolem Function s (by a monadic formula with parameters)? This continues [6] where the question was asked only with respect to choice functions. A natural s ubclass is defined and proved to be the class of trees with definable Skolem functions. Along the way we investigate the spectrum of definab le well orderings of well ordered chains.