Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings

Rogers Semilattices of limitwise monotonic
numberings
Zhansaya Tleuliyeva
joint work with Bazhenov N. and Mustafa M.
Nazarbayev University, Astana, Kazakhstan
Computability in Europe 2023

25 July 2023

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

1 / 19Outline

Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings

Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings• We investigate numberings for a special subclass of Σ02 sets —limitwise monotonic sets.
• A set A ⊆ ω is limitwise monotonic if either A = ∅, or A is therange of a limitwise monotonic function.
• A total function F : ω → ω is limitwise monotonic (or s-function) if
there is a computable function f (x, s) with the following properties:• f (x, s) ≤ f (x, s + 1) for all x and s, and• F (x) = lims f (x, s) for all x.

Such a function f is often called a limitwise monotonic
approximation of the function F .

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

2 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings• We investigate numberings for a special subclass of Σ02 sets —limitwise monotonic sets.
• A set A ⊆ ω is limitwise monotonic if either A = ∅, or A is therange of a limitwise monotonic function.
• A total function F : ω → ω is limitwise monotonic (or s-function) if
there is a computable function f (x, s) with the following properties:• f (x, s) ≤ f (x, s + 1) for all x and s, and• F (x) = lims f (x, s) for all x.

Such a function f is often called a limitwise monotonic
approximation of the function F .

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

2 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings• We investigate numberings for a special subclass of Σ02 sets —limitwise monotonic sets.
• A set A ⊆ ω is limitwise monotonic if either A = ∅, or A is therange of a limitwise monotonic function.
• A total function F : ω → ω is limitwise monotonic (or s-function) if
there is a computable function f (x, s) with the following properties:• f (x, s) ≤ f (x, s + 1) for all x and s, and• F (x) = lims f (x, s) for all x.

Such a function f is often called a limitwise monotonic
approximation of the function F .

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

2 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings• The notion of s-function (or limitwise monotonic) was introduced by
Khisamiev1 . He used limitwise monotonic approximations of Σ02 sets
to study computable abelian p-groups.
• Coles, Downey, and Khoussainov2 used limitwise monotonic sets forbuilding computable linear orders with Π02 initial segments that are
not computably presentable and first introduced the term limitwisemonotonic function.

1 Khisamiev,N.G.: Constructive abelian p-groups. Sib.Adv.Math., 2, 68–113, 1992
2 Coles, R. J., Downey, R., Khoussainov, B.: On Initial Segments of Computable
Linear Orders. Order. 14(2), 107–121, 1997

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

3 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings• The notion of s-function (or limitwise monotonic) was introduced by
Khisamiev1 . He used limitwise monotonic approximations of Σ02 sets
to study computable abelian p-groups.
• Coles, Downey, and Khoussainov2 used limitwise monotonic sets forbuilding computable linear orders with Π02 initial segments that are
not computably presentable and first introduced the term limitwisemonotonic function.

1 Khisamiev,N.G.: Constructive abelian p-groups. Sib.Adv.Math., 2, 68–113, 1992
2 Coles, R. J., Downey, R., Khoussainov, B.: On Initial Segments of Computable
Linear Orders. Order. 14(2), 107–121, 1997

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

3 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings• Nowadays, limitwise monotonic functions and their generalizations
play an important role in modern computability theory. These
functions have become one of the standard tools for computability
theorists.

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

4 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings• Nowadays, limitwise monotonic functions and their generalizations
play an important role in modern computability theory. These
functions have become one of the standard tools for computability
theorists.

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

4 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings

Numberings and Reducibilities of Numberings
Definition• Any surjective mapping α of the set ω of natural numbers onto anonempty set A is called a numbering of A.
• So numbering is the assignment of natural numbers to a set ofobjects such as functions, rational numbers, graphs, or words insome formal language.
• Let α and β be numberings of A. We say that a numbering α isreducible to a numbering β (in symbols, α ⩽ β) if there exists a
computable function f such that α(n) = β(f (n)) for any n ∈ ω.
• We say that the numberings α and β are equivalent (in symbols,α ≡ β) if α ⩽ β and β ⩽ αZhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

5 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings

