General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Sibirsk. Mat. Zh.:

Personal entry:
Save password
Forgotten password?

Sibirsk. Mat. Zh., 2004, Volume 45, Number 3, Pages 634–652 (Mi smj1096)  

This article is cited in 13 scientific papers (total in 13 papers)

On the relation of $\Sigma$-reducibility between admissible sets

A. S. Morozov

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences

Abstract: Reducibility on admissible sets is studied which is a stronger version of the usual $\Sigma$-presentability of models. One of its informal prototypes is the interpretability of one computational device in the other. We obtain criteria of reducibility for recursively listed and pure sets, introduce the notion of jump, and prove exact boundaries for the ordinals of jumps. We also show that this reducibility is lifted to $\mathbb{HYP}$-superstructures. Several results are proven on the relations of this reducibility to some known reducibilities.

Keywords: definability, computability, reducibility, admissible set

Full text: PDF file (296 kB)
References: PDF file   HTML file

English version:
Siberian Mathematical Journal, 2004, 45:3, 522–535

Bibliographic databases:

UDC: 510.56
Received: 24.06.2003

Citation: A. S. Morozov, “On the relation of $\Sigma$-reducibility between admissible sets”, Sibirsk. Mat. Zh., 45:3 (2004), 634–652; Siberian Math. J., 45:3 (2004), 522–535

Citation in format AMSBIB
\by A.~S.~Morozov
\paper On the relation of $\Sigma$-reducibility between admissible sets
\jour Sibirsk. Mat. Zh.
\yr 2004
\vol 45
\issue 3
\pages 634--652
\jour Siberian Math. J.
\yr 2004
\vol 45
\issue 3
\pages 522--535

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. I. Sh. Kalimullin, V. G. Puzarenko, “Computability Principles on Admissible Sets”, Siberian Adv. Math., 15:4 (2005), 1–33  mathnet  mathscinet  zmath
    2. V. G. Puzarenko, “Computability in special models”, Siberian Math. J., 46:1 (2005), 148–165  mathnet  crossref  mathscinet  zmath  isi
    3. A. S. Morozov, “About the admissible predicates on admissible sets”, Siberian Math. J., 46:4 (2005), 668–674  mathnet  crossref  mathscinet  zmath  isi
    4. V. G. Puzarenko, “A certain reducibility on admissible sets”, Siberian Math. J., 50:2 (2009), 330–340  mathnet  crossref  mathscinet  isi
    5. A. I. Stukachev, “A jump inversion theorem for the semilattices of $\Sigma$-degrees”, Siberian Advances in Mathematics, 20:1 (2010), 68–74  mathnet  crossref  mathscinet
    6. Montalban A., “Rice Sequences of Relations”, Philos. Trans. R. Soc. A-Math. Phys. Eng. Sci., 370:1971, SI (2012), 3464–3487  crossref  mathscinet  zmath  adsnasa  isi  scopus
    7. Fokina E.B., Harizanov V., Melnikov A., “Computable Model Theory”, Turing'S Legacy: Developments From Turing'S Ideas in Logic, Lecture Notes in Logic, 42, ed. Downey R., Cambridge Univ Press, 2014, 124–194  mathscinet  isi
    8. A. I. Stukachev, “Processes and structures on approximation spaces”, Algebra and Logic, 56:1 (2017), 63–74  mathnet  crossref  crossref  mathscinet  isi
    9. I. Sh. Kalimullin, A. Kach, A. Montalbán, V. G. Puzarenko, M. Kh. Faizrakhmanov, “Jump inversions of algebraic structures and the $\Sigma$-definability”, Algebra and Logic, 57:2 (2018), 161–165  mathnet  crossref  crossref  isi
    10. Montalban A., “Coding and Definability in Computable Structures”, Notre Dame J. Form. Log., 59:3 (2018), 285–306  crossref  mathscinet  zmath  isi
    11. Calvert W., Frolov A., Harizanov V., Knight J., McCoy C., Soskova A., Vatev S., “Strong Jump Inversion”, J. Logic Comput., 28:7 (2018), 1499–1522  crossref  mathscinet  zmath  isi  scopus
    12. R. M. Korotkova, O. V. Kudinov, A. S. Morozov, “O vzaimnoi opredelimosti operatsii nad polyami”, Sib. matem. zhurn., 60:6 (2019), 1324–1334  mathnet  crossref
    13. Faizrahmanov M., Kach A., Kalimullin I., Montalban A., Puzarenko V., “Jump Inversions of Algebraic Structures and SIGMA-Definability”, Math. Log. Q., 65:1 (2019), 37–45  crossref  mathscinet  zmath  isi  scopus
  • Сибирский математический журнал Siberian Mathematical Journal
    Number of views:
    This page:215
    Full text:80

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020