Endpoints of Associated Intervals
Boris A. Romov
The relational description of endpoints of an associated interval of restriction- closed partial clones, defined on a finite set, having the same clone as their total component, is presented by utilizing model-theoretical approach (positive primitive quantifier elimination criteria). For Boolean clones, endpoints of such intervals are described via &-formulas from relations that determine those clones, which include intervals associated with clones forming eight infinite descending chains. It is shown that if a Boolean clone is finitely definable (determined by a finite set of relations), then, with 19 exceptions, both min and max elements of this interval are also finitely definable. In case, when a clone on a finite set is not finitely definable, then both endpoints of the associated interval are also not finitely definable partial clones. The decidability of problems to recognize the endpoints of associated intervals for finitely definable clones, as well as to recognize some model-theoretical properties connected with them is established*.
Keywords: Associated interval; positive primitive elimination set; extendable partial clone; polyhomogeneous structure.