Algebra i logika
General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Algebra Logika:

Personal entry:
Save password
Forgotten password?

Algebra Logika, 2004, Volume 43, Number 3, Pages 291–320 (Mi al71)  

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

$\Sigma$-Subsets of Natural Numbers

A. S. Morozov, V. G. Puzarenko

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

Abstract: It is shown that the class of all possible families of $\Sigma$-subsets of finite ordinals in admissible sets coincides with a class of all non-empty families closed under $e$-reducibility and $\oplus$. The construction presented has the property of being minimal under effective definability. Also, we describe the smallest (w.r.t. inclusion) classes of families of subsets of natural numbers, computable in hereditarily finite superstructures. A new series of examples is constructed in which admissible sets lack in universal $\Sigma$-function. Furthermore, we show that some principles of classical computability theory (such as the existence of an infinite non-trivial enumerable subset, existence of an infinite computable subset, reduction principle, uniformization principle) are always satisfied for the classes of all $\Sigma$-subsets of finite ordinals in admissible sets

Keywords: admissible set, $\Sigma$-subset, finite ordinal, hereditarily finite superstructure, universal $\Sigma$-function

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

English version:
Algebra and Logic, 2004, 43:3, 162–178

Bibliographic databases:

UDC: 510.5
Received: 22.04.2002

Citation: A. S. Morozov, V. G. Puzarenko, “$\Sigma$-Subsets of Natural Numbers”, Algebra Logika, 43:3 (2004), 291–320; Algebra and Logic, 43:3 (2004), 162–178

Citation in format AMSBIB
\by A.~S.~Morozov, V.~G.~Puzarenko
\paper $\Sigma$-Subsets of Natural Numbers
\jour Algebra Logika
\yr 2004
\vol 43
\issue 3
\pages 291--320
\jour Algebra and Logic
\yr 2004
\vol 43
\issue 3
\pages 162--178

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. A. S. Morozov, “On the relation of $\Sigma$-reducibility between admissible sets”, Siberian Math. J., 45:3 (2004), 522–535  mathnet  crossref  mathscinet  zmath  isi
    2. I. Sh. Kalimullin, V. G. Puzarenko, “Computability Principles on Admissible Sets”, Siberian Adv. Math., 15:4 (2005), 1–33  mathnet  mathscinet  zmath
    3. V. G. Puzarenko, “Computability in special models”, Siberian Math. J., 46:1 (2005), 148–165  mathnet  crossref  mathscinet  zmath  isi
    4. A. N. Khisamiev, “On $\Sigma$-subsets of naturals over abelian groups”, Siberian Math. J., 47:3 (2006), 574–583  mathnet  crossref  mathscinet  zmath  isi
    5. A. N. Khisamiev, “On quasiresolvent periodic abelian groups”, Siberian Math. J., 48:6 (2007), 1115–1126  mathnet  crossref  mathscinet  zmath  isi
    6. I. Sh. Kalimullin, “Spectra of degrees of some structures”, Algebra and Logic, 46:6 (2007), 399–408  mathnet  crossref  mathscinet  zmath  isi
    7. Kalimullin I., “Some notes on degree spectra of the structures”, Computation and Logic in the Real World, Proceedings, Lecture Notes in Computer Science, 4497, 2007, 389–397  crossref  mathscinet  zmath  isi  scopus
    8. V. G. Puzarenko, “O semeistve vychislimykh mnozhestv na dopustimykh mnozhestvakh”, Sib. elektron. matem. izv., 5 (2008), 1–7  mathnet  mathscinet
    9. V. G. Puzarenko, “A certain reducibility on admissible sets”, Siberian Math. J., 50:2 (2009), 330–340  mathnet  crossref  mathscinet  isi
    10. I. Sh. Kalimullin, V. G. Puzarenko, “Reducibility on families”, Algebra and Logic, 48:1 (2009), 20–32  mathnet  crossref  mathscinet  zmath  isi
    11. A. N. Khisamiev, “$\Sigma$-Bounded algebraic systems and universal functions. I”, Siberian Math. J., 51:1 (2010), 178–192  mathnet  crossref  mathscinet  isi
    12. Khisamiev A.N., “Bounded algebraic systems and universal functions”, Doklady Mathematics, 81:2 (2010), 309–311  crossref  mathscinet  zmath  isi  elib  scopus
    13. V. G. Puzarenko, “Descriptive properties on admissible sets”, Algebra and Logic, 49:2 (2010), 160–176  mathnet  crossref  mathscinet  zmath  isi
    14. A. N. Khisamiev, “$\Sigma$-uniform structures and $\Sigma$-functions. I”, Algebra and Logic, 50:5 (2011), 447–465  mathnet  crossref  mathscinet  zmath  isi
    15. A. N. Khisamiev, “$\Sigma$-uniform structures and $\Sigma$-functions. II”, Algebra and Logic, 51:1 (2012), 89–102  mathnet  crossref  mathscinet  zmath  isi
    16. A. N. Khisamiev, “On a universal $\Sigma$-function over a tree”, Siberian Math. J., 53:3 (2012), 551–553  mathnet  crossref  mathscinet  isi
    17. A. N. Khisamiev, “Universal functions and almost $c$-simple models”, Siberian Math. J., 56:3 (2015), 526–540  mathnet  crossref  crossref  mathscinet  isi  elib  elib
    18. A. N. Khisamiev, “A class of almost $c$-simple rings”, Siberian Math. J., 56:6 (2015), 1133–1141  mathnet  crossref  crossref  mathscinet  isi  elib
    19. S. S. Goncharov, “Conditional terms in semantic programming”, Siberian Math. J., 58:5 (2017), 794–800  mathnet  crossref  crossref  isi  elib  elib
    20. S. S. Goncharov, D. I. Sviridenko, “Recursive terms in semantic programming”, Siberian Math. J., 59:6 (2018), 1014–1023  mathnet  crossref  crossref  isi  elib
    21. A. N. Khisamiev, “Universalnye funktsii i $K\Sigma$-struktury”, Sib. matem. zhurn., 61:3 (2020), 703–716  mathnet  crossref
    22. A. N. Khisamiev, “Universalnye funktsii i $\Sigma_{\omega}$-ogranichennye struktury”, Algebra i logika, 60:2 (2021), 210–230  mathnet  crossref
    23. A. N. Khisamiev, “Ob universalnykh funktsiyakh v nasledstvenno konechnykh nadstroikakh”, Matem. tr., 24:2 (2021), 160–180  mathnet  crossref
  • Алгебра и логика Algebra and Logic
    Number of views:
    This page:548
    Full text:135
    First page:1

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2022