Numberings and Reducibilities of Numberings
Definition• Any surjective mapping α of the set ω of natural numbers onto anonempty set A is called a numbering of A.
• So numbering is the assignment of natural numbers to a set ofobjects such as functions, rational numbers, graphs, or words insome formal language.
• Let α and β be numberings of A. We say that a numbering α isreducible to a numbering β (in symbols, α ⩽ β) if there exists a
computable function f such that α(n) = β(f (n)) for any n ∈ ω.
• We say that the numberings α and β are equivalent (in symbols,α ≡ β) if α ⩽ β and β ⩽ αZhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

5 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings

Numberings and Reducibilities of Numberings
Definition• Any surjective mapping α of the set ω of natural numbers onto anonempty set A is called a numbering of A.
• So numbering is the assignment of natural numbers to a set ofobjects such as functions, rational numbers, graphs, or words insome formal language.
• Let α and β be numberings of A. We say that a numbering α isreducible to a numbering β (in symbols, α ⩽ β) if there exists a
computable function f such that α(n) = β(f (n)) for any n ∈ ω.
• We say that the numberings α and β are equivalent (in symbols,α ≡ β) if α ⩽ β and β ⩽ αZhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

5 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings

Numberings and Reducibilities of Numberings
Definition• Any surjective mapping α of the set ω of natural numbers onto anonempty set A is called a numbering of A.
• So numbering is the assignment of natural numbers to a set ofobjects such as functions, rational numbers, graphs, or words insome formal language.
• Let α and β be numberings of A. We say that a numbering α isreducible to a numbering β (in symbols, α ⩽ β) if there exists a
computable function f such that α(n) = β(f (n)) for any n ∈ ω.
• We say that the numberings α and β are equivalent (in symbols,α ≡ β) if α ⩽ β and β ⩽ αZhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

5 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings• Let A be some set of objects. We are interested only in thoseobjects that admit a certain constructive description.
• Define some language L and the interpretation of that language
determined as a partial surjective mapping i : L → A. For any objecta ∈ A, each "formula" in i−1 (a) is interpreted as a description of a.
• For example, if A consists of partial computable functions theni−1 (a) may be considered as a set of programs of Turing machines
for a.
• If A is a set of c.e. sets then a ∈ A is definable by Σ01 -formulas inarithmetics and we could consider i−1 (a) as a collection of suchformulas.
• For L, we consider a Gödel numbering G : ω → L.

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

6 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings• Let A be some set of objects. We are interested only in thoseobjects that admit a certain constructive description.
• Define some language L and the interpretation of that language
determined as a partial surjective mapping i : L → A. For any objecta ∈ A, each "formula" in i−1 (a) is interpreted as a description of a.
• For example, if A consists of partial computable functions theni−1 (a) may be considered as a set of programs of Turing machines
for a.
• If A is a set of c.e. sets then a ∈ A is definable by Σ01 -formulas inarithmetics and we could consider i−1 (a) as a collection of suchformulas.
• For L, we consider a Gödel numbering G : ω → L.

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

6 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings• Let A be some set of objects. We are interested only in thoseobjects that admit a certain constructive description.
• Define some language L and the interpretation of that language
determined as a partial surjective mapping i : L → A. For any objecta ∈ A, each "formula" in i−1 (a) is interpreted as a description of a.
• For example, if A consists of partial computable functions theni−1 (a) may be considered as a set of programs of Turing machines
for a.
• If A is a set of c.e. sets then a ∈ A is definable by Σ01 -formulas inarithmetics and we could consider i−1 (a) as a collection of suchformulas.
• For L, we consider a Gödel numbering G : ω → L.

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

6 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings• Let A be some set of objects. We are interested only in thoseobjects that admit a certain constructive description.
• Define some language L and the interpretation of that language
determined as a partial surjective mapping i : L → A. For any objecta ∈ A, each "formula" in i−1 (a) is interpreted as a description of a.
• For example, if A consists of partial computable functions theni−1 (a) may be considered as a set of programs of Turing machines
for a.
• If A is a set of c.e. sets then a ∈ A is definable by Σ01 -formulas inarithmetics and we could consider i−1 (a) as a collection of suchformulas.
• For L, we consider a Gödel numbering G : ω → L.

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

6 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings• Let A be some set of objects. We are interested only in thoseobjects that admit a certain constructive description.
• Define some language L and the interpretation of that language
determined as a partial surjective mapping i : L → A. For any objecta ∈ A, each "formula" in i−1 (a) is interpreted as a description of a.
• For example, if A consists of partial computable functions theni−1 (a) may be considered as a set of programs of Turing machines
for a.
• If A is a set of c.e. sets then a ∈ A is definable by Σ01 -formulas inarithmetics and we could consider i−1 (a) as a collection of suchformulas.
• For L, we consider a Gödel numbering G : ω → L.

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

