We study the Weihrauch complexity for problems of finding an elementary embedding (within the framework of the classical model theory). We prove that the problem of finding an elementary embedding from a prime model M into an arbitrary model N (which is elementarily equivalent to M) is strongly Weihrauch equivalent to the familiar problem lim (i.e., the problem of finding the limit of a sequence in Baire space). We show that the problem of finding an elementary embedding from an arbitrary model M into a countable saturated model N is also strongly Weihrauch equivalent to lim.
We study one class of semirings close to distributive lattices, namely: semirings with commutative idempotent multiplication, satisfying the identity x + 2xy = x. For such semirings, the equalizing properties are investigated (Theorems 7, 8, 10, Proposition 12). The results obtained can be applied to distributive lattices (Propositions 15, 16, 17). The work provides examples and explanatory notes.
We study the generic nature of simplicity, non-affinity and polynomial completeness of finite n-quasigroups. It is shown that for fixed n almost all n-quasigroups are strongly non-affine, i.e., not isotopic to affine n-quasigroups. Exact number of simple, affine and simultaneously simple and affine n-quasigroups of the order 4 is established. As a corollary, it is proven that almost all n-quasigroups of the order 4 are polynomially complete and strongly non-affine.
We study the additive theory of arbitrary figures in linear spaces, that is, the theory of addition extended to sets of vectors. Our main result is the following: if a linear space is infinite, then the additive theory of figures allows to interpret second-order arithmetic and, therefore, has this or higher degree of undecidability. For countably infinite spaces, we prove the opposite result, the theory of figures can be interpreted in second-order arithmetic. Therefore, these theories are algorithmically equivalent. For uncountable spaces, the last question remains open. We show that for spaces of different cardinalities, the additive theories of figures can be elementary non-equivalent.
The review outlines the foundations of the theory of separable numberings of universal algebras.
The work is devoted to the algebraic theory of structured automata. We consider semigroup automata without output signals over graphs, which are called graphic semiautomata. We study partial graphic semiautomata, each input signal of which is a partial endomorphism of the state graph. In the category of partial graphic semiautomata over the graph G = (X, ρ), special attention is paid to the semiautomaton PAtm(G) = (G, PEnd(G),⋆) with semigroup PEnd(G) of all partial endomorphisms of the graph G, since it is a universally attracting object in this category and is called a universal partial graphic semiautomaton. The main result of the work is the proof of the relatively elementary definability of the class of universal partial graphic semiautomata over nontrivial reflexive graphs in the class of semigroups, and applications of got relatively elementary definability.
