Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Arborescent structures. II. Interpretability in the theory of trees


Author: James H. Schmerl
Journal: Trans. Amer. Math. Soc. 266 (1981), 629-643
MSC: Primary 03C65; Secondary 03B15, 03B25, 03C15, 03F25, 06A10
DOI: https://doi.org/10.1090/S0002-9947-1981-0617556-9
MathSciNet review: 617556
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The first-order theory of arborescent structures is shown to be completely faithfully interpretable in the first-order theory of trees. It follows from this interpretation that Vaught's conjecture is true for arborescent structures, the theory of arborescent structures is decidable, and every $ {\aleph _0}$-categorical arborescent structure has a decidable theory.


References [Enhancements On Off] (What's this?)

  • [1] J. Ershov, Skolem functions and constructive models, Algebra and Logic 12 (1973), 644-654. MR 0465841 (57:5727)
  • [2] J. D. Monk, Mathematical logic, Springer-Verlag, New York, 1976. MR 0465767 (57:5656)
  • [3] M. O. Rabin, Decidability of second-order theories and automata on finite trees, Trans. Amer. Math. Soc. 141 (1969), 1-35. MR 0246760 (40:30)
  • [4] J. H. Schmerl, The decidability of some $ {\aleph _0}$-categorical theories, Colloq. Math. 36 (1976), 165-169. MR 0441715 (56:113)
  • [5] -, On $ {\aleph _0}$-categoricity and the theory of trees, Fund. Math. 94 (1977), 121-128. MR 0437337 (55:10269)
  • [6] -, $ {\aleph _0}$-categoricity and comparability graphs, Logic Colloq. '77, North-Holland, Amsterdam, 1978. MR 519817 (83i:03054)
  • [7] -, Decidability and $ {\aleph _0}$-categoricity of theories of partially ordered sets, J. Symbolic Logic (to appear).
  • [8] -, Arborescent structures. I: Recursive models, Aspects of Effective Algebra (to appear).
  • [9] J. R. Schoenfield, Mathematical logic, Addison-Wesley, Reading, Mass., 1967. MR 0225631 (37:1224)
  • [10] J. R. Steel, On Vaught's conjecture, (Cabal Seminar 1976-1977), Lecture Notes in Math., vol. 689, Springer-Verlag, Berlin and New York, 1978, pp. 193-208. MR 526920 (81b:03036)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03C65, 03B15, 03B25, 03C15, 03F25, 06A10

Retrieve articles in all journals with MSC: 03C65, 03B15, 03B25, 03C15, 03F25, 06A10


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1981-0617556-9
Article copyright: © Copyright 1981 American Mathematical Society

American Mathematical Society