6 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings

Computable Numberings
Definition
A numbering α : ω → A is called a computable numbering of A in thelanguage L with respect to the interpretation i if there exists a
computable function f for which the formula G(f (n)) distinguishes anelement α(n) in L relative to i, i.e. α(n) = i(G(f (n))) for all n ∈ ω.
• Goncharov and Sorbi3 generalized the theory of numberings todifferent notions of computability:
Let C be an abstract "notion" of computability, i.e., a countableclass of sets of numbers, and let A ⊆ C: then a numbering
α : ω → A is C-computable, if{< k, x >: x ∈ α(k)} ∈ C.
3 S. Goncharov and A. Sorbi. Generalized computable numerations and non-trivial
Rogers semilattices. Algebra and Logic, 36(6):359–369, 1997.

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

7 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings

Rogers semilattices• A family A ⊂ P (ω) is C-computable if A has a C-computable
numbering.
• By ComC (A) we denote the set of all C-computable numberings ofthe family A.
• Given numberings ν and µ of a family A, one defines a newnumbering ν ⊕ µ as follows.
(ν ⊕ µ)(2n) := ν(n), (ν ⊕ µ)(2n + 1) := µ(n).
• For a computable family A, the quotient structure
RC (A) := (ComC (A); ≤, ⊕)/≡
is an upper semilattice. It is called the Rogers semilattice 4 of thecomputable family A.
4 Rogers, H. Gödel numberings of partial recursive functions. The Journal of
Symbolic Logic, 23(3), 331-341.(1958)

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

8 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings

Rogers semilattices• A family A ⊂ P (ω) is C-computable if A has a C-computable
numbering.
• By ComC (A) we denote the set of all C-computable numberings ofthe family A.
• Given numberings ν and µ of a family A, one defines a newnumbering ν ⊕ µ as follows.
(ν ⊕ µ)(2n) := ν(n), (ν ⊕ µ)(2n + 1) := µ(n).
• For a computable family A, the quotient structure
RC (A) := (ComC (A); ≤, ⊕)/≡
is an upper semilattice. It is called the Rogers semilattice 4 of thecomputable family A.
4 Rogers, H. Gödel numberings of partial recursive functions. The Journal of
Symbolic Logic, 23(3), 331-341.(1958)

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

8 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings

Rogers semilattices• A family A ⊂ P (ω) is C-computable if A has a C-computable
numbering.
• By ComC (A) we denote the set of all C-computable numberings ofthe family A.
• Given numberings ν and µ of a family A, one defines a newnumbering ν ⊕ µ as follows.
(ν ⊕ µ)(2n) := ν(n), (ν ⊕ µ)(2n + 1) := µ(n).
• For a computable family A, the quotient structure
RC (A) := (ComC (A); ≤, ⊕)/≡
is an upper semilattice. It is called the Rogers semilattice 4 of thecomputable family A.
4 Rogers, H. Gödel numberings of partial recursive functions. The Journal of
Symbolic Logic, 23(3), 331-341.(1958)

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

8 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings

Rogers semilattices• A family A ⊂ P (ω) is C-computable if A has a C-computable
numbering.
• By ComC (A) we denote the set of all C-computable numberings ofthe family A.
• Given numberings ν and µ of a family A, one defines a newnumbering ν ⊕ µ as follows.
(ν ⊕ µ)(2n) := ν(n), (ν ⊕ µ)(2n + 1) := µ(n).
• For a computable family A, the quotient structure
RC (A) := (ComC (A); ≤, ⊕)/≡
is an upper semilattice. It is called the Rogers semilattice 4 of thecomputable family A.
4 Rogers, H. Gödel numberings of partial recursive functions. The Journal of
Symbolic Logic, 23(3), 331-341.(1958)

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

8 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings• Rogers semilattice RC (A) of a family A ⊆ Σin is a quotient
structure of all C– computable numberings of the family A modulo
equivalence of the numberings ordered by the relation induced by
reducibility of the numberings.
• RC (A) allows one to measure the different computations of a given
family A.
• It also serves as a tool to classify properties of C– computable
numberings for the different families A.

