Rabin's Uniformization Problem
Gurevich, Yuri ; Shelah, Saharon
J. Symbolic Logic, Tome 48 (1983) no. 1, p. 1105-1119 / Harvested from Project Euclid
The set of all words in the alphabet $\{l, r\}$ forms the full binary tree $T$. If $x \in 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 $\phi^\ast(X, y)$ such that for every nonempty subset $X$ of $T$ there is a unique $y \in X$ that satisfies $\phi^\ast(X, y)$ in $T$.
Publié le : 1983-12-14
Classification: 
@article{1183741418,
     author = {Gurevich, Yuri and Shelah, Saharon},
     title = {Rabin's Uniformization Problem},
     journal = {J. Symbolic Logic},
     volume = {48},
     number = {1},
     year = {1983},
     pages = { 1105-1119},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183741418}
}
Gurevich, Yuri; Shelah, Saharon. Rabin's Uniformization Problem. J. Symbolic Logic, Tome 48 (1983) no. 1, pp.  1105-1119. http://gdmltest.u-ga.fr/item/1183741418/