On effective presentations of formal concept lattices.
On elementary cuts in recursively saturated models of Peano Arithmetic
On extending automorphisms of models of Peano Arithmetic
Continuing the earlier research in [10] we give some information on extending automorphisms of models of PA to end extensions and cofinal extensions.
On problems of databases over a fixed infinite universe
In the relational model of databases a database state is thought of as a finite collection of relations between elements. For many applications it is convenient to pre-fix an infinite domain where the finite relations are going to be defined. Often, we also fix a set of domain functions and/or relations. These functions/relations are infinite by their nature. Some special problems arise if we use such an approach. In the paper we discuss some of the problems. We show that there exists a recursive...
On quasiresolvent periodic Abelian groups.
On the Ershov upper semilattice .
On the existence of super-decomposable pure-injective modules over strongly simply connected algebras of non-polynomial growth
Assume that k is a field of characteristic different from 2. We show that if Γ is a strongly simply connected k-algebra of non-polynomial growth, then there exists a special family of pointed Γ-modules, called an independent pair of dense chains of pointed modules. Then it follows by a result of Ziegler that Γ admits a super-decomposable pure-injective module if k is a countable field.
On the index sets of -subsets of the real numbers.
On the problem of finite signature.
On the relation of -reducibility between admissible sets.
Recursive expansions
Let A be a recursive structure, and let ψ be a recursive infinitary sentence involving a new relation symbol. The main result of the paper gives syntactical conditions which are necessary and sufficient for every recursive copy of A to have a recursive expansion to a model of ψ, provided A satisfies certain decidability conditions. The decidability conditions involve a notion of rank. The main result is applied to prove some earlier results of Metakides-Nerode and Goncharov. In these applications,...
Relatively recursive expansions
In this paper, we consider the following basic question. Let A be an L-structure and let ψ be an infinitary sentence in the language L∪R, where R is a new relation symbol. When is it the case that for every B ≅ A, there is a relation R such that (B,R) ⊨ ψ and ? We succeed in giving necessary and sufficient conditions in the case where ψ is a “recursive” infinitary sentence. (A recursive infinitary formula is an infinitary formula with recursive disjunctions and conjunctions.) We consider also...
Relatively recursive expansions II
In [AK], we asked when a recursive structure A and a sentence φ, with a new relation symbol, have the following property: for each ℬ≅ A there is a relation S such that S is recursive relative to ℬ and ℬ,S)⊨ φ. Here we consider several related properties, in which there is a uniform procedure for determining S from ℬ ≅A, or from ℬ,¯b)≅(A,ā), for some fixed sequence of parameters ā from A; or in which ℬ and S are required to be recursive. We investigate relationships between these properties, showing...
Restrictions on the degree spectra of algebraic structures.
Results on automorphisms of recursively saturated models of PA
Strong categoricity.
The degree spectra of definable relations on Boolean algebras.
The effective Borel hierarchy
Let K be a subclass of Mod() which is closed under isomorphism. Vaught showed that K is (respectively, ) in the Borel hierarchy iff K is axiomatized by an infinitary (respectively, ) sentence. We prove a generalization of Vaught’s theorem for the effective Borel hierarchy, i.e. the Borel sets formed by union and complementation over c.e. sets. This result says that we can axiomatize an effective or effective Borel set with a computable infinitary sentence of the same complexity. This result...
Weakly maximal decidable structures
We prove that there exists a structure M whose monadic second order theory is decidable, and such that the first-order theory of every expansion of M by a constant is undecidable.
Автоморфизмы булевых алгебр, рeкурсивных на атомах.