• The quotient structure RC (A) := (ComC (A); ≤, ⊕)/≡ is an upper
semilattice. If ComC (A) ̸= ∅, then we say that RC (A) is the Rogers
C-semilattice of the family A. For the sake of convenience, we use
the following standard notation for Rogers Σ0n -semilattices:
R0n (A) := RΣ0n (A).

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

9 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings• Rogers semilattice RC (A) of a family A ⊆ Σin is a quotient
structure of all C– computable numberings of the family A modulo
equivalence of the numberings ordered by the relation induced by
reducibility of the numberings.
• RC (A) allows one to measure the different computations of a given
family A.
• It also serves as a tool to classify properties of C– computable
numberings for the different families A.

• The quotient structure RC (A) := (ComC (A); ≤, ⊕)/≡ is an upper
semilattice. If ComC (A) ̸= ∅, then we say that RC (A) is the Rogers
C-semilattice of the family A. For the sake of convenience, we use
the following standard notation for Rogers Σ0n -semilattices:
R0n (A) := RΣ0n (A).

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

9 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings• Rogers semilattice RC (A) of a family A ⊆ Σin is a quotient
structure of all C– computable numberings of the family A modulo
equivalence of the numberings ordered by the relation induced by
reducibility of the numberings.
• RC (A) allows one to measure the different computations of a given
family A.
• It also serves as a tool to classify properties of C– computable
numberings for the different families A.

• The quotient structure RC (A) := (ComC (A); ≤, ⊕)/≡ is an upper
semilattice. If ComC (A) ̸= ∅, then we say that RC (A) is the Rogers
C-semilattice of the family A. For the sake of convenience, we use
the following standard notation for Rogers Σ0n -semilattices:
R0n (A) := RΣ0n (A).

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

9 / 19Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings

Limitwise monotonic numberings
We consider limitwise monotonic numberings for families S of l.m.sets.
In the definition, we use the following notation. Let n ≥ 1, and let F bea function acting from ω n+1 to ω. For numbers k1 , k2 , . . . , kn ∈ ω, wewrite F (k1 , k2 , . . . , kn , ·) to denote the unary function
g : y 7→ F (k1 , k2 , . . . , kn , y).

Definition
A numbering ν is limitwise monotonic if there exists a computablefunction f (k, z, s) with the following properties:
1. f (k, z, s) ≤ f (k, z, s + 1), for all k, z, s.
2. For every k and z, there exists a finite limit F (k, z) = lims f (k, z, s).
3. For every k, the set ν(k) is equal to the range of the function
F (k, ·).
Such a function f is called a limitwise monotonic approximation of thenumbering ν.
Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

10 / 19

Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings• We say that a family S is limitwise monotonic if it has a limitwisemonotonic numbering. Informally speaking, l.m. families S are
precisely those that admit a uniform l.m. approximation.
• For a l.m. family S, by Rlm (S) we denote the Rogers semilatticeinduced by the l.m. numberings of S. Notice that this is consistent
with the above introduced notation RC (S), by taking C to be theset of all l.m. numberings, and denoting in this case C = lm.

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

11 / 19

Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings• We say that a family S is limitwise monotonic if it has a limitwisemonotonic numbering. Informally speaking, l.m. families S are
precisely those that admit a uniform l.m. approximation.
• For a l.m. family S, by Rlm (S) we denote the Rogers semilatticeinduced by the l.m. numberings of S. Notice that this is consistent
with the above introduced notation RC (S), by taking C to be theset of all l.m. numberings, and denoting in this case C = lm.

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

11 / 19

Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings

Following the approach5 , we discuss reductions between types ofnumberings. Our reduction Γ transforms a Σ02 -computable family into al.m. family. The reduction Γ is very simple. Nevertheless, it is pretty
useful: as an immediate consequence, we obtain that every Rogers
Σ02 -semilattice R02 (S) is isomorphic to the semilattice Rlm (Γ(S)).

Definition
For a set A ⊆ ω, we set Γ(A) := A ⊕ ω. For a numbering ν, by Γ(ν) we
denote the following numbering: for k ∈ ω, define(Γ(ν))(k) := Γ(ν(k)).
For a family S, we define Γ(S) = {Γ(A) : A ∈ S}.

5 I. Herbert and S. Jain and S. Lempp and M. Mustafa and F. Stephan, Reductions
between types of numberings, 2017

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

