Arborescent structures. II. Interpretability in the theory of trees
HTML articles powered by AMS MathViewer
- by James H. Schmerl PDF
- Trans. Amer. Math. Soc. 266 (1981), 629-643 Request permission
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
- Ju. L. Eršov, Skolem functions and constructive models, Algebra i Logika 12 (1973), 644–654, 735 (Russian). MR 0465841
- J. Donald Monk, Mathematical logic, Graduate Texts in Mathematics, No. 37, Springer-Verlag, New York-Heidelberg, 1976. MR 0465767, DOI 10.1007/978-1-4684-9452-5
- Michael O. Rabin, Decidability of second-order theories and automata on infinite trees, Trans. Amer. Math. Soc. 141 (1969), 1–35. MR 246760, DOI 10.1090/S0002-9947-1969-0246760-1
- James H. Schmerl, The decidability of some $\aleph _{0}$-categorical theories, Colloq. Math. 36 (1976), no. 2, 165–169. MR 441715, DOI 10.4064/cm-36-2-165-169
- James H. Schmerl, On $\aleph _{0}$-categoricity and the theory of trees, Fund. Math. 94 (1977), no. 2, 121–128. MR 437337, DOI 10.4064/fm-94-2-121-128
- James H. Schmerl, $\aleph _{0}$-categoricity and comparability graphs, Logic Colloquium ’77 (Proc. Conf., Wrocław, 1977) Studies in Logic and the Foundations of Mathematics, vol. 96, North-Holland, Amsterdam-New York, 1978, pp. 221–228. MR 519817 —, Decidability and ${\aleph _0}$-categoricity of theories of partially ordered sets, J. Symbolic Logic (to appear). —, Arborescent structures. I: Recursive models, Aspects of Effective Algebra (to appear).
- Joseph R. Shoenfield, Mathematical logic, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1967. MR 0225631
- John R. Steel, On Vaught’s conjecture, Cabal Seminar 76–77 (Proc. Caltech-UCLA Logic Sem., 1976–77) Lecture Notes in Math., vol. 689, Springer, Berlin, 1978, pp. 193–208. MR 526920
Additional Information
- © Copyright 1981 American Mathematical Society
- 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