Open Access Open Access  Restricted Access Access granted  Restricted Access Subscription Access

Vol 58, No 5 (2019)

Article

Constructing Decidable Graphs from Decidable Structures

Bazhenov N.A., Harrison-Trainor M.

Abstract

It is shown that every structure (including one in an infinite language) can be transformed into a graph that is bi-interpretable with the original structure, for which the full elementary diagrams can be computed one from the other.

Algebra and Logic. 2019;58(5):369-382
pages 369-382 views

Classifications of Definable Subsets

Boyadzhiyska S., Lange K., Raz A., Scanlon R., Wallbaum J., Zhang X.

Abstract

Given a structure ℳ over ω and a syntactic complexity class \( \mathfrak{E} \), we say that a subset is \( \mathfrak{E} \)-definable in ℳ if there exists a C-formula Θ(x) in the language of ℳ such that for all x ∈ ω, we have x ∈ A iff Θ(x) is true in the structure. S. S. Goncharov and N. T. Kogabaev [Vestnik NGU, Mat., Mekh., Inf., 8, No. 4, 23-32 (2008)] generalized an idea proposed by Friedberg [J. Symb. Log., 23, No. 3, 309-316 (1958)], introducing the notion of a \( \mathfrak{E} \)-classification of M: a computable list of \( \mathfrak{E} \)-formulas such that every \( \mathfrak{E} \)-definable subset is defined by a unique formula in the list. We study the connections among\( {\varSigma}_1^0- \), \( d-{\varSigma}_1^0- \), and \( {\varSigma}_2^0 \)-classifications in the context of two families of structures, unbounded computable equivalence structures and unbounded computable injection structures. It is stated that every such injection structure has a \( {\varSigma}_1^0- \)classification, a \( {\varSigma}_1^0- \)classification, and a \( {\varSigma}_2^0 \)-classification. In equivalence structures, on the other hand, we find a richer variety of possibilities.

Algebra and Logic. 2019;58(5):383-404
pages 383-404 views

Σ-Preorderings in \( \mathbb{H}\mathbbm{F} \)(ℝ)

Morozov A.S.

Abstract

It is proved that the ordinal ω1cannot be embedded into a preordering Σ-definable with parameters in the hereditarily finite superstructure over the real numbers. As a corollary, we obtain the descriptions of ordinals Σ-presentable over\( \mathbb{H}\mathbbm{F} \)(ℝ) and of Gödel constructive sets of the form Lα. It is also shown that there are no Σ-presentations of structures of T-, m-, 1- and tt-degrees.

Algebra and Logic. 2019;58(5):405-416
pages 405-416 views

Simple Asymmetric Doubles, Their Automorphisms and Derivations

Pchelintsev S.V., Shashkov O.V.

Abstract

A simple right-alternative, but not alternative, superalgebra whose even part coincides with an algebra of second-order matrices is called an asymmetric double. It is known that such superalgebras are eight-dimensional. We give a solution to the isomorphism problem for asymmetric doubles, point out their automorphism groups and derivation superalgebras.

Algebra and Logic. 2019;58(5):417-433
pages 417-433 views

Primitive Normality and Primitive Connectedness of a Class of Divisible Polygons

Stepanova A.A., Krasitskaya A.I.

Abstract

We study monoids over which a class of divisible S-polygons is primitive normal or primitive connected. It is shown that for an arbitrary monoid S, the class of divisible polygons is primitive normal iff S is a linearly ordered monoid, and that it is primitive connected iff S is a group.

Algebra and Logic. 2019;58(5):434-440
pages 434-440 views

SESSIONS OF THE SEMINAR “ALGEBRA i LOGIKA”

Algebra and Logic. 2019;58(5):444-445
pages 444-445 views

Communications

On Realization of Index Sets in \( {\prod}_1^0 \)-Classes

Downey R., Melnikov A.G.
Algebra and Logic. 2019;58(5):441-443
pages 441-443 views