12 / 19

Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings

Theorem
Let S be a Σ02 -computable family. Then the following holds:
1. The family Γ(S) is limitwise monotonic.
2. The operator Γ is a bijection from the set of all Σ02 -computable
numberings of S onto the set of all l.m. numberings of Γ(S).
3. A numbering ν ∈ ComΣ02 (S) is positive if and only if Γ(ν) is
positive. A similar fact is true for Friedberg numberings.
4. For any ν, µ ∈ ComΣ02 (S), we have ν ≤ µ if and only if
Γ(ν) ≤ Γ(µ).
Consequently, the semilattices R02 (S) and Rlm (Γ(S)) are isomorphic.
In particular, this implies that there are infinitely many pairwise
non-elementarily-equivalent Rogers semilattices for l.m. families.

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

13 / 19

Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings

TheoremSuppose that S is a l.m. family such that every set A ∈ S is infinite.
Then a numbering ν of the family S is limitwise monotonic if and only if
ν is Σ02 -computable. Consequently, the semilattices Rlm (S) and R02 (S)are equal.
These two theorems allow to transfer many known results on
Σ02 -computable families into the l.m. setting.

Corollary
There exist l.m. families Si , i ∈ ω, such that the corresponding Rogers
semilattices Rlm (Si ) are pairwise not elementarily equivalent.
Consequently, there are infinitely many isomorphism types of Rogers
l.m. semilattices.

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

14 / 19

Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings

We also establish some differences between Σ02 -computable families
and l.m. families.
• Proposition: For a non-zero n ∈ ω, consider the following finite
families:
Sn = {∅, {0}, {0, 1}, {0, 1, 2}, . . . , {0, 1, 2, . . . , n − 1}},
Tn = {{0}, {1}, {2}, {3}, . . . , {n}}.
The Rogers semilattices R01 (Sn ) and Rlm (Tn ) are isomorphic.

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

15 / 19

Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings• For a non-zero number n, consider the poset Pn , which is obtainedby deleting the greatest element from the finite poset (Sn , ⊆).
• Notice the following:• if m ̸= n, then the posets Pm and Pn are not isomorphic. By a
result of Ershov [?], this implies that the semilattices R01 (Sm ) andR01 (Sn ) are not isomorphic.
• Consequently, Proposition “transfers” infinitely many isomorphism
types of Rogers Σ01 -semilattices into the limitwise monotonic setting.

To our best knowledge, it is still unknown whether there exists a
Σ02 -computable family T such that the semilattice R02 (T ) is
isomorphic to R01 (Sn ) for some n ≥ 1.

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

16 / 19

Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings• For a non-zero number n, consider the poset Pn , which is obtainedby deleting the greatest element from the finite poset (Sn , ⊆).
• Notice the following:• if m ̸= n, then the posets Pm and Pn are not isomorphic. By a
result of Ershov [?], this implies that the semilattices R01 (Sm ) andR01 (Sn ) are not isomorphic.
• Consequently, Proposition “transfers” infinitely many isomorphism
types of Rogers Σ01 -semilattices into the limitwise monotonic setting.

To our best knowledge, it is still unknown whether there exists a
Σ02 -computable family T such that the semilattice R02 (T ) is
isomorphic to R01 (Sn ) for some n ≥ 1.

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

16 / 19

Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings

Cardinalities and Laticeness of Rogers Semilattice ofl.m.numberings

The first two problems on Rogers semilattices for computable families
were raised by Ershov(1967):(i) What are possible cardinalities of Rogers semilattices?
(ii) Can a non-one-element Rogers semilattice be a lattice?
Khutoretskii(1971) proved the following: if a Rogers semilattice R01 (S)contains more than one element, then it is infinite. Selivanov(1976)
established that an infinite R01 (S) cannot be a lattice.

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

17 / 19

Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings

We consider these two problems in the limitwise monotonic setting.
We obtain the following:

TheoremSuppose that a l.m. family S contains at least two elements. Then thesemilattice Rlm (S) is infinite, and it is not a lattice.

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

18 / 19

Motivation

Basic definition

Computable Numberings

Limitwise monotonic numberings

Thank you for your attention!

Zhansaya Tleuliyeva joint work with Bazhenov N. and Mustafa M.
Rogers Semilattices of limitwise monotonic numberings.

25 July, 2023

19 / 19