卷 58, 编号 2 (2019)

The concept of a generalized wreath product of permutation m-groups is introduced, and it is proved that an m-transitive permutation group embeds into a generalized wreath product of its primitive components.

We give a criterion for the countable spectrum to be maximal in small binary quite o-minimal theories of finite convexity rank.

A standard way to capture the inherent complexity of the isomorphism type of a countable structure is to consider the set of all Turing degrees relative to which the given structure has a computable isomorphic copy. This set is called the degree spectrum of a structure. Similarly, to characterize the complexity of models of a theory, one may examine the set of all degrees relative to which the theory has a computable model. Such a set of degrees is called the degree spectrum of a theory. We generalize these two notions to arbitrary equivalence relations. For a structure \( \mathcal{A} \) and an equivalence relation E, the degree spectrum DgSp(\( \mathcal{A} \), E) of \( \mathcal{A} \) relative to E is defined to be the set of all degrees capable of computing a structure \( \mathcal{B} \) that is E-equivalent to \( \mathcal{A} \). Then the standard degree spectrum of \( \mathcal{A} \) is DgSp(\( \mathcal{A} \), ≅) and the degree spectrum of the theory of \( \mathcal{A} \) is DgSp(\( \mathcal{A} \), ≡). We consider the relations \( {\equiv}_{\sum_n} \) (\( \mathcal{A}{\equiv}_{\sum_n}\mathcal{B} \) iff the Σ_n theories of \( \mathcal{A} \) and \( \mathcal{B} \) coincide) and study degree spectra with respect to \( {\equiv}_{\sum_n} \).

Functions of the algebra of logic that can be realized by read-once formulas over finite bases are studied. Necessary and sufficient conditions are derived under which functions of the algebra of logic are read-once in pre-elementary bases {−, ·,∨, 0, 1, x₁ · . . . · x_n ∨ \( {\overline{x}}_1 \)· . . . · \( {\overline{x}}_n \)} and {−, ·,∨, 0, 1, x₁(x₂ ∨ x₃ · . . . · x_n) ∨ x₂\( {x}_2{\overline{x}}_3 \) · . . . · \( {\overline{x}}_n \)} where n ≥ 4. This completes the description of classes of read-once functions of the algebra of logic in all pre-elementary bases.