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 -categorical arborescent structure has a decidable theory.

**[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**-categorical theories*, Colloq. Math.**36**(1976), 165-169. MR**0441715 (56:113)****[5]**-,*On**-categoricity and the theory of trees*, Fund. Math.**94**(1977), 121-128. MR**0437337 (55:10269)****[6]**-,*-categoricity and comparability graphs*, Logic Colloq. '77, North-Holland, Amsterdam, 1978. MR**519817 (83i:03054)****[7]**-,*Decidability and**-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)**

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