### Uniformization, choice functions and well orders in the class of trees

by Lifsches and Shelah. [LeSh:539]

J Symbolic Logic, 1996

The monadic second-order theory of trees allows
quantification over elements and over arbitrary subsets. We
classify the class of trees with respect to the question: does a
tree T have a definable choice function (by a monadic formula
with parameters)? A natural dichotomy arises where the trees
that fall in the first class don't have a definable choice
function and the trees in the second class have even a definable
well ordering of their elements. This has a close connection to
the uniformization problem.

Back to the list of publications