Monadic Second Order Definable Relations on the Binary Tree

Lauchli, Hans; Savioz, Christian

J. Symbolic Logic, Tome 52 (1987) no. 1, p. 219-226 / Harvested from Project Euclid

Résumé

Let S2S [WS2S] espectively be the storn [weak] monadic second order theory of the binary tree $T$ in the language of two successor functions. An S2S-formula whose free variables are just individual variables defines a relation on $T$ (rather than on the power set of $T$). We show that S2S and WS2S define the same relations on $T$, and we give a simple characterization of these relations.

Publié le : 1987-03-14
Classification:

@article{1183742326,
     author = {Lauchli, Hans and Savioz, Christian},
     title = {Monadic Second Order Definable Relations on the Binary Tree},
     journal = {J. Symbolic Logic},
     volume = {52},
     number = {1},
     year = {1987},
     pages = { 219-226},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183742326}
}

Lauchli, Hans; Savioz, Christian. Monadic Second Order Definable Relations on the Binary Tree. J. Symbolic Logic, Tome 52 (1987) no. 1, pp.  219-226. http://gdmltest.u-ga.fr/item/1183742326/