English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

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 MK0-categorical arborescent structure has a decidable theory. Arborescent structures were introduced in [8] by abstracting a very simple property that trees possess. The main result of [8] is that every consistent, recursively axiomatizable theory of arborescent structures has a recursive model. In this paper we continue the study of arborescent structures, showing as the principal result that the theory of arborescent structures is interpretable in the theory of trees in a very strong way. From this, many interesting results are deducible; for example, the theory of arborescent structures is decidable (Corollary 4.2) and Vaught's conjecture is true for arborescent structures (Corollary 4.4). For a better appreciation of the significance of the notion of arborescence, some familiarity with the development leading to its isolation might be useful. Rabin [3] proved the decidability of S2S, and from this result the decidability of (more than) the first-order theory of trees easily follows by interpreting it in S2S. My interest in the theory of trees originated after proving in [5] that every p0-categorical theory of trees is decidable. This result was later shown to be connected with that of Rabin's when I proved in [4] that if a theory is interpretable in S2S, then so is every one of its Ho-categorical completions. At this point I became interested in finding some rather simple conditions which implied interpretability in S2S, or in the theory of trees, possibly some sort of structural property. I first considered partially ordered sets, and was able to extend the above results for trees to reticles [7], which are partially ordered sets not embedding the 4-element partially ordered set by showing that the theory of reticles is interpretable in the theory of trees. Reticles turned out to be a fascinating kind of partially ordered set which appeared to possess many of the nicer properties that trees do. I tried for some time to modify the interpretation of the theory of reticles in the theory of trees in order to Received by the editors June 4, 1980. 1980 Mathematics Subject Classification. Primary 03C65, 03C35. 'Research supported in part by NSF Grant MCS-7905028. Much of this paper was completed while I was visiting the University of California, San Diego, during the year 1978-1979. ? 1981 American Mathematical Society 0002-9947/81 /0000-0368/$04.75

Arborescent structures. II. Interpretability in the theory of trees