Patrizio Cintioli

We consider the structure of all labeled trees, called also infinite terms, in the first order language with function symbols in a recursive signature of cardinality at least two and at least a symbol of arity two, with equality and a binary relation symbol which is interpreted to be the subtree relation. The existential theory over of this structure is decidable (see Tulipani [9]), but more complex fragments of the theory are undecidable. We prove that the theory of the structure is in , where formulas are those in prenex form consisting of a string of unbounded existential quantifiers followed by a string of arbitrary quantifiers all bounded with respect to . Since the fragment of the theory was already known to be -hard (see Marongiu and Tulipani [5]), it is now established to be -complete

We consider the structure $IT_S$ of all labeled trees, called also infinite terms, in the first order language ${\cal L}$ with function symbols in a recursive signature $S$ of cardinality at least two and at least a symbol of arity two, with equality and a binary relation symbol $\sqsubseteq$ which is interpreted to be the subtree relation. The existential theory over ${\cal L}$ of this structure is decidable, but more complex fragments of the theory are undecidable. We prove that the $ \exists\Delta$ theory of the structure is in $\Sigma^1_1$, where $ \exists\Delta$ formulas are those in prenex form consisting of a string of unbounded existential quantifiers followed by a string of arbitrary quantifiers all bounded with respect to $\sqsubseteq$. Since the fragment of the theory was already known to be $\Sigma^1_1$-hard, it is now established to be $\Sigma^1_1$-complete.

Previously, both Soare and Simpson considered sets without subsets of higher -degree. Cintioli and Silvestri, for a reducibility , define the concept of a -introimmune set. For the most common reducibilities , a set does not contain subsets of higher -degree if and only if it is -introimmune. In this paper we consider -introimmune and -introimmune sets and examine how structurally easy such sets can be. In other words we ask, What is the smallest class of the Kleene's Hierarchy containing -introimmune sets for ? We answer the question by proving the existence of -introimmune sets in the class , bi--introimmune sets in , and bi--introimmune sets in