Serikzhan A. Badaev
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Serikzhan A. Badaev has a total of 20 co-authors. Here are the top co-authors by number of shared publications:
- Sergey Savostyanovich Goncharov
Sobolev Institute of Mathematics, Novosibirsk, Russia
9 shared publications - Andrea Sorbi
Dipartimento di Ingegneria Informatica e Scienze Matematiche, Università Degli Studi di Siena, Siena, Italy
7 shared publications A. Sorbi
Dipartimento di Scienze Matematiche ed Informatiche “Roberto Magari
3 shared publications- Manat Mustafa
Nazarbayev University
3 shared publications - Sergey Goncharov
Novosibirsk State University
3 shared publications - Birzhan S. Kalmurzayev
Kazakh-British Technical University
2 shared publications
Latest Publications
- Open Access
- 27 September 2025
- Published by Kazakh-British Technical University in Herald of the Kazakh-British technical university
- Vol. 22 (3) , 199-209
A NOTE ON THE STRUCTURE OF MINIMAL DARK CEERS
The structure of computably enumerable equivalence relations under computable reducibility (commonly referred to as ceers) has been actively developed over the past 25 years. A comprehensive survey by Andrews and Sorbi presented numerous structural properties of ceers, most notably investigating the existence of joins and meets in the degree structure of ceers. They divided the structure into two definable parts: dark ceers (ceers without an effective transversal) and light ceers (ceers with an effective transversal). They also showed the existence of an infinite number of minimal dark ceers (modulo equivalence relations with finitely many classes). Minimal dark ceers exhibit the distinctive property that every pair of classes is computably inseparable. Furthermore, the classes of weakly precomplete equivalence relations (i.e. those that lack a computable diagonal functions) are also computably inseparable. In this context, a natural question arises: do minimal dark equivalence relations exist that are not weakly precomplete? This paper provides an affirmative answer to this question. Moreover, we establish the existence of an infinite family of non-weakly precomplete minimal dark ceers that avoids lower cone of a given non-universal ceer. We denote by FC the set of ceers consisting of only finite classes. Andrews, Schweber, Sorbi showed the existence of dark FC equivalences. In this paper, we prove that over any dark FC ceer, there exists an infinite antichain of dark FC ceers.
- 27 September 2025
- Published by Kazakh-British Technical University in Herald of the Kazakh-British technical university
- Vol. 22 (3) , 199-209
Open AccessA NOTE ON THE STRUCTURE OF MINIMAL DARK CEERS
The structure of computably enumerable equivalence relations under computable reducibility (commonly referred to as ceers) has been actively developed over the past 25 years. A comprehensive survey by Andrews and Sorbi presented numerous structural properties of ceers, most notably investigating the existence of joins and meets in the degree structure of ceers. They divided the structure into two definable parts: dark ceers (ceers without an effective transversal) and light ceers (ceers with an effective transversal). They also showed the existence of an infinite number of minimal dark ceers (modulo equivalence relations with finitely many classes). Minimal dark ceers exhibit the distinctive property that every pair of classes is computably inseparable. Furthermore, the classes of weakly precomplete equivalence relations (i.e. those that lack a computable diagonal functions) are also computably inseparable. In this context, a natural question arises: do minimal dark equivalence relations exist that are not weakly precomplete? This paper provides an affirmative answer to this question. Moreover, we establish the existence of an infinite family of non-weakly precomplete minimal dark ceers that avoids lower cone of a given non-universal ceer. We denote by FC the set of ceers consisting of only finite classes. Andrews, Schweber, Sorbi showed the existence of dark FC equivalences. In this paper, we prove that over any dark FC ceer, there exists an infinite antichain of dark FC ceers.
- 13 June 2019
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 85 (1) , 61-86
ON ISOMORPHISM CLASSES OF COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS
We examine how degrees of computably enumerable equivalence relations (ceers) under computable reduction break down into isomorphism classes. Two ceers are isomorphic if there is a computable permutation of ω which reduces one to the other. As a method of focusing on nontrivial differences in isomorphism classes, we give special attention to weakly precomplete ceers. For any degree, we consider the number of isomorphism types contained in the degree and the number of isomorphism types of weakly precomplete ceers contained in the degree. We show that the number of isomorphism types must be 1 or ω, and it is 1 if and only if the ceer is self-full and has no computable classes. On the other hand, we show that the number of isomorphism types of weakly precomplete ceers contained in the degree can be any member of $[0,\omega ]$ . In fact, for any $n \in [0,\omega ]$ , there is a degree d and weakly precomplete ceers ${E_1}, \ldots ,{E_n}$ in d so that any ceer R in d is isomorphic to ${E_i} \oplus D$ for some $i \le n$ and D a ceer with domain either finite or ω comprised of finitely many computable classes. Thus, up to a trivial equivalence, the degree d splits into exactly n classes.We conclude by answering some lingering open questions from the literature: Gao and Gerdes [11] define the collection of essentially FC ceers to be those which are reducible to a ceer all of whose classes are finite. They show that the index set of essentially FC ceers is ${\rm{\Pi }}_3^0$ -hard, though the definition is ${\rm{\Sigma }}_4^0$ . We close the gap by showing that the index set is ${\rm{\Sigma }}_4^0$ -complete. They also use index sets to show that there is a ceer all of whose classes are computable, but which is not essentially FC, and they ask for an explicit construction, which we provide.Andrews and Sorbi [4] examined strong minimal covers of downwards-closed sets of degrees of ceers. We show that if $\left( {{E_i}} \right)$ is a uniform c.e. sequence of non universal ceers, then $\left\{ {{ \oplus _{i \le j}}{E_i}|j \in \omega } \right\}$ has infinitely many incomparable strong minimal covers, which we use to answer some open questions from [4].Lastly, we show that there exists an infinite antichain of weakly precomplete ceers.- 13 June 2019
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 85 (1) , 61-86
ON ISOMORPHISM CLASSES OF COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS
We examine how degrees of computably enumerable equivalence relations (ceers) under computable reduction break down into isomorphism classes. Two ceers are isomorphic if there is a computable permutation of ω which reduces one to the other. As a method of focusing on nontrivial differences in isomorphism classes, we give special attention to weakly precomplete ceers. For any degree, we consider the number of isomorphism types contained in the degree and the number of isomorphism types of weakly precomplete ceers contained in the degree. We show that the number of isomorphism types must be 1 or ω, and it is 1 if and only if the ceer is self-full and has no computable classes. On the other hand, we show that the number of isomorphism types of weakly precomplete ceers contained in the degree can be any member of $[0,\omega ]$ . In fact, for any $n \in [0,\omega ]$ , there is a degree d and weakly precomplete ceers ${E_1}, \ldots ,{E_n}$ in d so that any ceer R in d is isomorphic to ${E_i} \oplus D$ for some $i \le n$ and D a ceer with domain either finite or ω comprised of finitely many computable classes. Thus, up to a trivial equivalence, the degree d splits into exactly n classes.We conclude by answering some lingering open questions from the literature: Gao and Gerdes [11] define the collection of essentially FC ceers to be those which are reducible to a ceer all of whose classes are finite. They show that the index set of essentially FC ceers is ${\rm{\Pi }}_3^0$ -hard, though the definition is ${\rm{\Sigma }}_4^0$ . We close the gap by showing that the index set is ${\rm{\Sigma }}_4^0$ -complete. They also use index sets to show that there is a ceer all of whose classes are computable, but which is not essentially FC, and they ask for an explicit construction, which we provide.Andrews and Sorbi [4] examined strong minimal covers of downwards-closed sets of degrees of ceers. We show that if $\left( {{E_i}} \right)$ is a uniform c.e. sequence of non universal ceers, then $\left\{ {{ \oplus _{i \le j}}{E_i}|j \in \omega } \right\}$ has infinitely many incomparable strong minimal covers, which we use to answer some open questions from [4].Lastly, we show that there exists an infinite antichain of weakly precomplete ceers.- 15 December 2018
- Published by National Academy of Sciences of the Republic of Kazakshtan in NEWS OF THE NATIONAL ACADEMY OF SCIENCES OF THE REPUBLIC OF KAZAKHSTAN
- Vol. 6 (6) , 49-53
UNIVERSAL POSITIVE PREORDERS
In this paper, we investigate universal objects in the class of positive preorders with respect to computable reducibility, we constructed a computable numbering of this class and proved theorems on the existence of a universal positive lattice and a universal weakly precomplete.
- 15 December 2018
- Published by National Academy of Sciences of the Republic of Kazakshtan in NEWS OF THE NATIONAL ACADEMY OF SCIENCES OF THE REPUBLIC OF KAZAKHSTAN
- Vol. 6 (6) , 49-53
UNIVERSAL POSITIVE PREORDERS
In this paper, we investigate universal objects in the class of positive preorders with respect to computable reducibility, we constructed a computable numbering of this class and proved theorems on the existence of a universal positive lattice and a universal weakly precomplete.
- 1 September 2018
- Published by Springer Nature in Algebra and Logic
- Vol. 57 (4) , 275-288
Some Absolute Properties of A-Computable Numberings
- 1 September 2018
- Published by Springer Nature in Algebra and Logic
- Vol. 57 (4) , 275-288
Some Absolute Properties of A-Computable Numberings
- 1 December 2016
- Published by Springer Nature
- p. 418-451
A Survey on Universal Computably Enumerable Equivalence Relations
- 1 December 2016
- Published by Springer Nature
- p. 418-451
A Survey on Universal Computably Enumerable Equivalence Relations
- 12 February 2016
- Published by Wiley in Mathematical Logic Quarterly
- Vol. 62 (1-2) , 111-127
Weakly precomplete computably enumerable equivalence relations
Using computable reducibility ⩽ on equivalence relations, we investigate weakly precomplete ceers (a “ceer” is a computably enumerable equivalence relation on the natural numbers), and we compare their class with the more restricted class of precomplete ceers. We show that there are infinitely many isomorphism types of universal (in fact uniformly finitely precomplete) weakly precomplete ceers , that are not precomplete; and there are infinitely many isomorphism types of non‐universal weakly precomplete ceers. Whereas the Visser space of a precomplete ceer always contains an infinite effectively discrete subset, there exist weakly precomplete ceers whose Visser spaces do not contain infinite effectively discrete subsets. As a consequence, contrary to precomplete ceers which always yield partitions into effectively inseparable sets, we show that although weakly precomplete ceers always yield partitions into computably inseparable sets, nevertheless there are weakly precomplete ceers for which no equivalence class is creative. Finally, we show that the index set of the precomplete ceers is Σ3‐complete, whereas the index set of the weakly precomplete ceers is Π3‐complete. As a consequence of these results, we also show that the index sets of the uniformly precomplete ceers and of the e‐complete ceers are Σ3‐complete.
- 12 February 2016
- Published by Wiley in Mathematical Logic Quarterly
- Vol. 62 (1-2) , 111-127
Weakly precomplete computably enumerable equivalence relations
Using computable reducibility ⩽ on equivalence relations, we investigate weakly precomplete ceers (a “ceer” is a computably enumerable equivalence relation on the natural numbers), and we compare their class with the more restricted class of precomplete ceers. We show that there are infinitely many isomorphism types of universal (in fact uniformly finitely precomplete) weakly precomplete ceers , that are not precomplete; and there are infinitely many isomorphism types of non‐universal weakly precomplete ceers. Whereas the Visser space of a precomplete ceer always contains an infinite effectively discrete subset, there exist weakly precomplete ceers whose Visser spaces do not contain infinite effectively discrete subsets. As a consequence, contrary to precomplete ceers which always yield partitions into effectively inseparable sets, we show that although weakly precomplete ceers always yield partitions into computably inseparable sets, nevertheless there are weakly precomplete ceers for which no equivalence class is creative. Finally, we show that the index set of the precomplete ceers is Σ3‐complete, whereas the index set of the weakly precomplete ceers is Π3‐complete. As a consequence of these results, we also show that the index sets of the uniformly precomplete ceers and of the e‐complete ceers are Σ3‐complete.
- 1 November 2014
- Published by Springer Nature in Algebra and Logic
- Vol. 53 (5) , 355-364
Generalized Computable Universal Numberings
- 1 November 2014
- Published by Springer Nature in Algebra and Logic
- Vol. 53 (5) , 355-364
Generalized Computable Universal Numberings
- 13 September 2014
- Published by Springer Nature in Archive for Mathematical Logic
- Vol. 54 (1-2) , 59-73
Friedberg numberings in the Ershov hierarchy
- 13 September 2014
- Published by Springer Nature in Archive for Mathematical Logic
- Vol. 54 (1-2) , 59-73
Friedberg numberings in the Ershov hierarchy
- 1 September 2014
- Published by Springer Nature in Algebra and Logic
- Vol. 53 (4) , 271-286
Families Without Minimal Numberings
- 1 September 2014
- Published by Springer Nature in Algebra and Logic
- Vol. 53 (4) , 271-286
Families Without Minimal Numberings
- 12 July 2012
- Published by Wiley in Mathematical Logic Quarterly
- Vol. 58 (4-5) , 366-376
Rogers semilattices of families of two embedded sets in the Ershov hierarchy
Let a be a Kleene's ordinal notation of a nonzero computable ordinal. We give a sufficient condition on a, so that for every \documentclass{article}\usepackage{amssymb}\pagestyle{empty}$\Sigma ^{-1}_a$ ‐computable family of two embedded sets, i.e., two sets A, B, with A properly contained in B, the Rogers semilattice of the family is infinite. This condition is satisfied by every notation of ω; moreover every nonzero computable ordinal that is not sum of any two smaller ordinals has a notation that satisfies this condition. On the other hand, we also give a sufficient condition on a, that yields that there is a \documentclass{article}\usepackage{amssymb}\pagestyle{empty}$\Sigma ^{-1}_a$ ‐computable family of two embedded sets, whose Rogers semilattice consists of exactly one element; this condition is satisfied by all notations of every successor ordinal bigger than 1, and by all notations of the ordinal ω + ω; moreover every computable ordinal that is sum of two smaller ordinals has a notation that satisfies this condition. We also show that for every nonzero n ∈ ω, or n = ω, and every notation a of a nonzero ordinal there exists a \documentclass{article}\usepackage{amssymb}\pagestyle{empty}$\Sigma ^{-1}_a$ ‐computable family of cardinality n, whose Rogers semilattice consists of exactly one element.
- 12 July 2012
- Published by Wiley in Mathematical Logic Quarterly
- Vol. 58 (4-5) , 366-376
Rogers semilattices of families of two embedded sets in the Ershov hierarchy
Let a be a Kleene's ordinal notation of a nonzero computable ordinal. We give a sufficient condition on a, so that for every \documentclass{article}\usepackage{amssymb}\pagestyle{empty}$\Sigma ^{-1}_a$ ‐computable family of two embedded sets, i.e., two sets A, B, with A properly contained in B, the Rogers semilattice of the family is infinite. This condition is satisfied by every notation of ω; moreover every nonzero computable ordinal that is not sum of any two smaller ordinals has a notation that satisfies this condition. On the other hand, we also give a sufficient condition on a, that yields that there is a \documentclass{article}\usepackage{amssymb}\pagestyle{empty}$\Sigma ^{-1}_a$ ‐computable family of two embedded sets, whose Rogers semilattice consists of exactly one element; this condition is satisfied by all notations of every successor ordinal bigger than 1, and by all notations of the ordinal ω + ω; moreover every computable ordinal that is sum of two smaller ordinals has a notation that satisfies this condition. We also show that for every nonzero n ∈ ω, or n = ω, and every notation a of a nonzero ordinal there exists a \documentclass{article}\usepackage{amssymb}\pagestyle{empty}$\Sigma ^{-1}_a$ ‐computable family of cardinality n, whose Rogers semilattice consists of exactly one element.