Abstract

The set of all words in the alphabet {l, r} forms the full binary tree T. If x ∈ T then xl and xr are the left and the right successors of x respectively. We consider the monadic second-order language of the full binary tree with the two successor relations. This language allows quantification over elements of T and over arbitrary subsets of T. We prove that there is no monadic second-order formula φ * (X, y) such that for every nonempty subset X of T there is a unique y ∈ X that satisfies φ * (X, y) in T