Algebraic Properties of Rogers Semilattices
of Arithmetical Numberings
Sergei Podzorov (podz@math.nsc.ru)
Novosibirsk State University (Russia)
A numbering of a set S is an arbitrary
surjective mapping from naturals onto S. A numbering of S is
called S0n-computable if S is a family of
arithmetical sets and there is an effective procedure computing
S0n-formulae which define the elements of S by the
indices of these elements. We say that numbering is
arithmetical if it is S0n-computable for some n. For
any fixed n all S0n-computable numberings of some fixed
S form a preordered structure with respect to usual reducibility
relation; its quotient is an upper semilattice which we call
Rogers semilattice and denote by Â0n(S).
Our talk is devoted to the different kind of problems concerned
with the algebraic properties of Â0n(S) for various n
and S. We consider the isomorphism types of initial segments and
intervals in Â0n(S), covers, questions on an existence
of the extremal elements of these semilattices, and other related
topics.
We intend also to give a sketch of proofs of the following two
results obtained recently.
For every n and every S0n+2-computable nontrivial family S,
each Lachlan semilattice is isomorphic to an ideal of Rogers semilattice
Â0n+2(S).
For every k and every discrete family S consisting
of k+2 S02-sets, Rogers semilattice Â02(S)
is isomorphic to the semilattice of c.e. m -degrees
with its top removed.
File translated from TEX by TTH, version 1.59.