Matematicheskie Trudy
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mat. Tr.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Matematicheskie Trudy, 2022, Volume 25, Number 1, Pages 177–197
DOI: https://doi.org/10.33048/mattrudy.2022.25.108
(Mi mt665)
 

On numberings for classes of families of total functions

M. Kh. Faizrahmanov

Institute of Mathematics and Mechanics, Kazan (Volga Region) Federal University
References:
Abstract: In the present article, we study computable numberings and the Rogers semilattices for classes of families of everywhere defined (total) computable functions. We prove that the isomorphism type of the Rogers semilattice for a finite class $\mathfrak{F}$ of computable families of total functions depends only on the order with respect to inclusion on the class $\mathfrak{F}$ itself and the class $C(\mathfrak{F})$ of the closures of its elements regarded as subsets of a Baire space. We obtain necessary and sufficient conditions for existence of universal numberings for finite classes of computable families of total functions. We also consider a question whether a class of families of total functions admitting a universal numbering is closed under the union of computable increasing sequences of its elements. For a computable class $\mathfrak{F}$ such that $C(\mathfrak{F})$ is finite, we prove that the Rogers semilattice is either trivial or infinite; moreover, in the latter case, this semilattice is not a lattice.
Key words: numbering, computable numbering, $\Sigma_n^0$-computable numbering, computable family, $\Sigma_n^0$-computable family, computable class of families, rogers semilattice, universal numbering.
Received: 11.05.2021
Revised: 15.07.2021
Accepted: 30.08.2021
Document Type: Article
UDC: 510.57
Language: Russian
Citation: M. Kh. Faizrahmanov, “On numberings for classes of families of total functions”, Mat. Tr., 25:1 (2022), 177–197
Citation in format AMSBIB
\Bibitem{Fai22}
\by M.~Kh.~Faizrahmanov
\paper On numberings for classes of families of total functions
\jour Mat. Tr.
\yr 2022
\vol 25
\issue 1
\pages 177--197
\mathnet{http://mi.mathnet.ru/mt665}
\crossref{https://doi.org/10.33048/mattrudy.2022.25.108}
Linking options:
  • https://www.mathnet.ru/eng/mt665
  • https://www.mathnet.ru/eng/mt/v25/i1/p177
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Математические труды Siberian Advances in Mathematics
    Statistics & downloads:
    Abstract page:73
    Full-text PDF :27
    References:19
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024