Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-27T13:09:14.114Z Has data issue: false hasContentIssue false
  • English
  • Français

The full binary tree cannot be interpreted in a chain

Published online by Cambridge University Press:  12 March 2014

Alexander Rabinovich
Alexander Rabinovich*
Affiliation:
The Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We show that for no chain C there is a monadic-second order interpretation of the full binary tree in C.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 75 , Issue 4 , December 2010 , pp. 1489 - 1498
Copyright
Copyright © Association for Symbolic Logic 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[Bu62]Büchi, J. R., On a decision method in restricted second order arithmetic, Logic, Methodology and Philosophy of Science, Stanford University Press, 1962, pp. 1–11.Google Scholar
[BS73]Büchi, J. R. and Siefkes, D., The monadic second order theory of all countable ordinals, Lecture Notes in Mathematics, vol. 328, Springer, 1973.Google Scholar
[ER66]Elgot, C. and Rabin, M. O., Decidability and Undecidability of Extensions of Second (First) Order Theory of (Generalized) Successor, this Journal, vol. 31 (1966), no. 2, pp. 169–181.Google Scholar
[FV59]Feferman, S. and Vaught, R. L., The first order properties of products of algebraic systems. Fundamenta Mathematicae, vol. 47 (1959), pp. 57–103.CrossRefGoogle Scholar
[GMS83]Gurevich, Y., Magidor, M., and Shelah, S., The monadic theory of ω2, this Journal, vol. 48 (1983), pp. 387–398.Google Scholar
[GS89]Gurevich, Y and Shelah, S., On the strength of the interpretation method, this Journal, vol. 54 (1989), pp. 305–323.Google Scholar
[LS97]Lifsches, S. and Shelah, S., Peano arithmetic may not be interpretable in the monadic theory of linear orders, this Journal, vol. 62 (1997), pp. 848–872.Google Scholar
[LS98]Lifsches, S. and Shelah, S., Uniformization and Skolem functions in the class of trees, this Journal, vol. 63 (1998), pp. 103–127.Google Scholar
[LS99]Lifsches, S. and Shelah, S., Random graphs in the monadic theory of order. Archive for Mathematical Logic, vol. 38 (1999), pp. 273–312.CrossRefGoogle Scholar
[Rab69]Rabin, M. O., Decidability of second-order theories and automata on infinite trees, Transactions of the American Mathematical Society, vol. 141 (1969), pp. 1–35.Google Scholar
[Ro82]Rosenstein, J. G., Linear orderings, Academic Press Inc., New York, 1982.Google Scholar
[Sh75]Shelah, S., The monadic theory of order, Annals of Mathematics. Second Series, vol. 102 (1975), pp. 379–419.CrossRefGoogle Scholar